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

Habe ich einen Haufen Daten, die voller Duplikate, und ich will zur Beseitigung der Duplikate. Sie wissen, z.B. [1, 1, 3, 5, 5, 5, 7] wird [1, 3, 5, 7].

Es sieht aus wie ich kann entweder std::map und std::set, um diese zu bewältigen. Aber ich bin mir nicht sicher ob es schneller ist, (a) legen Sie einfach alle Werte in die container, oder (b) überprüfen Sie, ob Sie bereits im container und nur einfügen, wenn Sie nicht - sind die Einsätze sehr leistungsfähig? Auch wenn es einen besseren Weg,... können Sie vorschlagen, eine schnelle Möglichkeit, dies zu tun?

Andere Frage - wenn die Daten, die ich bin, zu speichern, in Ihnen ist nicht so trivial, wie ganze zahlen, und stattdessen ist eine benutzerdefinierte Klasse, wie funktioniert der std::map zu verwalten, um Sie zu lagern (hash?) die Daten für den schnellen Zugriff per operator[]?

Ein set wäre mehr geeignet, da Sie nicht benötigen Sie einen zugehörigen Wert mit jedem element. Ich werde zu erraten, dass die Prüfung und dann das einfügen in den Satz langsamer sein wird als nur das einsetzen, denn Sie würden im wesentlichen werden dabei zwei Schlüssel suchen in der ehemaligen.
Durch die definition einer von den beiden wird überprüfen, für dich bei ausführen einfügen. I. e. Sie wird tun, was Sie sonst mit einigen anderen container: überprüfen Sie für existance. Persönlich, ich ' D gehen mit dem set, es sei denn, Sie sind absichtlich mapping etwas, um etwas anderes.
Ist die Daten immer sortiert? Weil es aussieht wie Sie wollen, std::unique, nicht einen neuen container
Nein, es ist nicht sortiert. Aber ich brauche einen container, um die Ergebnisse aus dem original-Datensatz (die muss ich behalten).
Danke an alle für Eure Antworten. Leider kann ich nicht markieren Sie alle. 🙂

InformationsquelleAutor Gigi | 2012-10-10

  1. 10

    std::map nicht hashing. std::unordered_map tut, aber das ist C++11. std::map und std::set beide nutzen einen Komparator, den Sie bieten. Die Klassen-templates Standardwerte für diesen Komparator, der kocht nach unten auf eine operator< Vergleich, aber Sie können Ihren eigenen stellen.

    Wenn Sie nicht brauchen, sowohl ein Schlüssel und ein Wert gespeichert werden (sieht man nicht), sollten Sie nur verwenden eine std::set, wie das ist, mehr angemessen ist.

    Des Standard nicht sagen, welche Daten die Strukturen maps und sets verwenden, unter der Haube, nur dass bestimmter Aktionen für bestimmte Zeit Komplexität. In Wirklichkeit, die meisten Implementierungen, die ich bin mir dessen bewusst, verwenden ein Baum.

    Macht es keinen Unterschied, Zeit-Komplexität-Weise, wenn Sie operator[] oder insert, aber ich würde insert oder operator[] vor, ich habe einen search gefolgt von einem insert wenn das Element nicht gefunden wird. Die später bedeuten würde, zwei getrennte Suchvorgänge einfügen ein Element in dem Satz.

    InformationsquelleAutor John Dibling

  2. 7

    Einer insert() auf einen der dazugehörigen Container hat eine find() um zu sehen, ob das Objekt vorhanden ist und fügt dann das Objekt. Einfach einfügen der Elemente in eine std::set<T> sollte die Beseitigung der Duplikate einigermaßen effizient.

    Je nach Größe des Fernsehers und das Verhältnis von Duplikaten, um eindeutige Werte, kann es schneller sein, um die Objekte in std::vector<T>, std::sort() dann, und verwenden Sie dann std::unique() zusammen mit std::vector<T>::erase() zu bekommen, entfernen Sie die Duplikate.

    "insert() [...] ist ein find() [aber wenn nicht gefunden] fügt..." - die code-Formatierung von find() es ergriffen werden könnten, von einigen Lesern als Aufruf an die find() API-Aufruf, in der Erwägung, dass insert(x) Implementierungen nicht buchstäblich .find(x) als wenn Sie nicht vorhanden gibt es keine Aufzeichnung (iterator), in dem die Suche abgebrochen wurde, die erforderlich ist, zu überspringen, ein weiteres O(logN) Baum traveral für die tatsächliche Einbringung. Sie bekommen konnte in der Nähe mit lower_bound gefolgt von der insert überlast mit einem iterator hint, aber insert Implementierungen behandelt diese intern für eine optimale Leistung.

    InformationsquelleAutor Dietmar Kühl

  3. 2

    Wie oft sollten Sie es tun?

    Inserts üblich ist:

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

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

    Wenn Sie füllen einmal:

    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

    InformationsquelleAutor Naszta

  4. 0

    Vorausgesetzt, der common implementation strategy for std::map und std::set, d.h. symmetrische binäre suchbäume, die beide einfügen " und "lookup", um eine Baum-traversal-um den Punkt zu finden, wo der Schlüssel sein sollte. So versagt lookup gefolgt von insertion wäre etwa doppelt so langsam wie nur einfügen.

    wie funktioniert der std::map zu verwalten, um Sie zu lagern (hash?) die Daten für den schnellen Zugriff per operator[]?

    Durch eine Vergleich-Funktion, die Sie angeben (oder std::less, die funktioniert, wenn Sie überlastung operator< auf Ihrem benutzerdefinierten Typ). In jedem Fall std::map und std::set sind nicht hash-Tabellen.

    InformationsquelleAutor Fred Foo

  5. 0

    std::set und std::map sind sowohl umgesetzt als rot-schwarz-Baum, soweit ich weiß. Und wahrscheinlich verwenden Sie nur einsetzen würde schneller sein (dann beide, weil Sie wäre eine Verdoppelung der lookup-Zeit).

    Auch map und set verwenden operator <. So lange, wie Sie Ihre Klasse definiert hat operator < Es würde in der Lage sein, um Sie als Schlüssel.

    InformationsquelleAutor tozka

Schreibe einen Kommentar