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

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

---

내 말은- 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

I'd like go iterate through all elements, with key, greater than a concrete int value.

That is surely possible.

---

Yes ... the elements in a std::map have a strict weak-ordering, meaning that the elements will be composed of a set (i.e., there will be no repeats of keys that are "equal"), and equality is determined by testing on any two keys A and B, that if key A is not less than key B, and B is not less than A, then key A is equal to key B.

That being said, you cannot properly sort the elements of a std::map if the weak-ordering for that type is ambiguous (in your case, where you are using integers as the key-type, that is not a problem). You must be able to define a operation that defines a total order on the type you are using for the keys in your std::map, otherwise you will only have a partial order for your elements, or poset, which has property where A may not be comparable to B. What will typically happen in this scenario is that you'll be able to insert the key/value pairs, but you may end up with duplicate key/value pairs if you iterate through the entire map, and/or detect "missing" key/value pairs when you attempt to perform a std::map::find() of a specific key/value pair in the map.

---

begin() may give the smallest element. But it is implementation depended. Is it specified in the C++ standard? If not, then it is dangerous to make this assumption.

참고URL : https://stackoverflow.com/questions/7648756/is-the-order-of-iterating-through-stdmap-known-and-guaranteed-by-the-standard