Czy kolejność iteracji przez std :: map jest znana (i gwarantowana przez standard)?

Chodzi mi o to - wiemy, że std::mapelementy są posortowane według kluczy. Powiedzmy, że klucze są liczbami całkowitymi. Jeśli wykonam iterację od std::map::begin()do std::map::end()a for, czy standard gwarantuje, że będę konsekwentnie przechodzić przez elementy z kluczami posortowane w kolejności rosnącej?

Przykład:

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;
}

Czy jest to gwarantowane do druku, 234czy jest to zdefiniowana implementacja?

Powód z życia: mam klucz std::mapz intkluczami. W bardzo rzadkich sytuacjach chciałbym powtórzyć wszystkie elementy, z kluczem, większym niż konkretna intwartość. Tak, wygląda na to, że std::vectorbyłby to lepszy wybór, ale zwróć uwagę na moje „bardzo rzadkie sytuacje”.

EDYCJA : Wiem, że elementy std::mapsą posortowane… nie trzeba na to zwracać uwagi (dla większości odpowiedzi tutaj). Napisałem to nawet w swoim pytaniu.
Pytałem o iteratory i kolejność, gdy przechodzę przez kontener. Dzięki @Kerrek SB za odpowiedź.

Tak, to gwarantowane. Co więcej, *begin()daje najmniejszą i *rbegin()największą elementu, określona przez operatora porównania i dwie kluczowe wartości ai bdla których wyrażenie !compare(a,b) && !compare(b,a)jest prawdziwe są uważane za równe. Domyślną funkcją porównania jest std::less<K>.

Porządkowanie nie jest szczęśliwą funkcją bonusową, ale jest raczej fundamentalnym aspektem struktury danych, ponieważ kolejność jest używana do określenia, kiedy dwa klucze są takie same (zgodnie z powyższą regułą) i do wydajnego wyszukiwania (zasadniczo binarny wyszukiwanie, które ma logarytmiczną złożoność w liczbie elementów).

Gwarantują to wymagania dotyczące kontenerów asocjacyjnych w standardzie C ++. Np. Patrz 23.2.4 / 10 w C ++ 11:

Podstawową właściwością iteratorów kontenerów asocjacyjnych jest to, że one
iteruj przez kontenery w nie malejącej kolejności kluczy, gdzie
nie-malejąco jest definiowane przez porównanie, które zostało użyte do ich skonstruowania.
Dla dowolnych dwóch iteratorów dereferencyjnych i i j takich, że odległość od i do j wynosi
pozytywny,
  value_comp (* j, * i) == false

i 23.2.4 / 11

W przypadku kontenerów asocjacyjnych z unikalnymi kluczami obowiązuje silniejszy warunek,
  value_comp (* i, * j)! = false.

Myślę, że istnieje zamieszanie w strukturach danych.

W większości języków a mapjest po prostu AssociativeContainer: mapuje klucz do wartości. W „nowszych” językach jest to generalnie osiągane przy użyciu mapy mieszania, dlatego nie jest gwarantowana kolejność.

Jednak w C ++ tak nie jest:

• std::mapto posortowany kontener asocjacyjny
• std::unordered_map jest asocjacyjnym kontenerem opartym na tablicy skrótów wprowadzonym w C ++ 11

Tak więc, aby wyjaśnić gwarancje przy zamówieniu.

W C ++ 03:

• std::set, std::multiset, std::mapI std::multimapsą zagwarantowane uporządkowane zgodnie z tymi przyciskami (i kryterium zestawie)
• w std::multiseti std::multimap, norma nie narzuca żadnej gwarancji zamówienia na równoważne elementy (tj. takie, które porównują równe)

W C ++ 11:

• std::set, std::multiset, std::mapI std::multimapsą zagwarantowane uporządkowane zgodnie z tymi przyciskami (i kryterium zestawie)
• w std::multiseti std::multimap, norma narzuca, że równoważne elementy (te, które porównują równe sobie) są sortowane zgodnie z kolejnością wstawiania (pierwsze wstawione jako pierwsze)
• std::unordered_*kontenery, jak sama nazwa wskazuje, nie są zamawiane. Przede wszystkim kolejność elementów może się zmienić, gdy kontener jest modyfikowany (po wstawieniu / usunięciu).

Gdy Norma mówi, że elementy są uporządkowane w sposób, oznacza to, że:

• podczas iteracji zobaczysz elementy w zdefiniowanej kolejności
• podczas wykonywania iteracji w odwrotnej kolejności elementy są wyświetlane w odwrotnej kolejności

Mam nadzieję, że to wyjaśni wszelkie nieporozumienia.

Czy to gwarantuje wydruk 234, czy zdefiniowano jego implementację?

Tak, std::mapjest to sortowany pojemnik, zamawiany przez Keydostawcę Comparator. Więc jest to gwarantowane.

Chciałbym przejść przez wszystkie elementy, z kluczem, większym niż konkretna wartość int.

To z pewnością możliwe.

Tak ... elementy w std::map mają ścisłą słabą kolejność, co oznacza, że ​​elementy będą składać się z zestawu (tj. Nie będzie powtórzeń kluczy, które są „równe”), a równość jest określana przez testowanie na dowolnym dwa klucze A i B, jeśli klucz A jest nie mniejszy niż klucz B i B jest nie mniejszy niż klucz A, to klucz A jest równy kluczowi B.

Mając to na uwadze, nie możesz poprawnie posortować elementów a, std::mapjeśli słaba kolejność dla tego typu jest niejednoznaczna (w twoim przypadku, gdy używasz liczb całkowitych jako typu klucza, nie stanowi to problemu). Musisz być w stanie zdefiniować operację, która definiuje całkowitą kolejność według typu, którego używasz dla kluczy w swoim std::map, w przeciwnym razie będziesz mieć tylko częściowe zamówienie dla swoich elementów lub poset, który ma właściwość, w której A może nie być porównywalne z B. W tym scenariuszu zazwyczaj zdarza się, że będziesz w stanie wstawić pary klucz / wartość, ale możesz skończyć z zduplikowanymi parami klucz / wartość, jeśli przejdziesz przez całą mapę i / lub wykryjesz „brakujące” pary klucz / wartość podczas próby wykonania std::map::find()określonej pary klucz / wartość na mapie.

begin () może dać najmniejszy element. Ale to zależy od implementacji. Czy jest to określone w standardzie C ++? Jeśli nie, to takie założenie jest niebezpieczne.