c++ 关联容器

关联容器

关联容器按关键字来保存和访问元素，顺序容器是按它们在容器中得位置来顺序保存和访问。关联容器支持高效的关键字查找和访问。关联容器和顺序容器一样都是模板，需指定类型。关联容器的迭代器都是双向迭代器，顺序容器中除了forward_list外都是。

标准库有8个关联容器，容器间的不同体现在三个维度上：每个容器**（1）或是一个set，或是一个map**；（2）要求不重复的关键字，或者允许重复关键字；（3）按顺序保存元素，或无序保存。

关键字multi表示允许关键字重复，关键字unordered表示无序保存。map和multimap定义在头文件map中；set和multiset定义在头文件set中；无序容器定义在头文件unordered_map和unordered_set中。

使用map

根据用户输入，统计各个单词输入次数：

int main() 
{
	map<string, size_t> word_count; // string 到 size_t的空map
	string word;
	while (std::cin >> word)
		++word_count[word]; // 提取word的计数器并将其加1
	for (const auto& w : word_count) // 遍历，得到的是一个pair类型对象。
	{
		cout << w.first << " occurs " << w.second
			<< ((w.second > 1) ? " times" : " time") << endl;
	}
}

从map提取元素时，会得到一个pair类型的对象。pair是一个模板类型，保存两个名为first和second的数据成员。

使用set

扩展前一个项目，将常用单词忽略：

int main() 
{
	map<string, size_t> word_count; // string 到 size_t的空map
	set<string> exclude = { "The", "But", "And", "Or", "An", "A",
							"the", "but", "and", "or", "an", "a" };
	string word;
	while (std::cin >> word) 
	{
		// 统计不在exclude中的单词
		if (exclude.find(word) == exclude.end()) {
			++word_count[word];
		}
	}
	for (const auto& w : word_count) // 遍历
	{
		cout << w.first << " occurs " << w.second
			<< ((w.second > 1) ? " times" : " time") << endl;
	}
}

扩展，忽略首字母大小写以及标点符号：处理字母大小写常见做法是在存储前统一将其转为全大写或全小写，我采用转为小写；标点符号则直接删除，ispunct 是 C++ 标准库 <cctype> 中的一个函数，它用于检查字符是否是标点符号。

if (exclude.find(word) == exclude.end()) 
{
	// 转为小写
	for (auto& ch : word) ch = tolower(ch);
	// 删除标点
	word.erase(remove_if(word.begin(), word.end(), ispunct), word.end());

	++word_count[word];
}

multimap与multiset

map与set中关键字必须唯一，一个关键字只能有一个元素的关键字等于它。加上multi后则不同，可支持多个元素具有相同的关键字。

vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
	ivec.push_back(i);
	ivec.push_back(i);
}

set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());

cout << ivec.size() << endl;  // 20
cout << iset.size() << endl;  // 10
cout << miset.size() << endl; // 20

关键字类型的要求

关联类型对其关键字类型有一些限制。对于有序容器，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。集合类型中，关键字类型就是元素类型；映射类型中，关键字类型是元素的第一部分的类型。

若要提供自己定义的操作来代替关键字上的<运算符，所提供的操作必须在关键字类型上定义一个严格弱序（可看作“小于等于”）。

使用函数指针方式

class Book {
public:
	Book(string bn = ""):isbn(bn){}
	const string& getIsbn() const{
		return isbn;
	}
private:
	string isbn;
};

bool compareIsbn(const Book& b1, const Book& b2) {
	return b1.getIsbn() < b2.getIsbn();
}

int main() 
{
	vector<Book> bookVec = { Book("C3"), Book("C5"), Book("A3") };
	// 隐式，使用decltype获取函数类型，然后加*
	//multiset<Book, decltype(compareIsbn)*> books(compareIsbn);
	// 显式，直接使用函数指针， 注意尖括号中为类型，不可使用函数指针变量
	multiset<Book, bool (*)(const Book&, const Book&)> books(compareIsbn);

	for (const auto& book : bookVec) {
		books.insert(book);
	}
	cout << books.size() << endl; // 20	
	for (const auto& s : books) // 遍历
	{
		cout << s.getIsbn() << endl;
	}
}

使用重载<方式

class Student {
public:
	Student(string n = "", int a = 0):name(n), age(a){}
	bool operator < (const Student& s) const {
		return age < s.age;
	}
public:
	string name;
	int age;
};

int main() 
{
	vector<Student> stuVec = { Student("C", 3), Student("A", 5), Student("A", 4) };
	multiset<Student> students(stuVec.cbegin(), stuVec.cend());
	cout << students.size() << endl; 
	for (const auto& s : students) // 遍历
	{
		cout << s.name << ": " << s.age << endl;
	}
}

std::map 的键需要具备可比较的逻辑， std::list::iterator 并没有提供内置的 < 运算符。需提供比较函数，或比较器。

std::vector<int> vi;
mv.insert(std::pair<std::vector<int>::iterator, int>(vi.begin(), 0));

// but when using this one the compiler complained that
// error: no match for 'operator<' in '__x < __y'
std::list<int> li;
ml.insert(std::pair<std::list<int>::iterator, int>(li.begin(), 0));

pair

pair位于utility.h中，保存两个数据成员，类似容器，用于生成特定类型的模板。

// 初始化器
pair<string, string> author{ "James", "Joyce" };

创建pair的方法：

int main()
{
    std::vector<std::pair<std::string, int>> vec;
    std::string str;
    int i;
    while (std::cin >> str >> i)
        vec.push_back(std::pair<std::string, int>(str, i));
    // vec.push_back(std::make_pair(str, i));
    // vec.push_back({ str, i }); // 参数为一个pair
    // vec.emplace_back(str, i); // 参数为一个构造, 最简洁

    for (const auto& p : vec)
        std::cout << p.first << ":" << p.second << std::endl;
}

关联容器操作

set类型的key_type和value_type相同；set中保存的值就是关键字。map中元素是关键字-值对，每个元素是一个pair对象，由于元素关键字不能改变，pair的关键字部分是const。

set<string>::value_type v1; // v1为string
set<string>::key_type v2; // v2为string

map<string, int>::value_type v3; // v3为pair<const string, int>
map<string, int>::key_type v4; // v4为string
map<string, int>::mapped_type v5; // v5为int，只有map类型才定义了此类型

关联容器迭代器

解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值引用。map的value_type是一个pair，可以改变pair的值，但不能改变关键字成员的值。set类型定义了iterator和const_iterator类型，但是都只允许只读访问set中的元素。

添加元素

关联容器使用insert时，在插入已存在的元素对容器没有影响。

vector<int> ivec = { 2, 4, 6, 8, 2, 4, 6, 8 }; // ivec有8个元素
set<int> set2; // 空集合
set2.insert(ivec.begin(), ivec.end()); // 4个元素
set2.insert({1, 3, 5, 7, 1, 3, 5, 7}); // 8个元素

map<string, int> words;
words.insert({ "aaa", 1});  // 使用{}初始化pair， word包含1个元素
words.insert(std::make_pair("aaa2", 3 )); // 显式构造pair， word包含2个元素
words.insert(pair<string, int>("aaa", 7)); // 显式构造pair， word包含2个元素, aaa - 1， aaa2 - 3
words.insert(map<string, size_t>::value_type("aaa", 5)); // 显式构造pair， word包含2个元素, aaa - 1， aaa2 - 3

检测insert的返回值

insert(或emplace)返回的值依赖于容器类型和参数。返回一个pair，pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值，指出元素是插入成功还是已经存在于容器中。

使用insert重写单词计数程序，区别是可以配置初始值：

map<string, size_t> word_count; // 从string到size_t的空map
string word;
while (std::cin >> word) {
  // 插入一个元素，关键字等于word， 值为5；
  // 若word已在word_count中，insert什么也不做
  pair<map<string, size_t>::iterator, bool> ret = word_count.insert({ word, 5 });
  if (!ret.second) // word已在word_count中
      ++ret.first->second;
}

可以将上述流程简化为：

while (std::cin >> word) {
  ++word_count.insert({ word, 4 }).first->second;
}

ret 为pair
ret.first 是一个map迭代器，指向具有给定关键字的元素
ret.first-> 解引用此迭代器，提取map中的元素，元素也是一个pair
ret.first->second map中元素的值部分

multiset或multimap 添加元素

在允许关键字不唯一时，insert总会插入一个元素，因此，insert无须返回bool值。

multimap<string, string> authors;
// 插入第一个元素
authors.insert({"Barth, John", "Son-Weed Factor"});
// 插入第二个元素，与前一个关键字相同
authors.insert({"Barth, John", "Lost in the Funhouse"});

删除元素

删除关键字时，不重复关键字的容器，erase返回值总是0或1，在允许重复关键字的容器，删除元素数量可能大于1。

map的下标操作

set不支持下标，因为set中没有与关键字相关联的“值”。multimap或unordered_multimap也不能进行下标操作，因为可能有多个值与一个关联字相关联。

当使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到map中。

map下标操作的返回值

通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的。但map使用下标操作时，会获得一个mapped_type对象（每个关键字关联的类型）；解引用一个map迭代器时，会得到一个value_type对象。

同其他下标运算符相同，map下标运算符返回一个左值，所以可进行读写。

访问元素

find方法不会添加将查找的关键字插入到map中。

在multimap或multiset中查找元素

multimap<string, int> authors;
authors.insert({ "a", 1 });
authors.emplace("b", 1);
authors.emplace("c", 1);
 
multimap<string, string> authors2{
    { "a", "1" },
    { "b", "1" },
    { "c", "1" },
    { "b", "1" }
};

1、先查找总个数，然后加个迭代器定位到第一个元素

multimap<string, string> authors;
string search_item("Alain de Botton"); // 要查找的作者
auto entries = authors.count(search_item); // 总数量
auto iter = authors.find(search_item); // 此作者的第一本书
// 循环查找所有
while (entries) {
  cout << iter->second << endl; // 打印每个书名
  ++iter;
  --entries;
}

2、使用lower_bound和upper_bound

for (auto beg = authors.lower_bound(search_item),
 	end = authors.upper_bound(search_item);
 	beg != end;
 	++beg)
cout << beg->second << endl; // 打印

当lower_bound（第一次出现）和upper_bound（最后一次出现之后）返回相同的迭代器时，则给定的关键字不在容器中。当元素不存在时，迭代器都会指向一个不影响排序的关键字插入位置。

3、使用equal_range函数

for (auto pos = authors.equal_range(search_item);
    pos.first != pos.second;
    ++pos.first)
    cout << pos.first->second << endl;

与第二种没有本质区别。

下标运算符对比

1、下标操作符在重复赋值相同关键字时，会保留最后一次的记录。insert会保留第一次的记录。

2、只能在非const类型的map上使用下标操作符，因为可能会插入一个元素。所有某些场景下只能使用find