Erkennung von Duplikaten mit Set

Question

Ich arbeite mit Daten, die nicht zweimal auftauchen sollten. Wenn dies der Fall ist, sollte es dies erkennen und eine Funktion aufrufen, die das behandelt.

Derzeit schiebe ich einige Daten in einen Vektor und vor dem Einfügen sollte es überprüfen, ob die Daten bereits in diesem Vektor enthalten sind. Im Moment ist dies nicht sehr effektiv, z

for (int i = 0; i < myVector.size() ; i++) 
{ 
    if (myVector[i] == data) 
    { 
      // invoke function 
      return false; 
    } 
} 

Ich weiß set ist eine besondere Art von Vektor, der nur einzigartige Daten ermöglicht.

Gibt es eine andere Möglichkeit, doppelte Daten zu erkennen, die der set hinzugefügt werden (oder zumindest versuchen, sie hinzuzufügen)?

Answer 1

Lassen Sie uns zunächst nur klar sein, dass ein set nicht eine besondere Art von vector ist. Es ist eine Art Container, orthogonal zum Vektor, der zufällige Duplikate verhindert.

Sie können Duplikate erkennen durch den Rückgabewert von insert Überprüfung:

if(my_set.insert("value").second == false) { do_something_for_duplicate(); } 

Answer 2

std::set gibt std::pair<iterator, bool> zurück, wobei die boolfalse ist, wenn das Einfügen fehlgeschlagen ist (z. B. durch Hinzufügen doppelter Werte).

Beispiel:

std::set<int> set{ 1, 2, 3 }; 
auto result = set.insert(1); 
if (!result.second) 
    std::cout << "Failed to insert element!" << std::endl; 

Answer 3

Sie eine std::unordered_set verwenden können. Es gibt eine Methode insert, die, abhängig von der Bibliotheksversion, Ihnen Informationen über die Einfügung zurückgibt (entweder ein Paar mit einer bool, das wahr ist, wenn die Einfügung effektiv war und false, wenn bereits), oder einen Iterator, etc. Suchen Sie die Dokumentation Ihrer lib .

Answer 4

A std::set oder std::unordered_set sind ein weiterer Container von Standard C++ Library, aber keine vector ... Sie gehorchen unterschiedliche Regeln:

• ein Vektor ist mehr oder weniger eine wachstumsfähige Array: keine Kontrolle über Duplikate , aber respektieren Sie den Anzeigenauftrag
• ein Satz erfordert einen Auftrag für die Daten, die er enthält, und ermöglicht es, seine Daten gemäß dieser Reihenfolge zu durchsuchen. Es ablehnt automatisch Duplikate bei Einfügezeitpunkt
• eine unordered_set auch Duplikate bei Einfügezeitpunkt ablehnen, aber die Browse-Reihenfolge ist eine Art zufällig (nicht genau, es sogar vollkommen deterministisch ist, sondern hängt von der Hash-Funktion verwendet wird)

Für einen Vektor ein einfacher Weg, um zu sehen, ob es bereits einen Wert enthält, ist (ref):

std::find(vector.begin(), vector.end(), item) != vector.end() 

für einen Satz von unordered_set kehrt der Insert-Methode ein Iterator Paar zu dem Element zeigen - boolean wo es anzeigt, wurde hinzugefügt oder nicht, um schon da zu sein

if (! my_set.insert(data).second) { 
    // invoke function 
    return false; 
}