STL Map and Multimap

Container, Map, STL

Map and Multimap

Map and Multimap
Internal Structure of Maps and Multimaps

包含头文件<map>。
定义：

1
2
3
4
5
6
7
8
9
10
namespace std {
	template <	typename Key, typename T,
			typename Compare = less<Key>,
			typename Allocator = allocator<pair<const Key,T> > >
			class map;
	template <	typename Key, typename T,
			typename Compare = less<Key>,
			typename Allocator = allocator<pair<const Key,T> > >
			class multimap;
}

map容器的key和value必须是copyable且movable的。而且key必须可用排序标准进行比较。
排序标准的要求与set相同。
关联容器。一般用平衡二叉树实现。自动排序。查找一个已知key快，查找已知value慢。key是不可修改的，只能删了重加。可以修改非const类型的value值。

Map和Multimap容器的操作

Create, Copy, and Destroy

Operation Effect
map c Default constructor; creates an empty map/multimap without any elements
map c(op) Creates an empty map/multimap that uses op as the sorting criterion
map c(c2) Copy constructor; creates a copy of another map/multimap of the same type (all elements are copied)
map c = c2 Copy constructor; creates a copy of another map/multimap of the same type (all elements are copied)
map c(rv) Move constructor; creates a new map/multimap of the same type, taking the contents of the rvalue rv (since C++11)
map c = rv Move constructor; creates a new map/multimap of the same type, taking the contents of the rvalue rv (since C++11)
map c(beg, end) Creates a map/multimap initialized by the elements of the range [beg,end)
map c(beg, end, op) Creates a map/multimap with the sorting criterion op initialized by the elements of the range [beg,end)
map c(initlist) Creates a map/multimap initialized with the elements of initializer list initlist (since C++11)
map c = initlist Creates a map/multimap initialized with the elements of initializer list initlist (since C++11)
c.~map() Destroys all elements and frees the memory

其中，map可以是：

map Effect
map<Key, Val> A map that by default sorts keys with less<> (operator <)
map<Key, Val, Op> A map that by default sorts keys with Op
multimap<Key, Val> A multimap that by default sorts keys with less<> (operator <)
multimap<Key, Val, Op> A multimap that by default sorts keys with Op

Nonmodifying Operations

Operation Effect
c.key_comp() Returns the comparison criterion
c.value_comp() Returns the comparison criterion for values as a whole (an object that compares the key in a key/value pair)
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 (calls == for the elements)
c1 != c2 Returns whether c1 is not equal to c2 (equivalent to !(c1==c2) )
c1 < c2 Returns whether c1 is less than c2
c1 > c2 Returns whether c1 is greater than c2 (equivalent to c2<c1)
c1 <= c2 Returns whether c1 is less than or equal to c2 (equivalent to !(c2<c1) )
c1 >= c2 Returns whether c1 is greater than or equal to c2 (equivalent to !(c1<c2) )

比较只发生在相同类型之间，即key/value/sorting criterion都必须相同。
如果想比较不同排序类型的容器，需要用标准库里的比较函数。

Special Search Operations

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

用来查找key，而不是value。查找value要用标准库的find_if()(这个还需要一个把元素和某个值比较的函数物体)，或手动写一个循环。在循环里remove元素要小心迭代器失效。
用find_if

1
2
3
4
auto posVal = find_if(	coll.begin(),coll.end(),
			[] (const pair<float,float>& elem) {
				return elem.second == 3.0;
			});

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 Functions and Element Access

Operation Effect
c.begin() Returns a bidirectional iterator for the first element
c.end() Returns a bidirectional iterator for the position after the last element
c.cbegin() Returns a constant bidirectional iterator for the first element (since C++11)
c.cend() Returns a constant bidirectional 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)

双向迭代器。要想修改里面的元素，必须用这个容器自己提供的成员函数。因为key是const的，不能用标准库里的做修改的任何通用函数。
一个修改value的例子：

1
2
3
4
5
6
7
8
9
10
std::map<std::string,float> coll;
//add 10 to the value ofeach element:
std::for_each (	coll.begin(), coll.end(),
		[] (std::pair<const std::string,float>& elem) {
			elem.second += 10;
		});
// 其中std::pair<const std::string,float>还可以是：
// std::map<std::string,float>::value_type
// 或：
// decltype(coll)::value_type

Inserting and Removing Elements

Operation Effect
c.insert(val) Inserts a copy of val and returns the position of the new element and, for maps, 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 maps, 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)

C++11后删除同一value所有元素的例子：

1
2
3
4
5
6
7
8
9
std::map<std::string,float> coll;
for (auto pos = coll.begin(); pos != coll.end(); ) {
	if (pos->second == value) {
		pos = coll.erase(pos); //possible only since C++11
	}
	else {
		++pos;
	}
}

C++11前删除同一value所有元素的例子：

1
2
3
4
5
6
7
8
9
10
11
12
typedef std::map<std::string,float> StringFloatMap;
StringFloatMap coll;
StringFloatMap::iterator pos;
//remove all elements having a certain value
for (pos = coll.begin(); pos != coll.end(); ) {
	if (pos->second == value) {
		coll.erase(pos++);
	}
	else {
		++pos;
	}
}

Direct Element Access of 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 maps)
c.at(key) Returns a reference to the value of the element with key (since C++11)

使用Map和Multimap的示例

Using Algorithms and Lambdas with a Map/Multimap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	/*map<string, double> coll { {"tim", 9.9}, {"struppi", 11.77} };*/
	map<string, double> coll;
	coll.insert(make_pair("tim", 9.9));
	coll.insert(make_pair("struppi", 11.77));
	// square the value of each element:
	for_each(coll.begin(), coll.end(),
				[] (pair<const string, double>& elem)	{
					elem.second *= elem.second;
				});
	// print each element:
	for_each(coll.begin(), coll.end(),
			[] (const map<string, double>::value_type& elem) {
				cout << elem.first << ": " << elem.second << endl;
			});
	system("Pause");
}

Using a Map as an Associative Array

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
51
52
#include <map>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
	// create map/associateve array
	// - keys are strings
	// - values are floats
	typedef map<string, float> StringFloatMap;
	StringFloatMap stocks;	// create empty container
	// insert some elements
	stocks["BASF"] = 369.50;
	stocks["VW"] = 413.50;
	stocks["Daimler"] = 819.00;
	stocks["BMW"] = 834.00;
	stocks["Siemems"] = 842.20;
	// print all elements
	StringFloatMap::iterator pos;
	cout << left;	// left-adjust values
	for (pos = stocks.begin(); pos != stocks.end(); ++pos)
	{
		cout << "stock:	" << setw(12) << pos->first
			<< "price:	" << pos->second << endl;
	}
	cout << endl;
	// boom (all prices doubled)
	for (pos = stocks.begin(); pos != stocks.end(); ++pos)
	{
		pos->second *= 2;
	}
	// print all elements
	for (pos = stocks.begin(); pos != stocks.end(); ++pos)
	{
		cout << "stock:	" << setw(12) << pos->first
			<< "price:	" << pos->second << endl;
	}
	cout << endl;
	// rename key from "VM" to "Volkswagen"
	// - provided only by exchanging element
	stocks["Volkswagen"] = stocks["VW"];
	stocks.erase("VW");
	// print all elements
	for (pos = stocks.begin(); pos != stocks.end(); ++pos)
	{
		cout << "stock:	" << setw(12) << pos->first
			<< "price:	" << pos->second << endl;
	}
	cout << endl;
	system("Pause");
}

Sorting Criterion at Runtime

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <map>
#include <string>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cctype>
using namespace std;
// function object to compare strings
// - allows you to set the comparison criterion at runtime
// - allows you to compare case insensitive
class RuntimeStringCmp
{
public:
	// constants for the comparison criterion
	enum cmp_mode {normal, nocase};
private:
	// actual comparison mode
	const cmp_mode mode;
	// auxiliary function to compare case insensitive
	static bool nocase_compare (char c1, char c2)
	{
		return toupper(c1) < toupper(c2);
	}
public:
	// constructor: initializes the comparison criterion
	RuntimeStringCmp (cmp_mode m = normal) : mode(m) {}
	// the comparison
	bool operator() (const string& s1, const string& s2) const
	{
		if (mode == normal) {return s1 < s2;}
		else
		{
			return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), nocase_compare);
		}
	}
};
// container type:
// - map with
//	- string keys
//	- string values
//	- the special comparison object type
typedef map<string,string,RuntimeStringCmp> StringStringMap;
// function that fills and prints such containers
void fillAndPrint(StringStringMap& coll);
int main()
{
	// create a container with the default comparison criterion
	StringStringMap coll1;
	fillAndPrint(coll1);
	// create an object for case-insensitive comparisons
	RuntimeStringCmp ignorecase(RuntimeStringCmp::nocase);
	// create a container with the case-insensitive comparisons criterion
	StringStringMap coll2(ignorecase);
	fillAndPrint(coll2);
	system("Pause");
}
void fillAndPrint(StringStringMap& coll)
{
	// insert elements in random order
	coll["Deutschland"] = "Germany";
	coll["deutsch"] = "German";
	coll["Haken"] = "snag";
	coll["arbeiten"] = "work";
	coll["Hund"] = "dog";
	coll["gehen"] = "go";
	coll["Unternehmen"] = "enterprise";
	coll["unternehmen"] = "undertake";
	coll["gehen"] = "walk";
	coll["Bestatter"] = "undertaker";
	// print elements
	cout.setf(ios::left, ios::adjustfield);
	//for (const auto& elem : coll) {
	for (StringStringMap::iterator it = coll.begin(); it != coll.end(); ++it){
		const StringStringMap::value_type& elem = *it;
		cout << setw(15) << elem.first << " "
			<< elem.second << endl;
	}
	cout << endl;
}

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