map 和 unordered_map

Question

对比

operation	map	unordered_map
Ordering	increasing order (by default)	No ordering
Implementation	Self balancing BST (RBT)	Hash Table
search time	log(n)	O(1) -> Average O(N)-> Worst Case
Insertion time	log(n) + Rebalance	Same as search
Deletion time	log(n) + Rebalance	Same as search

Use std::map when

• You need ordered data.
• You would have to print/access the data (in sorted order).
• You need predecessor/successor of elements.
• See advantages of BST over Hash Table for more cases.

Use std::unordered_map when

• You need to keep count of some data (Example – strings) and no ordering is required.
• You need single element access i.e. no traversal.

unordered_set && set

• unordered_set 类似 于 unordered_map No ordering Hash Table
• set: RBT

Code

std::map<int, std::string> ismap;
isunordered[100] = "test000";
isunordered[10] = "test001";
isunordered[110] = "test002";
isunordered[9] = "test003";
isunordered[1100] = "test004";
isunordered[107] = "test005";
ismap[100] = "test000";
ismap[10] = "test001";
ismap[110] = "test002";
ismap[9] = "test003";
ismap[1100] = "test004";
ismap[107] = "test005";
std::cout << "unordered :" << std::endl;
for (auto x : isunordered)
{
	std::cout << x.first << " : " << x.second.c_str() << std::endl;
}
std::cout << "map :" << std::endl;
for (auto x : ismap)
{
	std::cout << x.first << " : " << x.second.c_str() << std::endl;
}

Result :

unordered :
100 : test000
10 : test001
110 : test002
9 : test003
1100 : test004
107 : test005
map :
9 : test003
10 : test001
100 : test000
107 : test005
110 : test002
1100 : test004