Associative Container

按照关键字来保存和访问。map 和 set。

  • map: 键值对
  • set: 集合，高效查询操作

标准库提供8个关联容器：1. set或map; 2. 要求不重复的关键字，或者允许重复; 3. 按顺序保存元素或无序保存

1
[unordered_][multi][map|set]

使用关联容器

multi_map

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
#include <iostream>
#include <map>
#include <string>

int main() {
    // 创建一个multimap，键为int类型，值为string类型
    std::multimap<int, std::string> mm;

    // 插入元素
    mm.insert({1, "apple"});
    mm.insert({2, "banana"});
    mm.insert({1, "apricot"});  // 插入重复键
    mm.insert({3, "cherry"});
    mm.insert({2, "blueberry"}); // 插入重复键

    // 遍历multimap
    std::cout << "所有元素：" << std::endl;
    for (const auto& pair : mm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找特定键的所有值
    int key = 2;
    std::cout << "\n键为 " << key << " 的所有值：" << std::endl;
    
    // 使用equal_range查找特定键的范围
    auto range = mm.equal_range(key);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl;
    }

    // 计算特定键的出现次数
    std::cout << "\n键为 " << key << " 的元素数量：" 
              << mm.count(key) << std::endl;

    // 删除特定键的所有元素
    mm.erase(key);
    std::cout << "\n删除键 " << key << " 后剩余元素：" << std::endl;
    for (const auto& pair : mm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

pair<T1, T2> name = {v1, v2}

map / multimap的key的数据类型：

  1. 基本数据类型
  2. 自定义类型：必须定义比较规则 <, 自定义比较器（结构体）

关联容器操作

  • key_type: 关键字类型
  • mapped_type: 每个关键字关联的类型，只适用map
  • value_type: for set, == key_type; for map, pair<const key_type, mapped_type>

迭代器：解引用得到value_type；set的迭代器为const

实际中，对一个关联容器使用算法，要么作为一个源序列，要么作为一个目的位置。

添加元素

insert, emplace(args): 插入一个存在的元素无影响, 返回pair，包含迭代器指向关键字的元素，以及一个指示是否插入成功的bool。对于multiset, multimap，总会插入成功，返回迭代器。

删除元素

erase(k): 删除关键字为k的元素

erase(p): 删除迭代器p指定的元素，p必须指向c中一个真实元素，不能等于c.end()。

erase(b, e): 删除迭代器对b和e所表示的范围中的元素，返回e

下标操作

map和unordered_map容器提供了下标运算符和一个对应的at函数

访问元素

find or count
对map使用find代替下标操作。如果下标运算符不在map中，会插入一个具有给定关键字的元素。

无序容器

新标准定义了四个无序关联容器，不使用比较运算符组织元素，使用一个哈希函数和关键字类型的==运算符。

默认情况下，无序容器使用关键字类型的==运算符来比较元素，还使用hash类型的对象来生成每个元素的哈希值。内置类型，string和智能指针具有hash模版。自定义类需要定义hash函数和==运算符的函数。

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
#include <iostream>
#include <string>
#include <unordered_set>
#include <functional>

// 自定义类：表示学生信息
class Student {
private:
    std::string name;  // 姓名
    int id;            // 学号（唯一标识）

public:
    // 构造函数
    Student(std::string n, int i) : name(n), id(i) {}

    // 获取成员变量的方法
    // const表示函数不会修改类的任何成员变量，也不能调用非const的成员函数。
    std::string get_name() const { return name; }
    int get_id() const { return id; }

    // 1. 重载==运算符：用于判断两个Student对象是否相等
    // 这里规定：学号相同则认为两个学生是同一个人
    bool operator==(const Student& other) const {
        return this->id == other.id;
    }
};

// 2. 为Student类定义哈希函数
// 需要在std命名空间中特化hash模板
namespace std {
    template<> struct hash<Student> {
        // 哈希函数 operator()：计算Student对象的哈希值
        size_t operator()(const Student& s) const {
            // 结合学号和姓名的哈希值（这里主要以学号为主）
            size_t id_hash = hash<int>()(s.get_id());
            size_t name_hash = hash<string>()(s.get_name());

            // 混合两个哈希值（简单的异或操作）
            return id_hash ^ (name_hash << 1);
        }
    };
}

int main() {
    // 使用unordered_set存储Student对象
    std::unordered_set<Student> students;

    // 添加学生对象
    students.insert(Student("Alice", 1001));
    students.insert(Student("Bob", 1002));
    students.insert(Student("Charlie", 1003));
    students.insert(Student("Alice", 1001));  // 学号相同，视为同一个对象，不会被重复插入

    // 遍历输出所有学生
    std::cout << "所有学生：" << std::endl;
    for (const auto& s : students) {
        std::cout << "学号：" << s.get_id() << "，姓名：" << s.get_name() << std::endl;
    }

    // 查找学生
    Student target("David", 1002);  // 姓名不同但学号相同，会被认为是同一个人
    auto it = students.find(target);
    if (it != students.end()) {
        std::cout << "\n找到学生：学号=" << it->get_id() << "，姓名=" << it->get_name() << std::endl;
    } else {
        std::cout << "\n未找到学生" << std::endl;
    }

    return 0;
}