map, set, multimap, multiset, unordered_map, unordered_set…

概述

关联容器可以分为两大类：有序关联容器和无序关联容器。

有序关联容器

有序关联容器中的元素是按关键字以特定顺序排列的，包括：

• map
• set
• multimap 关键字可以重复出现
• multiset 关键字可以重复出现

无序关联容器

无序关联容器中的元素没有特定顺序，包括：

• unordered_map
• unordered_set
• unordered_multimap 关键字可以重复出现
• unordered_multiset 关键字可以重复出现

无序容器通过哈希函数来确定元素的位置，因此它们的查找速度通常比有序容器快，但不支持按顺序遍历。

初始化

有序关联容器

列表初始化：

1
2
3
4
5

std::map<std::string, int> stuId = {
    {"Alice", 1001},
    {"Bob", 1002},
    {"Charlie", 1003}
};

迭代器初始化：

1
2
3
4
5
6
7
8
9

std::vector<std::pair<std::string, int>> vec = {
    {"Alice", 1001},
    {"Bob", 1002},
    {"Charlie", 1003}
};
std::map<std::string, int> stuId(vec.begin(), vec.end());

std::vector<int> vec = {1, 2, 3};
std::set<int> mySet(vec.begin(), vec.end());

有序容器中，其关键字类型必须是 严格弱序 的（视为小于等于）。STL 中对内置类型的有序容器实现已经满足了严格弱序的要求，加入我们要实现自定义类的有序容器，需要保证我们的 “比较函数”满足严格弱序的要求：

• a ≤ b 且 b ≤ a 不可能同时为真
• a ≤ b 且 b ≤ c，则 a ≤ c
• 若 !(a ≤ b) 且 !(b ≤ a)，则 a 和 b 是等价的（即 a == b）

无序关联容器

对于自定义的无序关联容器，需要提供一个哈希函数和一个比较函数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class MyClass;

struct MyHash {
    std::size_t operator()(const MyClass& obj) const {
        // 实现哈希函数
        return std::hash<int>()(obj.id); // 假设 MyClass 有一个 id 成员
    }
};

struct MyEqual {
    bool operator()(const MyClass& lhs, const MyClass& rhs) const {
        // 实现比较函数
        return lhs.id == rhs.id; // 假设 MyClass 有一个 id 成员
    }
};

std::unordered_map<MyClass, int, MyHash, MyEqual> myMap;

pair 类型

pair 是一个模板类，用于存储两个值的组合。它通常用于关联容器中存储键值对。

set 容器的迭代器是只读的，不能修改元素的值：

1
2
3
4
5
6
7
8

std::set<int> mySet = {1, 2, 3};
auto it = mySet.begin();

for (it; it != mySet.end(); ++it) {
    // *it 是只读的，不能修改
    std::cout << *it << " ";
    *it = 10; // 错误，不能修改 set 中的元素
}

遍历

迭代器

迭代器是关联容器的主要遍历方式。可以使用 begin() 和 end() 方法获取迭代器。

1
2
3
4
5
6
7
8
9

std::map<std::string, int> stuId = {
    {"Alice", 1001},
    {"Bob", 1002},
    {"Charlie", 1003}
};

for (auto it = stuId.begin(); it != stuId.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

范围 for 循环

范围 for 循环是 C++11 引入的语法糖，可以更简洁地遍历容器。

1
2
3

for (const auto& pair : stuId) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

map 和 unordered_map 的下标访问

对于 map 和 unordered_map，可以使用下标操作符 [] 访问元素。

1
2
3
4
5
6
7

std::map<std::string, int> stuId = {
    {"Alice", 1001},
    {"Bob", 1002},
    {"Charlie", 1003}
};

std::cout << "Alice's ID: " << stuId["Alice"] << std::endl;

对一个不在容器中的元素使用 [] 进行下标访问会自动插入一个默认值。

1

std::cout << "David's ID: " << stuId["David"] << std::endl;

使用 .at() 函数可以避免这种情况，它会在访问不存在的元素时抛出异常。

1
2
3

std::cout << "David's ID: " << stuId.at("David") << std::endl; // 抛出异常

// out_of_range: key not found

查找

对于map容器，如果不想在访问时自动插入默认值，可以使用 find() 方法。

删除

使用 erase() 方法删除元素。

关联容器设计的术语表

• 关联容器（associative container） 通过关键字以及比较函数来存储和访问元素的容器。
• 有序关联容器（ordered associative container） 元素按关键字的顺序排列。
• 无序关联容器（unordered associative container） 关键字没有特定顺序，依赖哈希函数来存储和访问元素
• key_type 关联容器中的关键字类型。对于 map，它是关键字的类型；对于 set，其 key_type 和 value_type 相同。
• mapped_type 关联容器中关键字的值的类型。
• value_type 关联容器中存储的值的类型。对于 map，它是 std::pair<const key_type, mapped_type>, pair.first 是 const key_type，pair.second 是 mapped_type；对于 set，它是 key_type（和value_type相同）。
• map 有序关联容器的类模板，需要用 关键字类型 和 值类型 来实例化。解引用 map 的迭代器得到的是 std::pair<const key_type, mapped_type> 类型的对象。注意：
  • map 的关键字类型是 const 的，不能修改
  • map 的迭代器是双向迭代器，可以前后移动
• set 有序关联容器的类模板，存储唯一的关键字。解引用 set 的迭代器得到的是 const key_type 类型的对象。
• multimap 和 multiset: 有序关联容器的类模板，允许关键字重复。
• unordered_map 无序关联容器的类模板，存储唯一的关键字和对应的值。解引用 unordered_map 的迭代器得到的是 std::pair<const key_type, mapped_type> 类型的对象。
• unordered_set 无序关联容器的类模板，存储唯一的关键字。解引用 unordered_set 的迭代器得到的是 const key_type 类型的对象。
• unordered_multimap 和 unordered_multiset 无序关联容器的类模板，允许关键字重复。
• pair 是一个模板类，用于存储两个值的组合，通常用于关联容器中存储键值对。其包含两个公有成员变量 first 和 second。
• [ ] 下标操作符只能用于访问 map 和 unordered_map 容器的非 const 对象。它接受一个 key_type 类型的值作为参数，并返回对应的 mapped_type 类型的值。注意：如果关键字不存在，则会自动插入一个默认值（自动进行值初始化）。