Ist die Reihenfolge der Iteration durch std :: map bekannt (und durch den Standard garantiert)?

158

Was ich meine ist - wir wissen, dass die std::mapElemente nach den Schlüsseln sortiert sind. Nehmen wir also an, die Schlüssel sind ganze Zahlen. Wenn ich von std::map::begin()bis zur std::map::end()Verwendung von a iteriere for, garantiert der Standard, dass ich konsequent durch die Elemente mit Schlüsseln iteriere, die in aufsteigender Reihenfolge sortiert sind?


Beispiel:

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

Wird dies garantiert gedruckt 234oder ist die Implementierung definiert?


Realer Grund: Ich habe einen std::mapmit intSchlüsseln. In sehr seltenen Situationen möchte ich alle Elemente mit einem Schlüssel durchlaufen, der größer als ein konkreter intWert ist. Ja, es klingt wie std::vectordie bessere Wahl, aber beachten Sie meine "sehr seltenen Situationen".


EDIT : Ich weiß, dass die Elemente von std::mapsortiert sind. Sie müssen nicht darauf hinweisen (für die meisten Antworten hier). Ich habe es sogar in meiner Frage geschrieben.
Ich habe nach den Iteratoren und der Reihenfolge gefragt, wenn ich durch einen Container iteriere. Danke @Kerrek SB für die Antwort.

Kiril Kirov
quelle
6
Falls Sie es nicht wussten: In Ihrem realen Leben können Sie map::upper_boundden Punkt finden, an dem Sie mit der Iteration beginnen können.
Steve Jessop
Ich weiß das und ich weiß genau, wo ich anfangen würde zu iterieren. Ich bin nur gewandert, wenn die Bestellung garantiert ist.
Kiril Kirov
Ein spärlicher Vektor wäre nicht sinnvoll, wenn Ihre Schlüssel (numerische Indizes) auf der ganzen Linie stark variieren. Ich verwende eine ähnliche Lösung, bei der der numerische Index eine kartesische y-Koordinate im dreidimensionalen Raum darstellt. Die Verwendung eines Vektors in diesem Szenario würde meinen Speicherbedarf um Gigabyte erhöhen. Ich denke also nicht, dass der Vektor hier ein Allheilmittel ist, weit davon entfernt.
Jonathan Neufeld
Ich verstehe die Frage nicht und werde durch ein Gedankenexperiment erklären, warum. Wenn Sie bereits wissen, dass die Elemente geordnet sind, wie könnte die Iteration nicht sein? Was bedeutet Bestellung überhaupt, wenn sie nicht für die Iteration gilt? Welche anderen Fälle gibt es, in denen die Reihenfolge wichtig ist, erkennbar ist usw.? (Die Antwort wurde von Konstantin gegeben .)
underscore_d

Antworten:

176

Ja, das ist garantiert. Darüber hinaus *begin()gibt Ihnen die kleinste und *rbegin()das größte Element, wie durch den Vergleichsoperator bestimmt, und zwei Schlüsselwerte aund bfür die der Ausdruck !compare(a,b) && !compare(b,a)wahr ist gleich betrachtet werden . Die Standardvergleichsfunktion ist std::less<K>.

Die Reihenfolge ist kein Glücksbonus, sondern ein grundlegender Aspekt der Datenstruktur, da die Reihenfolge verwendet wird, um zu bestimmen, wann zwei Schlüssel gleich sind (gemäß der obigen Regel) und um eine effiziente Suche durchzuführen (im Wesentlichen eine Binärdatei) Suche, die logarithmische Komplexität in der Anzahl der Elemente hat).

Kerrek SB
quelle
std :: map wird mit binären Bäumen implementiert, daher wird technisch keine binäre Suche durchgeführt.
jupp0r
11
@ jupp0r: Die Strukturierung eines Bereichs als binärer Suchbaum ist eine besondere Methode, um die binäre Suche durch den Bereich zu implementieren. "Binäre Suche" ist eher ein abstraktes Konzept als eine bestimmte Implementierung. Es spielt keine Rolle, ob Sie durch Offsets in ein Array springen oder Verbindungsknoten folgen. Dies sind nur bestimmte Methoden, um "den Bereich zu halbieren".
Kerrek SB
1
Ich weiß, dass dies ein alter Beitrag ist, aber um klar zu sein, ist die "effiziente Suche" relativ. Technisch std::unordered_maphat der eine effizientere Suchzeit von O (1). Der Vorteil von std::mapliegt in der Schlüsselreihenfolge, aber nicht in der Suche.
Adam Johnston
42

Dies wird durch die Anforderungen an assoziative Container im C ++ - Standard garantiert. Siehe z. B. 23.2.4 / 10 in C ++ 11:

Die grundlegende Eigenschaft von Iteratoren assoziativer Container ist, dass sie
Durchlaufen Sie die Container in der nicht absteigenden Reihenfolge der Schlüssel, in denen
Nicht absteigend wird durch den Vergleich definiert, mit dem sie erstellt wurden.
Für zwei beliebige dereferenzierbare Iteratoren i und j, so dass der Abstand von i zu j ist
positiv,
  value_comp (* j, * i) == false

und 23.2.4 / 11

Für assoziative Container mit eindeutigen Schlüsseln gilt die stärkere Bedingung:
  value_comp (* i, * j)! = false.
Konstantin Oznobihin
quelle
32

Ich denke, es gibt eine Verwirrung in den Datenstrukturen.

In den meisten Sprachen ist a mapeinfach ein AssociativeContainer: Es ordnet einen Schlüssel einem Wert zu. In den "neueren" Sprachen wird dies im Allgemeinen mithilfe einer Hash-Map erreicht, sodass keine Reihenfolge garantiert wird.

In C ++ ist dies jedoch nicht so:

  • std::mapist ein sortierter assoziativer Container
  • std::unordered_map ist ein auf Hash-Tabellen basierender assoziativer Container, der in C ++ 11 eingeführt wurde

Also, um die Garantien bei der Bestellung zu klären.

In C ++ 03:

  • std::set, std::multiset, std::mapUnd std::multimapwerden entsprechend den Tasten zu bestellen garantiert (und das Kriterium geliefert)
  • in std::multisetund std::multimaplegt der Standard keine Bestellgarantie für äquivalente Elemente fest (dh solche, die gleich sind)

In C ++ 11:

  • std::set, std::multiset, std::mapUnd std::multimapwerden entsprechend den Tasten zu bestellen garantiert (und das Kriterium geliefert)
  • In std::multisetund schreibtstd::multimap der Standard vor, dass äquivalente Elemente (diejenigen, die gleich sind) gemäß ihrer Einfügereihenfolge (zuerst zuerst eingefügt) geordnet sind.
  • std::unordered_*Container werden, wie der Name schon sagt, nicht bestellt. Am bemerkenswertesten ist die Reihenfolge der Elemente kann geändert werden, wenn der Behälter verändert wird (beim Einfügen / Löschen).

Wenn der Standard besagt, dass Elemente in einer bestimmten Reihenfolge angeordnet sind, bedeutet dies:

  • Beim Iterieren sehen Sie die Elemente in der definierten Reihenfolge
  • Wenn Sie in umgekehrter Reihenfolge iterieren, sehen Sie die Elemente in umgekehrter Reihenfolge

Ich hoffe, das klärt Verwirrung.

Matthieu M.
quelle
Das hat nichts mit meiner Frage zu tun, sorry :) Ich weiß, welche bestellt sind und welche - nicht. Und ich frage nach der Reihenfolge, wenn ich die Elemente durchlaufe.
Kiril Kirov
10
@KirilKirov: Nun, die Definition eines geordneten assoziativen Containers ist, dass die Elemente beim Durchlaufen geordnet werden.
Matthieu M.
Nun, ich denke du hast recht, aber ich wusste das nicht und genau das habe ich gefragt :)
Kiril Kirov
4

Wird garantiert 234 gedruckt oder ist die Implementierung definiert?

Ja, std::mapist ein sortierter Behälter, der von Keyder mitgelieferten bestellt wird Comparator. So ist es garantiert.

Ich möchte alle Elemente mit einem Schlüssel durchlaufen, der größer als ein konkreter int-Wert ist.

Das ist sicher möglich.

jpalecek
quelle
3

Ja ... die Elemente in a std::maphaben eine strikte schwache Reihenfolge, was bedeutet, dass die Elemente aus einer Menge bestehen (dh es gibt keine Wiederholungen von Schlüsseln, die "gleich" sind), und die Gleichheit wird durch Testen einer beliebigen bestimmt zwei Schlüssel A und B: Wenn Schlüssel A nicht kleiner als Schlüssel B und B nicht kleiner als A ist, ist Schlüssel A gleich Schlüssel B.

Abgesehen davon können Sie die Elemente von a nicht richtig sortieren, std::mapwenn die schwache Reihenfolge für diesen Typ nicht eindeutig ist (in Ihrem Fall, in dem Sie Ganzzahlen als Schlüsseltyp verwenden, ist dies kein Problem). Sie müssen in der Lage sein, eine Operation zu definieren, die eine Gesamtreihenfolge für den Typ definiert, den Sie für die Schlüssel in Ihrem verwenden std::map. Andernfalls haben Sie nur eine Teilreihenfolge für Ihre Elemente oder Posets, deren Eigenschaft A möglicherweise nicht mit A vergleichbar ist B. In diesem Szenario können Sie normalerweise die Schlüssel / Wert-Paare einfügen. Wenn Sie jedoch die gesamte Karte durchlaufen und / oder "fehlende" Elemente erkennen, werden möglicherweise doppelte Schlüssel / Wert-Paare angezeigt. Schlüssel / Wert-Paare, wenn Sie versuchen, std::map::find()ein bestimmtes Schlüssel / Wert-Paar in der Karte auszuführen .

Jason
quelle
Wie die anderen Antworten, beantwortet dies meine Frage nicht wirklich, danke trotzdem.
Kiril Kirov
-3

begin () kann das kleinste Element ergeben. Aber es hängt von der Umsetzung ab. Ist es im C ++ - Standard angegeben? Wenn nicht, ist es gefährlich, diese Annahme zu treffen.

Pyang
quelle