Gibt es einen anderen Container, der einem Set mit der Lookup-Leistung eines Vektors ähnlich ist?

Question

Grundsätzlich habe ich viele Vektoren, die binäre Daten speichern. Ich möchte sie duplizieren. Das erste, was mir in den Sinn kam, ist ein set. Die Nachschlagleistung von set stimmt jedoch nicht mit der eines Vektors überein. Gibt es einen anderen Container, der Daten duplizieren und schneller ausführen kann? Ich brauche schnelle Suche, weil die Binärdaten von einem Server abgerufen, dedupliziert und an den Client gesendet werden, und dies ist ein kontinuierlicher Prozess.

Answer 1

Sie haben viele Möglichkeiten, aber alles hängt von Ihren Daten ab. Gehen für eine *set Datenstruktur klingt wie die Standardoption, aber Sie müssen Maßnahme mit einigen realistischen Datensätzen.

Lassen Sie mich einige kurze Punkte zu den verfügbaren Containern notieren, die Sie überprüfen können.

• Set

   
  Elements are sorted. 
  Don't have to worry about removing of duplicate entries. 
  Its a node based container, so no performance benefits from cache locality. 
  Try to go for boost::flat_set 
  

• unordered_set

   
  No ordering of elements, So not sorted by default. 
  Hash based container, so would seem like it would provide better performance. 
  Hashing of large keys will result in poor performance, 
  So, will have to resort to an augmented data structure which maps the actual data key to some integer value based on partial hashing of the key or something. 
  But, that depends upon hashing performance. Again, *Measure* (can't stress enough) 
  

• Vector

   
  Upto a certain number of elements, this would certainly beat std::set for performance. 
  Upto you to find that range. 
  std::sort followed by std::unique will give you deduplicated range of data. 
  Should consider boost::flat_set before implementing a set using vector on your own. 
  

• boost :: flat_set

   
  Already discussed as above. 
  

Um es zusammenzufassen, Sie haben Ihre Leistungsmessung Tests auf Ihrem Datensatz zu tun.