C++0x este introducerea unordered_set
care este disponibil în "impuls" și multe alte locuri. Ceea ce am înțeles este că unordered_seteste tabel hash cu
O(1)lookup complexitate. Pe de altă parte, " set " nu este nimic, dar un copac cu log(n)
lookup complexitate. De ce pe pământ ar folosi cineva " set " în loc de unordered_set
? eu.e e nevoie de un " set " de-acum?
Neordonate seturi trebui să plătească pentru O(1) mediu de timp de acces în câteva moduri:
unordered_set
.unordered_set
, ele sunt de multe ori garantate de a avea mai bine mai rău caz complexitatea pentru " set "(de exemplu "insert").,
<=,
> " și " >=.
unordered_set nu sunt necesare pentru a sprijini aceste operațiuni.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:
Utilizarea unordered_set atunci când:
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 :
Notă:(în unele cazuri " set "este mai convenabil) de exemplu, folosind "vector" ca element-cheie
set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});
for(const auto& vec:s)
cout<<vec<<endl; // I have override << for vector
// 1 2
// 1 3
Motivul pentru care vector<int>
poate fi la fel de tasta " set "pentru că" vector " suprascrie operatorul<
.
Dar, dacă folosiți unordered_set<vector<int>>
trebuie să creați o funcție hash pentru vector
struct VectorHash {
size_t operator()(const std::vector<int>& v) const {
std::hash<int> hasher;
size_t seed = 0;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
return seed;
}
};
vector<vector<int>> two(){
//unordered_set<vector<int>> s; // error vector<int> doesn't have hash function
unordered_set<vector<int>, VectorHash> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});
for(const auto& vec:s)
cout<<vec<<endl;
// 1 2
// 1 3
}
puteți vedea că, în unele cazuri unordered_set
este mult mai complicat.
În principal citat din: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006
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
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:
Costul acestui impuls de viteză este că nu sunt în măsură să eficient traversa în ordine.
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
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.