C++ Primer 5th笔记（chap 11）关联容器

•map

•multimap

•set

•multiset

•set

•unordered_map

•unordered_set

•unordered_multimap

•unordered_multiset

优点	缺点	适用处
map	有序性，其元素的有序性在很多应用中都会简化很多的操作，内部实现一个红黑书使得map的很多操作在lgnlgn的时间复杂度下就可以实现，因此效率非常的高。	空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间 对于那些有顺序要求的问题，用map会更高效一些
unordered_map	内部实现了哈希表，因此其查找速度非常的快	哈希表的建立比较耗费时间 对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

关联容器有一些顺序容器不支持的操作

关联容器有类型别名

map<K, V>::key_type    //在map容器中，用作索引的键的类型
set<K>::key_type  

map<K, V>::mapped_type //在map容器中，键所关联的值的类型
map<K, V>::value_type //一个pair类型，它的first元素具有key_type类型，second元素具有mapped_type类型
           

1. map

map<string, size_t> word_count; // empty map from string to size_t
string word;
while (cin >> word)
	++word_count[word];

for (const auto& w : word_count)
	cout << w.first << " occurs " << w.second << " times" << endl;

// get an iterator positioned on the first element
auto map_it = word_count.cbegin();
// compare the current iterator to the off-the-end iterator
while (map_it != word_count.cend()) {
	// dereference the iterator to print the element key--value pairs
	cout << map_it->first << " occurs "
		<< map_it->second << " times" << endl;
	++map_it;  // increment the iterator to denote the next element
}
           

2. set

map<string, size_t> word_count; // empty map from string to size_t
set<string> exclude = {"The", "But"};

string word;
while (cin >> word)
	if(exclude.find(word) == exclude.end())
		++word_count[word];

for (const auto& w : word_count)
	cout << w.first << " occurs " << w.second << " times" << endl;

// get an iterator positioned on the first element
auto map_it = word_count.cbegin();
// compare the current iterator to the off-the-end iterator
while (map_it != word_count.cend()) {
	// dereference the iterator to print the element key--value pairs
	cout << map_it->first << " occurs "
		<< map_it->second << " times" << endl;
	++map_it;  // increment the iterator to denote the next element
}
           

• set 中的关键字也是const的。所以说用一个set 的迭代器来读取元素的值，但不能修改其值。

3.multiset mulimap

std::map<string, string> authors = { {"Joyce", "James"} };
std::map<string, string> word_count = authors;
std::multimap<string, string> word_count2(authors.cbegin(), authors.cend());
	 
std::set<string> exclude = { "the", "but" };
std::set<string> exclude1(exclude.cbegin(), exclude.cend());

std::multiset<string> exclude2(exclude.cbegin(), exclude.cend());
           

• map, multimap, set, and multiset 的关键字类型必须定义 比较元素的方法(默认使用 “<” 来比较)

class Sales_data {
public:
	Sales_data() {}

	bool operator < (const Sales_data& lhs)
	{
		return  true;
	}

	bool static compareIsbn(const Sales_data& lhs, const Sales_data& rhs)
	{
		return  true;
	}
};  
multiset<Sales_data, decltype(Sales_data::compareIsbn)*> bookstore(Sales_data::compareIsbn);
           

4.pair类型

• 键值对
• pair 的默认构造函数会 first 和 second 数据成员进行值初始化
• pair的数据成员是public

定义(构造函数)：

定义	说明
pair<T1, T2> p1;	创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化
pair<T1, T2> p1(v1, v2);	创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2
make_pair(v1, v2);	以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型
p1 < p2	创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2
p1 == p2	两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true
p1.first	返回对象p1中名为first的公有数据成员
p1.second	返回对象p1中名为second的公有数据成员