2012-10-10 6 views
6

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].C++ std :: map oder std :: set - effizient Duplikate einfügen

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 []?

+1

Ein 'set' wäre besser geeignet, da Sie für jedes Element keinen zugehörigen Wert benötigen. Ich gehe davon aus, dass das Überprüfen und Einfügen in das Set langsamer ist als das Einfügen, da Sie im Wesentlichen zwei Schlüsselsuchen durchführen müssen. – GWW

+3

Per Definition wird jeder von denen * für Sie * überprüfen, wenn die Einfügung durchgeführt wird. I.e. Sie werden tun, was Sie sonst mit einem anderen Behälter tun würden: auf Existenz prüfen. Persönlich würde ich mit dem Set gehen, wenn Sie nicht absichtlich etwas auf etwas anderes abbilden. – WhozCraig

+3

Sind die Daten immer sortiert? Weil es so aussieht, als ob Sie [std :: unique] (http://msdn.microsoft.com/en-us/library/9f5eztca (v = vs.100) .aspx) wollen, kein neuer Container –

Antwort

9

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.

0

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.

7

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.

+0

* "' insert() '[...] tut ein' find() '[aber wenn nicht gefunden] fügt ..." * - die code-style Formatierung von 'find()' dort könnte genommen werden von einigen Lesern als Aufruf für den 'find()' API Aufruf, während 'insert (x)' Implementierungen nicht buchstäblich '.find (x)' verwenden, da wenn nicht vorhanden ist, gibt es keine Aufzeichnung von (iterator to) Die Suche wurde abgebrochen, was benötigt wird, um ein anderes O (logN) -Tever für die tatsächliche Einfügung zu überspringen. Sie könnten mit 'lower_bound', gefolgt von der 'insert'-Überladung mit einem Iterator' hint 'näher kommen, aber' insert'-Implementierungen werden dies intern für eine optimale Leistung handhaben. –

2

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 
0

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.