L’ordine di iterazione di std :: map è noto (e garantito dallo standard)?

Quello che voglio dire è che sappiamo che gli elementi di std::map sono ordinati in base alle chiavi. Quindi, diciamo che le chiavi sono numeri interi. Se eseguo l’iterazione da std::map::begin() a std::map::end() utilizzando un for , lo standard garantisce che eseguirò di conseguenza gli elementi con le chiavi, ordinati in ordine crescente?


Esempio:

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

È garantito stampare 234 o è stata definita l’implementazione?


Motivo della vita reale: ho una std::map con le chiavi int . In situazioni molto rare, mi piacerebbe scorrere tutti gli elementi, con una chiave, maggiore di un valore int concreto. Sì, sembra che std::vector sia la scelta migliore, ma nota le mie “situazioni molto rare”.


EDIT : Lo so, che gli elementi di std::map sono ordinati .. non c’è bisogno di indicarlo (per la maggior parte delle risposte qui). L’ho scritto anche nella mia domanda.
Stavo chiedendo agli iteratori e all’ordine quando sto iterando attraverso un container. Grazie a @Kerrek SB per la risposta.

Sì, è garantito. Inoltre, *begin() ti dà il più piccolo e *rbegin() l’elemento più grande, come determinato dall’operatore di confronto, e due valori chiave b per i quali l’espressione !compare(a,b) && !compare(b,a) è vero sono considerati uguali. La funzione di confronto predefinita è std::less .

L’ordinamento non è una funzione bonus fortunata, ma piuttosto è un aspetto fondamentale della struttura dati, poiché l’ordinamento viene utilizzato per determinare quando due chiavi sono uguali (secondo la regola precedente) e per eseguire una ricerca efficiente (essenzialmente un binario ricerca, che ha complessità logaritmica nel numero di elementi).

Questo è garantito dai requisiti del contenitore associativo nello standard C ++. Ad esempio, vedere 23.2.4 / 10 in C ++ 11:

 La proprietà fondamentale degli iteratori dei contenitori associativi è che loro
 scorrere tra i contenitori nell'ordine non discendente di chiavi in ​​cui
 non discendente è definito dal confronto utilizzato per costruirli.
 Per ogni due iteratori dereferenziabili i e j tali che la distanza da I a J sia
 positivo,
   value_comp (* j, * i) == false

e 23.2.4 / 11

 Per i contenitori associativi con chiavi univoche vale la condizione più forte,
   value_comp (* i, * j)! = false.

Penso che ci sia una confusione nelle strutture dati.

Nella maggior parte delle lingue, una map è semplicemente un AssociativeContainer: associa una chiave a un valore. Nelle lingue “più recenti”, questo è generalmente ottenuto usando una mappa hash, quindi nessun ordine è garantito.

In C ++, tuttavia, non è così:

  • std::map è un contenitore associativo ordinato
  • std::unordered_map è un contenitore associativo basato sulla tabella hash introdotto in C ++ 11

Quindi, al fine di chiarire le garanzie sull’ordine.

In C ++ 03:

  • std::set , std::multiset , std::map e std::multimap sono garantiti per essere ordinati in base alle chiavi (e al criterio fornito)
  • in std::multiset e std::multimap , lo standard non impone alcuna garanzia di ordine su elementi equivalenti (cioè, quelli che si equivalgono)

In C ++ 11:

  • std::set , std::multiset , std::map e std::multimap sono garantiti per essere ordinati in base alle chiavi (e al criterio fornito)
  • in std::multiset e std::multimap , lo Standard impone che gli elementi equivalenti (quelli che sono uguali) siano ordinati in base al loro ordine di inserimento (prima inserito per primo)
  • std::unordered_* contenitori std::unordered_* sono, come suggerisce il nome, non ordinati. In particolare, l’ordine degli elementi può cambiare quando il contenitore viene modificato (dopo l’inserimento / la cancellazione).

Quando lo standard dice che gli elementi sono ordinati in un modo, significa che:

  • quando si itera, si vedono gli elementi nell’ordine definito
  • quando si passa al contrario, si vedono gli elementi nell’ordine opposto

Spero che questo chiarisca ogni confusione.

È garantito stampare 234 o è stata definita l’implementazione?

Sì, std::map è un contenitore ordinato, ordinato dalla Key con il Comparator fornito. Quindi è garantito.

Mi piacerebbe andare avanti attraverso tutti gli elementi, con la chiave, maggiore di un valore int concreto.

Questo è sicuramente ansible.

Sì … gli elementi di una std::map hanno un severo ordine debole, il che significa che gli elementi saranno composti da un insieme (cioè, non ci saranno ripetizioni di chiavi che sono “uguali”), e l’uguaglianza è determinata testando su due chiavi A e B, che se la chiave A non è inferiore alla chiave B e B non è minore di A, allora il tasto A è uguale alla chiave B.

Detto questo, non puoi ordinare correttamente gli elementi di una std::map se l’ordine debole per quel tipo è ambiguo (nel tuo caso, dove stai usando numeri interi come tipo di chiave, non è un problema). Devi essere in grado di definire un’operazione che definisce un ordine totale sul tipo che stai utilizzando per le chiavi nella tua std::map , altrimenti avrai solo un ordine parziale per i tuoi elementi, o poset, che ha una proprietà dove A potrebbe non può essere paragonabile a B. Ciò che normalmente accade in questo scenario è che sarete in grado di inserire le coppie chiave / valore, ma potreste finire con coppie chiave / valore duplicate se si scorre l’intera mappa e / o rilevare coppie chiave / valore “mancanti” quando si tenta di eseguire una std::map::find() di una coppia chiave / valore specifica nella mappa.