De ce ar folosi cineva set în loc de unordered_set?

Neordonate seturi trebui să plătească pentru O(1) mediu de timp de acces în câteva moduri:

• "set" utilizări mai puțin de memorie decât unordered_set` pentru a stoca același număr de elemente.
• Pentru un număr mic de elemente, căutări într-un " set " ar putea fi rapid decât căutări într-un unordered_set.
• Chiar dacă multe operațiuni sunt mai rapide în mediu de caz pentru unordered_set, ele sunt de multe ori garantate de a avea mai bine mai rău caz complexitatea pentru " set "(de exemplu "insert").
• Acel " set " sortează elementele este util dacă doriți să accesați-le în ordine.
• Puteți lexicographically compara diferite set e cu<,<=,> " și " >=.unordered_set nu sunt necesare pentru a sprijini aceste operațiuni.

Atunci când, pentru cineva care vrea să itera peste elementele de set, ordinea conteaza.

Ori de câte ori ai prefera un copac pentru un tabel hash.

De exemplu, tabele de dispersie sunt "O(n)" în cel mai rău caz. O(1) este media de caz. Copacii sunt "O(log n)" în cel mai rău.

Utilizarea setat atunci când:

1. Avem nevoie ordonat de date(elemente distincte).
2. Ne-ar trebui pentru a imprima/acces la date (în ordine sortată).
3. Avem nevoie de predecesorul/succesorul de elemente.

Utilizarea unordered_set atunci când:

1. Avem nevoie de a păstra un set de elemente distincte și nu de a comanda este necesar.
2. Avem nevoie de un singur element acces adică nu traversare.

Exemple:

set:

Intrare : 1, 8, 2, 5, 3, 9

Ieșire : 1, 2, 3, 5, 8, 9

Unordered_set:

Intrare : 1, 8, 2, 5, 3, 9

Ieșire : 9 3 1 8 2 5 (poate acest ordin, influențată de funcție hash)

În principal de diferența :

[![introduceți descrierea imaginii aici][1]][1]

Notă:(în unele cazuri " set "este mai convenabil) de exemplu, folosind "vector" ca element-cheie

set s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout

Ia în considerare sweepline algoritmi. Acești algoritmi ar eșua cu totul cu tabele de dispersie, dar lucra frumos cu echilibrată copaci. Să vă dau un exemplu concret de o sweepline algoritmul ia în considerare avere's algoritm. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Pentru std::set face parte din Standardul C++ și unordered_set e't. C++0x NU este un standard, și nici Impuls. Pentru mulți dintre noi, portabilitatea este esențial, și asta înseamnă că lipirea la standard.

Un lucru mai mult, în plus față de ceea ce alți oameni deja menționat. În timp ce așteptam amortizat complexitate pentru inserarea unui element la o unordered_set este O(1), fiecare acum și apoi voi lua O(n) deoarece hash-table trebuie să fie restructurate (numărul de compartimente trebuie să se schimbe) - chiar și cu o 'bine' funcție hash. Doar ca inserarea unui element într-un vector are O(n) fiecare acum și apoi pentru că stau la baza matrice trebuie să fie realocate.

Inserarea într-un set întotdeauna nevoie de cel mult O(log n). Acest lucru ar putea fi de preferat în unele aplicații.

Scuză-mă, încă un lucru demn de remarcat despre sortate de proprietate:

Dacă vrei o serie de date în container, de exemplu: Ai stocate timp în set, si tu vrei timp de 2013-01-01 să 2014-01-01.

Pentru unordered_set este imposibil.

Desigur, acest exemplu ar fi mai convingătoare pentru utilizare cazuri între harta și unordered_map.

g++ 6.4 stdlibc++ ordonat vs mulțime neordonată de referință

Am evaluate această dominantă Linux implementare C++ pentru a vedea diferența:

Plin de referință detalii și analiză au fost date la: https://stackoverflow.com/questions/2558153/what-is-the-underlying-data-structure-of-a-stl-set-in-c/51944661#51944661 și eu nu le voi repeta aici.

"BST" inseamna "testat cu std::setși "hash map" inseamna "testat cu std::unordered_set. "Rabla" este pentru std::priority_queue care am analizat la: https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst/29548834#29548834

Ca un scurt rezumat:

• grafic arată în mod clar că, în aceste condiții, hashmap de inserție au fost întotdeauna mult mai repede atunci când există mai mult de 100 de articole, iar diferența crește pe măsură ce crește numărul de elemente

Costul acestui impuls de viteză este că nu sunt în măsură să eficient traversa în ordine.

• curbele sugerează în mod clar că a ordonat std::set este BST-a bazat și std::unordered_set este hashmap bazează. În referință raspuns, mi-a mai confirmat că prin GDB pas de depanare codul.

Întrebare similară pentru harta vs unordered_map: https://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of-trivial-keys

Dacă doriți să aveți lucruri de rezolvat, atunci v-ar folosi set în loc de unordered_set. unordered_set este folosit de peste setat atunci când comanda stocate nu contează.

Pe mână, aș spune că este convenabil de a avea lucrurile într-o relație dacă're în căutarea de a converti într-un format diferit.

Este posibil, de asemenea, că în timp ce unul este mai rapid de a accesa, de timp pentru a construi indicele sau de memorie folosit la crearea și/sau accesarea acestuia este mai mare.