Was ist der Unterschied zwischen std :: set und std :: map

Question

Ich bin relativ neu in C++ Programmierung und fragte mich, ob jemand helfen könnte, ein paar Fragen für mich zu klären.

http://www.cplusplus.com/reference/set/set/

http://www.cplusplus.com/reference/map/map/

Ich habe gelesen, wie STL binäre Suchbäume zu implementieren und ich halte zu bemerken, dass std :: gesetzt und std :: map als die Methoden ständig erwähnt zur Durchführung solcher eine Aufgabe. Was genau ist der Unterschied zwischen den beiden? Für mich scheinen beide fast identisch zu sein, und ich bin mir nicht sicher, ob es etwas gibt, das ich nicht bemerke, das einen für bestimmte Aufgaben besser macht als den anderen. Gibt es einen Vorteil, std :: set über std :: map zu verwenden, um einen STL-binären Suchbaum zu implementieren, der Werte von einem Array oder Vektor (wie zum Beispiel Geschwindigkeit) akzeptiert?

Wenn jemand mir helfen könnte, dieses Konzept zu verstehen, würde ich es sehr schätzen!

Answer 1

Sowohl std::set als auch std::map sind associative containers. Der Unterschied besteht darin, dass std::sets nur den Schlüssel enthält,
während in std::map dort ein zugehöriges Wert ist, dass, wenn A -> B, dann map [A] = B, das funktioniert wie hashing aber nicht O(1) statt O(log N).

Sie können weiter sehen unordered_map, die den Betrieb in O(1) Zeit bietet.

std::set speichert Daten im sortierten Format.
Die Implementierung von beiden erfolgt durch ausgeglichene Bäume (wie AVL oder Rot-Schwarz-Bäume) geben O(logN) Zeit Komplexität.

Aber wichtig zu beachten ist, dass beide eindeutige Werte speichern können. Um das zu überwinden, müssen Sie auch multimap und multiset sehen.

Hoffe, das hilft!

Update: Im Fall von Rot-Schwarz-Baum Neugewichtung Rotation ist ein O(1) Betrieb während mit AVL ist dies ein O(log n) Betrieb, so dass der Rot-Schwarz-Baum effizienter in diesem Aspekte der Neugewichtung Bühne und einer der möglichen Gründe, dass es häufiger verwendet wird.