C++ std :: map oder std :: set - effizient Duplikate einfügen

Question

Ich habe eine Reihe von Daten voller Duplikate und ich möchte die Duplikate zu beseitigen. Sie wissen z.B. [1, 1, 3, 5, 5, 5, 7] wird zu [1, 3, 5, 7].

Es sieht so aus, als ob ich entweder std :: map oder std :: set verwenden kann. Ich bin mir jedoch nicht sicher, ob es schneller ist, (a) einfach alle Werte in den Container einzufügen oder (b) zu prüfen, ob sie bereits im Container vorhanden sind und nur einfügen, wenn sie nicht - sind Einsätze sehr effizient? Selbst wenn es einen besseren Weg gibt ... kannst du einen schnellen Weg vorschlagen, dies zu tun?

Eine weitere Frage - wenn die Daten, die ich in ihnen speichern nicht so trivial wie Integers ist, und stattdessen eine benutzerdefinierte Klasse ist, wie verwaltet die std :: map die Daten für schnell zu speichern (Hash?) Zugriff über Operator []?

Answer 1

std::map nicht Hashing nicht verwendet. std::unordered_map tut, aber das ist C++ 11. std::map und std::set verwenden beide einen Komparator, den Sie bereitstellen. Die Klassenvorlagen haben Standardwerte für diesen Komparator, der auf einen Vergleich operator< hinausläuft, aber Sie können Ihren eigenen bereitstellen.

Wenn Sie weder einen Schlüssel noch einen zu speichernden Wert benötigen (sieht so aus als ob Sie es nicht tun), sollten Sie einfach eine std::set verwenden, da dies angemessener ist.

Der Standard sagt nicht, welche Datenstrukturen map s und set s unter der Haube verwenden, nur dass bestimmte Aktionen bestimmte Zeitkomplexitäten haben. In der Realität verwenden die meisten Implementierungen, die ich kenne, einen Baum.

Es macht keinen Unterschied zeit Komplexität weise, wenn Sie operator[] oder insert verwenden, aber ich würde insert oder operator[] verwenden, bevor ich eine search von einem insert gefolgt tat, wenn das Element nicht gefunden wird. Letzteres würde zwei getrennte Suchen implizieren, um ein Element in das Set einzufügen.

Answer 2

Unter der Annahme der gemeinsamen Implementierungsstrategie für std::map und std::set, d. H. Ausgeglichene binäre Suchbäume, müssen sowohl die Einfügung als auch die Suche eine Baumdurchquerung durchführen, um den Punkt zu finden, wo der Schlüssel sein sollte. Ein fehlgeschlagener Suchvorgang gefolgt von einer Einfügung wäre ungefähr doppelt so langsam wie nur das Einfügen.

wie funktioniert das std :: map verwalten richtig speichern (Hash?) Die Daten für einen schnellen Zugriff über Operator []?

Mittels einer Vergleichsfunktion, die Sie angeben (oder std::less, die, wenn Sie operator< auf Ihrem benutzerdefinierten Typ Überlastung funktioniert). In jedem Fall sind std::map und std::setnicht Hash-Tabellen.

Answer 3

Ein insert() auf einem der zugeordneten Container macht eine find(), um zu sehen, ob das Objekt existiert und fügt dann das Objekt ein. Einfaches Einfügen der Elemente in eine std::set<T> sollte die Duplikate einigermaßen effizient beseitigen.

Je nach Größe des Geräts und das Verhältnis von Duplikaten zu eindeutigen Werten, kann es schneller sein, um die Objekte in std::vector<T> zu setzen, std::sort() dann, und dann std::unique() zusammen verwenden mit std::vector<T>::erase() loszuwerden, den Duplikaten zu erhalten.

Answer 4

Wie oft sollten Sie es tun?

Wenn Einsatz ist üblich:

//*/ 
std::set<int> store; 
/*/ 
// for hash: 
std::unordered_set<int> store; 
//*/ 
int number; 

if (store.insert(number).second) 
{ 
    // was not in store 
} 

Wenn Sie einmal füllen:

std::vector<int> store; 
int number; 

store.push_back(number); 
std::sort(store.begin(),store.end()); 
store.erase(std::unique(store.begin(),store.end()),store.end()); 

// elements are unique 

Answer 5

std::set und std::map sind beide als rot schwarz Baum soweit ich weiß implementiert. Und wahrscheinlich würde nur die Einfügung schneller sein (dann beides, weil Sie die Nachschlagezeit verdoppeln würden).

Auch map und set Verwendung operator <. Solange Ihre Klasse operator < definiert hat, könnte sie diese als Schlüssel verwenden.