C++ 사양에 따라 std :: set 반복 순서가 항상 오름차순입니까?

여기 http://www.cplusplus.com/reference/stl/set/ std :: set in C++는 "일반적으로"트리 (적색 - 검정색)로 구현되고 정렬됩니다.C++ 사양에 따라 std :: set 반복 순서가 항상 오름차순입니까?

내가 이해할 수 없다는 뜻입니까? 사양으로 집합의 반복 순서는 항상 오름차순입니까? 또는 "일반적인 구현 세부 사항"일 뿐이고 때때로 일부 라이브러리/컴파일러가이 규칙을 위반할 수 있습니까? 당신이 순서를 인쇄 할 경우 사양 세트의 반복 순서에 의해

는

출처

2012-01-12 Rodion Gorkovenko

C++ 표준에 따라 std::set의 요소에 대한 반복은 std::less 또는 선택적 비교 술어 템플릿 인수로 결정된 정렬 된 순서로 진행됩니다.

(또한 C++ 표준, 삽입, 검색 및 삭제 당 그래서 균형을 검색 나무, 현재 std::set에 대한 유일한 가능한 구현 선택이다, 대부분의 O (LG 전자에서 N)의 시간이 걸릴에도 사용 레드 - 블랙 불구하고 나무가 표준에 의해 위임되지 않습니다.)

출처

2012-01-12 11:05:38

항상

예, 세트의 값은 항상 상승하는

을 오름차순입니다. 설명에서 알 수 있듯이 일반적으로 RBT (Red-Black Tree)를 사용하여 구현되지만 컴파일러 작성자는이를 위반하는 옵션이 있지만 일반적으로 다른 구현은 리소스를 효율적으로 구현할 수 없으므로 RBT 테마에 충실합니다 set의 작업.

출처

2012-01-12 11:04:47

기본 비교기가 적기 때문에 세트는 오름차순으로 정렬됩니다. 이를 변경하기 위해 다른 기존 또는 사용자 지정 비교기를 템플릿 인수로 지정할 수 있습니다.

출처

2012-01-12 11:06:44

이는 내부적으로 std::set이 해당 요소를 정렬 된 트리로 저장한다는 의미입니다. 그러나이 스펙은 정렬 순서에 대해서는 아무 것도 말하지 않는다. 기본적으로 std::set은 std::less을 사용하므로 낮음에서 높음으로 정렬됩니다. 그래서 예를 들면

std::set<valueType, comparissonStruct> myCustomOrderedSet;

std::set<int, std::greater<int> > myInverseSortedSet;

또는 사실

struct cmpStruct { 
    bool operator() (int const & lhs, int const & rhs) const 
    { 
    return lhs > rhs; 
    } 
}; 

std::set<int, cmpStruct > myInverseSortedSet;

, 이러한 예는 또한 그러나이 생성자를 사용하여 정렬 기능을 사용하면 원하는대로 될 수 있습니다 링크 된 웹 사이트에서 제공됩니다. 보다 구체적으로 여기에 : set constructor.

출처

2012-01-12 11:07:15 Darhuuk

C++ 11 N3337 표준 초안http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf

23.2.4는 "연관 컨테이너"라고 :

1 연관 컨테이너는 키를 기준으로 데이터의 빠른 검색을 제공합니다. 이 라이브러리는 집합 컨테이너, 집합, 다중 집합,지도 및 다중 맵의 네 가지 기본 종류 인 연관 컨테이너를 제공합니다.

하고 :

10 연관 컨테이너 반복기의 기본적인 속성은 비 - 강하가 있었던 비교에 의해 정의 된 키의 비 내림차순 용기 반복이다 그들을 구성하는 데 사용되는 .

은 너무 예, 순서는 기본적으로 언급 https://stackoverflow.com/a/11812871/895245로 균형 탐색 트리 구현을 필요로하는 C++ 표준에 의해 보장된다.

또한 C++ 11 unordered_set과 대조적으로 제한이 적기 때문에 성능이 향상 될 수 있습니다. 예 : Why on earth would anyone use set instead of unordered_set?. 해시 세트를 사용합니다.

출처

2017-01-02 10:11:04

C++ 사양에 따라 std :: set 반복 순서가 항상 오름차순입니까?

답변

관련 문제