algorithm - what is the difference between set and unordered_set in C++? -

came across question, similar not @ same since talks java, has different implementation of hash-tables, virtue of having synchronized accessor /mutators differences between hashmap , hashtable?

so difference in c++ implementation of set , unordered_set ? question can ofcourse extended map vs unordered_map , on other c++ containers.

here initial assessment

set : while standard doesnt explicitly asks implemented trees, time-complexity constraint asked operations find/insert, means implemented tree. rb tree (as seen in gcc 4.8), height-balanced. since height balanced, have predictable time-complexity find()

pros : compact (compared other ds in comparison)

con : access time complexity o(lg n)

unordered_set : while standard doesnt explicitly asks implemented trees, time-complexity constraint asked operations find/insert, means implemented hash-table.

pros :

1. faster (promises amortized o(1) search)
2. easy convert basic primitives thread-safe, compared tree-ds

cons :

1. look not guaranteed o(1) therotical worst case o(n)
2. not compact tree. (for practical purposes load factors never 1)

note : o(1), hashtable comes assumption there no collision. load-factor of .5, every second variable insertion leading collision. observed load-factor of hash-table inversely proportional number of operations required accessing element in it. more reduce #operations, sparser hash-table. when element stored of size comparable pointer, overhead quite significant.

edit : since saying question contains sufficient answer in it, changing question "did miss difference between map/set performance analysis 1 should know ??"

i think you've answered own question, however, this:

not compact tree. (for practical purposes load factors never 1)

is not true. each node of tree (we'll assume it's red-black tree) type t utilizes space equal @ least 2 * pointer_size + sizeof(t) + sizeof(bool). may 3 * pointer size depending on whether tree contains parent pointer each tree node.

compare hash-map: there wasted array space each hash map due fact load factor < 1 you've said. however, assuming hash map uses singly linked lists chaining (and really, there's no real reason not to), each element inserted take sizeof(t) + pointer size.

note analysis ignores overhead may come space used alignment.

for element t has small size (so, basic type), size of pointers , other overhead dominates. @ load factor of > 0.5 (for example) std::unordered_set may indeed use less memory equivalent std::set.

the other big missing point fact iterating through std::set guaranteed produce ordering smallest largest, based on given comparison function, while iterating through std::unordered_set return values in "random" order.