STL Unordered Container

Container, STL

Unordered Container

Unordered Containers
Internal Structure of Unordered Sets and Multisets
Internal Structure of Unordered Maps and Multimaps

包含头文件<unordered_set>或<unordered_map>。

定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
namespace std {
	template <typename T,
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<T> >
	class unordered_set;
	template <typename T,
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<T> >
	class unordered_multiset;
	template <typename Key, typename T,
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<pair<const Key, T> > >
	class unordered_map;
	template <typename Key, typename T,
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<pair<const Key, T> > >
	class unordered_multimap;
}

unordered set或multiset的元素必须是可比较的。
unordered map或multimap的key和value都必须copyable或movable。key必须在指定相等比较标准下可比较。
内置的hash<>支持所有内置类型，特殊的类型需要提供自己的hash function。性能就取决于hash function的质量。
Unordered Container。内部用hash table实现。
前向迭代器。key是const的，只能删除再添加，不能修改。erase操作不会让迭代器失效。insert/rehash/reverse/clear会导致rehash，从而让迭代器失效。

Unordered容器的操作

Create, Copy, and Destroy

Operation Effect
Unord c Default constructor; creates an empty unordered container without any elements
Unord c(bnum) Creates an empty unordered container that internally uses at least bnum buckets
Unord c(bnum, hf) Creates an empty unordered container that internally uses at least bnum buckets and hfas hash function
Unord c(bnum, hf, cmp) Creates an empty unordered container that internally uses at least bnum buckets, hfas hash function, and cmp as predicate to identify equal values
Unord c(c2) Copy constructor; creates a copy of another unordered container of the same type (all elements are copied)
Unord c = c2 Copy constructor; creates a copy of another unordered container of the same type (all elements are copied)
Unord c(rv) Move constructor; creates an unordered container, taking the contents of the rvalue rv (since C++11)
Unord c = rv Move constructor; creates an unordered container, taking the contents of the rvalue rv (since C++11)
Unord c(beg, end) Creates an unordered container initialized by the elements of the range [beg,end)
Unord c(beg, end, bnum) Creates an unordered container initialized by the elements of the range [beg,end) that internally uses at least bnum buckets
Unord c(beg, end, bnum, hf) Creates an unordered container initialized by the elements of the range [beg,end) that internally uses at least bnum buckets and hfas hash function
Unord c(beg, end, bnum, hf, cmp) Creates an unordered container initialized by the elements of the range [beg,end) that internally uses at least bnum buckets, hfas hash function, and cmp as predicate to identify equal values
Unord c(initlist) Creates an unordered unordered container initialized by the elements of the initializer list initlist
Unord c = initlist Creates an unordered unordered container initialized by the elements of the initializer list initlist
c.~Unord() Destroys all elements and frees the memory

其中Unord可以是：

Unord Effect
unordered_set<Elem> An unordered set that by default hashes with hash<> and compares equal_to<> (operator ==)
unordered_set<Elem, Hash> An unordered set that by default hashes with Hash and compares equal_to<> (operator ==)
unordered_set<Elem, Hash, Cmp> An unordered set that by default hashes with Hash and compares with Cmp
unordered_multiset<Elem> An unordered multiset that by default hashes with hash<> and compares equal_to<> (operator ==)
unordered_multiset<Elem, Hash> An unordered multiset that by default hashes with Hash and compares equal_to<> (operator ==)
unordered_multiset<Elem, Hash, Cmp> An unordered multiset that by default hashes with Hash and compares with Cmp
unordered_map<Key, T> An unordered map that by default hashes with hash<> and compares equal_to<> (operator ==)
unordered_map<Key, T, Hash> An unordered map that by default hashes with Hash and compares equal_to<> (operator ==)
unordered_map<Key, T, Hash, Cmp> An unordered map that by default hashes with Hash and compares with Cmp
unordered_multimap<Key, T> An unordered multimap that by default hashes with hash<> and compares equal_to<> (operator ==)
unordered_multimap<Key, T, Hash> An unordered multimap that by default hashes with Hash and compares equal_to<> (operator ==)
unordered_multimap<Key, T, Hash, Cmp> An unordered multimap that by default hashes with Hash and compares with Cmp

Layout Operations

Operation Effect
c.hash_function() Returns the hash function
c.key_eq() Returns the equivalence predicate
c.bucket_count() Returns the current number of buckets
c.max_bucket_count() Returns the maximum number of buckets possible
c.load_factor() Returns the current load factor
c.max_load_factor() Returns the current maximum load factor
c.max_load_factor(val) Sets the maximum load factor to val
c.rehash(bnum) Rehashes the container so that it has a bucket size of at least bnum
c.reserve(num) Rehashes the container so that is has space for at least num elements (since C++11)

影响内部布局的操作。
rehash与reserve的比较：

1
2
coll.rehash(100);	//prepare for 100/max_load_factor() elements
coll.reserve(100);	//prepare for 100 elements (since C++11)

Nonmodifying Operations

Operation Effect
c.empty() Returns whether the container is empty (equivalent to size()==0 but might be faster)
c.size() Returns the current number of elements
c.max_size() Returns the maximum number of elements possible
c1 == c2 Returns whether c1 is equal to c2
c1 != c2 Returns whether c1 is not equal to c2 (equivalent to !(c1==c2) )

Special Search Operations

Operation Effect
c.count(val) Returns the number of elements with value val
c.find(val) Returns the position of the first element with value val (or end() if none found)
c.equal_range(val) Returns a range with all elements with a value equal to val (i.e., the first and last positions, where val would get inserted)

Assignments

Operation Effect
c = c2 Assigns all elements of c2 to c
c = rv Move assigns all elements of the rvalue rv to c (since C++11)
c = initlist Assigns all elements of the initializer list initlist to c (since C++11)
c1.swap(c2) Swaps the data of c1 and c2
swap(c1, c2) Swaps the data of c1 and c2

Iterator Operations

Operation Effect
c.begin() Returns a forward iterator for the first element
c.end() Returns a forward iterator for the position after the last element
c.cbegin() Returns a constant forward iterator for the first element (since C++11)
c.cend() Returns a constant forward iterator for the position after the last element (since C++11)
c.rbegin() Returns a reverse iterator for the first element of a reverse iteration
c.rend() Returns a reverse iterator for the position after the last element of a reverse iteration
c.crbegin() Returns a constant reverse iterator for the first element of a reverse iteration (since C++11)
c.crend() Returns a constant reverse iterator for the position after the last element of a reverse iteration (since C++11)

前向迭代器。

Insert and Remove Operations

Operation Effect
c.insert(val) Inserts a copy of val and returns the position of the new element and, for unordered containers, whether it succeeded
c.insert(pos, val) Inserts a copy of val and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
c.insert(beg, end) Inserts a copy of all elements of the range [beg,end) (returns nothing)
c.insert(initlist) Inserts a copy of all elements in the initializer list initlist (returns nothing; since C++11)
c.emplace(args…) Inserts a copy of an element initialized with args and returns the position of the new element and, for unordered containers, whether it succeeded (since C++11)
c.emplace_hint(pos, args…) Inserts a copy of an element initialized with args and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
c.erase(val) Removes all elements equal to val and returns the number of removed elements
c.erase(pos) Removes the element at iterator position pos and returns the following position (returned nothing before C++11)
c.erase(beg, end) Removes all elements of the range [beg,end) and returns the following position (returned nothing before C++11)
c.clear() Removes all elements (empties the container)

Unordered Sets

1
2
3
4
5
6
pair<iterator,bool>	insert(const value_type& val);
iterator		insert(iterator posHint, const value_type& val);
template <typename... Args>
pair<iterator,bool>	emplace(Args&&... args);
template <typename... Args>
iterator		emplace_hint(const_iterator posHint, Args&&... args);

Unordered multisets

1
2
3
4
5
6
iterator	insert(const value_type& val);
iterator	insert(iterator posHint, const value_type& val);
template <typename... Args>
iterator	emplace(Args&&... args);
template <typename... Args>
iterator	emplace_hint(const_iterator posHint, Args&&... args);

Direct Element Access of Unordered Maps

Operation Effect
c[key] Inserts an element with key, if it does not yet exist, and returns a reference to the value of the element with key (only for nonconstant unordered maps)
c.at(key) Returns a reference to the value of the element with key (since C++11)

使用Unordered容器的示例

Unordered Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <unordered_set>
#include <numeric>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int main()
{
	// create and initialize unordered set
	//unordered_set<int> coll = {1,2,3,5,7,11,13,17,19,77};
	int temp[10] = {1,2,3,5,7,11,13,17,19,77};
	unordered_set<int> coll(temp, temp+10);
	// print elements
	// - elements are in arbitrary order
	copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// insert some additional elements
	// - might cause rehashing and create different order
	//coll.insert({-7,17,33,-11,17,19,1,13});
	int temp1[8] = {-7,17,33,-11,17,19,1,13};
	coll.insert(temp1, temp1+8);
	copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// remove element with specific value
	coll.erase(33);
	// insert sum of all existing values
	coll.insert(accumulate(coll.begin(), coll.end(), 0));
	copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// check if value 19 is in the set
	if (coll.find(19) != coll.end())
	{
		cout << "19 is available" << endl;
	}
	// remove all negative values
	unordered_set<int>::iterator pos;
	for (pos = coll.begin(); pos != coll.end();)
	{
		if (*pos < 0)
		{
			pos = coll.erase(pos);
		}else
		{
			++pos;
		}
	}
	copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	system("Pause");
}

Unordered Multiset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <unordered_set>
#include <numeric>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int main()
{
	// create and initialize, expand, and print unordered multiset
	//unordered_multiset<int> coll = { 1,2,3,5,7,11,13,17,19,77 };
	int temp[10] = { 1,2,3,5,7,11,13,17,19,77 };
	unordered_multiset<int> coll(temp, temp+10);
	// coll.insert({-7,17,33,-11,17,19,1,13});
	int temp1[8] = {-7,17,33,-11,17,19,1,13};
	coll.insert(temp1, temp1+8);
	copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// remove all elements with specific value
	coll.erase(17);
	// remove one of the elements with specific value
	auto pos = coll.find(13);
	if (pos != coll.end())
	{
		coll.erase(pos);
	}
	copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	system("Pause");
}

[1] The C++ Standard Library 2nd Edition