[c++] std :: map을 반복하는 순서가 알려져 있습니까 (그리고 표준에 의해 보장됨)?

C++ / 글쓴이

내 말은- std::map의 요소가 키에 따라 정렬되어 있다는 것을 알고 있습니다. 키가 정수라고 가정 해 봅시다. std::map::begin()를 std::map::end()사용하여 반복하는 경우 for표준에 따라 키가있는 요소를 오름차순으로 정렬하여 결과적으로 반복한다는 보장이 있습니까?

예:

std::map<int, int> map_;
map_[1] = 2;
map_[2] = 3;
map_[3] = 4;
for( std::map<int, int>::iterator iter = map_.begin();
     iter != map_.end();
     ++iter )
{
    std::cout << iter->second;
}

인쇄가 보장 234됩니까, 아니면 구현이 정의되어 있습니까?

실생활 이유 : 나는이 std::map와 int키. 매우 드문 상황에서 구체적인 int값 보다 큰 키를 사용하여 모든 요소를 ​​반복하고 싶습니다 . 같은 네, 그것은 소리가 std::vector더 나은 선택이 될,하지만 내 “매우 드문 경우”를 알 것이다.

편집 : 나는 요소 std::map가 정렬되어 있음을 알고 있습니다 . 지적 할 필요가 없습니다 (대부분의 답변은 여기에 있음). 나는 심지어 내 질문에 그것을 썼다.
컨테이너를 반복 할 때 반복자와 순서에 대해 묻고있었습니다. @Kerrek SB에게 감사합니다.

답변

예, 보장됩니다. 또한 비교 연산자에 의해 결정된 가장 *begin()작고 가장 *rbegin()큰 요소를 제공하며 두 가지 주요 값 a과 b표현식 !compare(a,b) && !compare(b,a)이 참인 것으로 간주됩니다. 기본 비교 기능은 std::less<K>입니다.

순서는 운이 좋은 보너스 기능이 아니라 데이터 구조의 기본 측면입니다. 순서는 두 키가 동일한 시점 (위 규칙에 따라)을 결정하고 효율적인 조회 (본질적으로 이진)를 수행하는 데 사용되기 때문입니다. 요소 수에 로그 복잡성이있는 검색).

답변

이는 C ++ 표준의 연관 컨테이너 요구 사항에 의해 보장됩니다. 예를 들어 C ++ 11에서 23.2.4 / 10 참조 :

연관 컨테이너 반복자의 기본 속성은
내림차순이 아닌 키 순서로 컨테이너를 반복합니다.
비 내림차순은이를 구성하는 데 사용 된 비교에 의해 정의됩니다.
참조 할 수없는 두 반복자 i 및 j의 경우, i에서 j까지의 거리는
양,
  value_comp (* j, * i) == 거짓

23.2.4 / 11

고유 한 키가있는 연관 컨테이너의 경우 더 강력한 상태가 유지됩니다.
  value_comp (* i, * j)! = 거짓.

답변

데이터 구조에 혼란이 있다고 생각합니다.

대부분의 언어에서 a map는 AssociativeContainer입니다. 키를 값에 매핑합니다. “최신”언어에서는 일반적으로 해시 맵을 사용하여이 작업을 수행하므로 순서가 보장되지 않습니다.

그러나 C ++에서는 그렇지 않습니다.

  • std::mapA는 정렬 연관 컨테이너
  • std::unordered_map C ++ 11에 도입 된 해시 테이블 기반 연관 컨테이너입니다.

따라서 주문에 대한 보장을 명확히하기 위해.

C ++ 03에서 :

  • std::set, std::multiset, std::map및 std::multimap키에 따라 정렬을 보장 (및 기준 공급)된다
  • in std::multiset및 std::multimap에서 표준은 동등한 요소 (즉, 동일하게 비교되는 요소)에 대해 어떠한 주문 보증도하지 않습니다.

C ++ 11에서 :

  • std::set, std::multiset, std::map및 std::multimap키에 따라 정렬을 보장 (및 기준 공급)된다
  • 로 std::multiset하고 std::multimap, 표준이 부과 등가의 요소 (동일한 비교하는 것들)을 그들의 삽입 순서에 따라 정렬된다 (제 1 제 삽입)
  • std::unordered_*컨테이너는 이름에서 알 수 있듯이 주문되지 않았습니다. 가장 주목할만한 점 은 컨테이너가 수정 될 때 (삽입 / 삭제시) 요소의 순서 가 변경 될 수 있다는 것입니다.

표준에 따르면 요소가 어떤 방식으로 주문되었다고 말하면 다음을 의미합니다.

  • 반복하면 정의 된 순서대로 요소가 표시됩니다.
  • 반대로 반복하면 요소가 반대 순서로 표시됩니다

이것이 혼란을 없애기를 바랍니다.

답변

이것이 234를 인쇄하도록 보장됩니까, 아니면 구현이 정의되어 있습니까?

예, 제공된 std::map으로 정렬 된 분류 된 컨테이너 입니다. 따라서 보장됩니다.KeyComparator

구체적인 int 값보다 큰 키를 사용하여 모든 요소를 ​​반복하고 싶습니다.

확실히 가능합니다.

답변

예 …의 요소 std::map는 엄격한 약한 순서를 갖습니다. 즉, 요소가 집합으로 구성되며 (즉, “동일한”키가 반복되지 않음) 동일성은 테스트를 통해 결정됩니다. 두 개의 키 A와 B, 키 A가 키 B보다 작지 않고 B가 A보다 작 으면 키 A는 키 B와 같습니다.

즉, std::map해당 유형의 약한 순서가 모호한 경우 ( 요소의 경우 키 유형으로 정수를 사용하는 경우 문제가되지 않음) 의 요소를 올바르게 정렬 할 수 없습니다 . 의 키에 사용하는 유형에 대한 총 순서를 정의하는 작업을 정의 할 수 있어야합니다 std::map. 그렇지 않으면 A와 비교할 수없는 속성이있는 요소 또는 poset에 대한 부분 순서 만 갖습니다. B.이 시나리오에서 일반적으로 발생하는 것은 키 / 값 쌍을 삽입 할 수 있지만 전체 맵을 반복하거나 “누락”을 감지하면 중복 키 / 값 쌍으로 끝날 수 있다는 것입니다. std::map::find()맵에서 특정 키 / 값 쌍 을 수행하려고 할 때 키 / 값 쌍.

답변

begin ()은 가장 작은 요소를 제공 할 수 있습니다. 그러나 구현에 따라 다릅니다. C ++ 표준에 지정되어 있습니까? 그렇지 않다면이 가정을하는 것은 위험합니다.

답변