C++开发必备：精通set与map容器，提升数据处理效率

C++开发必备：精通set与map容器，提升数据处理效率

引用

CSDN

1.

https://m.blog.csdn.net/2301_82213854/article/details/145560067

在C++的标准模板库（STL）中，容器是存储和管理数据的基础组件。set、multiset、map和multimap是四种非常重要的关联式容器，它们各自有不同的特点和应用场景。与序列式容器（如vector、list、deque等）不同，这些关联式容器存储的是键值对，使得数据的检索和操作更加高效。本文将从关联式容器、键值对、树形结构以及底层结构四个方面对这四种容器进行详细分析，帮助你更好地理解并运用这些强大的工具。

一、关联式容器：高效存储与检索

1.1 关联式容器的定义

在初阶阶段，我们已经接触过STL中的一些常用容器，如：vector、list、deque、forward_list(C++11)等，这些容器通常被归类为序列式容器。序列式容器的底层实现为线性序列的数据结构，存储的是元素本身（Key模型）。与之不同的是，关联式容器存储的是以<key, value>形式组织的键值对。这种容器能够提供更高效的查找、插入和删除操作，因为其通过key来直接定位到对应的value（KV模型）。

例如，如果你要创建一个字典，map就是一个理想选择，它可以通过提供的键（key）来快速检索到对应的值（value）。与顺序容器不同，关联容器具有更高的检索效率，特别是在处理大量数据时，性能优势十分明显。

二、键值对：关联式容器的核心结构

2.1 键值对的定义

关联式容器之所以能够高效工作，源于其底层使用了键值对的结构。在键值对中，key代表的是唯一标识符，而value表示与key对应的信息。这种一一对应的关系使得数据存储与检索变得更为高效。比如，当我们建立一个英汉互译字典时，字典中的每一个英文单词都是一个key，而与之对应的中文翻译就是value。

在SGI-STL（标准模板库）中，键值对的定义如下：

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    pair() : first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b) : first(a), second(b) {}
};

在此结构中，first表示key，second表示value。这种结构的设计非常灵活，可以适用于不同类型的key和value，例如可以存储int和string类型的键值对，也可以存储自定义类型的键值对。

三、树形结构的关联式容器：高效的底层实现

3.1 树形结构容器的介绍

根据应用场景的不同，STL实现了两种主要的关联式容器结构：树形结构和哈希结构。这里我们重点讨论树形结构的关联式容器，包括：map、set、multimap和multiset。

这些容器的共同点是它们都使用平衡二叉搜索树（通常为红黑树）作为底层数据结构。红黑树是一种自平衡的二叉查找树，它能确保在进行查找、插入和删除操作时，始终保持对数时间复杂度O(log n)。

3.1.1 set容器的实现

set容器按照一定次序存储元素，确保元素的唯一性和自动排序。在set中，元素的值即为其Key，并且每个值必须是唯一的。由于set采用红黑树实现，元素是按特定的排序准则（例如小于比较）进行排序的。

set的特点：

1. 元素按升序（默认）进行排序。
2. 元素值不可修改（元素为const类型）。
3. 在内部实现上，set存储的是<value, value>的键值对，即键和值是相同的。

1. set的构造函数

2. set的迭代器

3. set的容量

4. set的修改操作

set的使用示例：

#include <iostream>
#include <set>
void TestSet() {
    // 用数组array中的元素构造set
    int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    std::set<int> s(array, array + sizeof(array) / sizeof(array[0]));
    // 输出set中元素的个数
    std::cout << s.size() << std::endl;
    // 正向打印set中的元素，从打印结果中可以看出：set可去重
    for (auto& e : s) {
        std::cout << e << " ";
    }
    std::cout << std::endl;
    // 使用迭代器逆向打印set中的元素
    for (auto it = s.rbegin(); it != s.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    // set中值为3的元素出现了几次
    std::cout << s.count(3) << std::endl;
}

3.1.2 map容器的实现

map容器存储的是键值对（key, value），并根据key的顺序进行排序。与set不同，map存储的是真正的<key, value>，并且每个key是唯一的。

map的特点：

1. 存储key-value对。
2. key是唯一的，value可以重复。
3. 元素按照key进行排序。

2. map的构造

3. map的迭代器

4. map的容量与元素访问

备注：
在执行operator[]时，如果key不存在，操作会插入一个新的元素，返回该元素的value。如果key已存在，operator[]将返回该key的对应value。

5. map的修改操作

map的使用示例：

#include <iostream>
#include <string>
#include <map>
void TestMap() {
    map<string, string> m;
    // 向map中插入元素的方式：
    // 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
    m.insert(pair<string, string>("peach", "桃子"));
    // 将键值对<"banana","香蕉">插入map中，用make_pair函数来构造键值对
    m.insert(make_pair("banana", "香蕉"));
    // 借用operator[]向map中插入元素
    /*
    operator[]的原理是：
    用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
    如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
    如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
    operator[]函数最后将insert返回值键值对中的value返回
    */
    // 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果
    m["apple"] = "苹果";
    try {
        // 这里故意使用错误拼写，演示at操作抛出异常
        m.at("watermelon") = "水蜜桃";
    }
    catch (const out_of_range& e) {
        cout << "key不存在，at操作抛出异常" << endl;
    }
    cout << m.size() << endl;
    // 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
    for (auto& e : m) {
        cout << e.first << "--->" << e.second << endl;
    }
    cout << endl;
    // map中的键值对key一定是唯一的，如果key存在将插入失败
    auto ret = m.insert(make_pair("peach", "桃色"));
    if (ret.second) {
        cout << "<peach, 桃色>不在map中, 已经插入" << endl;
    }
    else {
        cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
            << ret.first->second << " 插入失败" << endl;
    }
    // 删除key为"apple"的元素
    m.erase("apple");
    if (1 == m.count("apple")) {
        cout << "apple还在" << endl;
    }
    else {
        cout << "apple被吃了" << endl;
    }
}

3.1.3 multiset与multimap的区别

与set和map不同，multiset和multimap允许存储重复的key。这意味着在multiset和multimap中，某个key可以出现多次。

multiset存储的是只有值的容器（与set类似），而multimap则存储key-value对（与map类似）。

multiset与multimap的特点：

1. multiset允许存储重复的元素，而set不允许。
2. multimap允许存储重复的key，而map不允许。

四、底层结构：红黑树与AVL树的应用

4.1 红黑树：平衡与效率

红黑树是set、map、multiset和multimap等容器的底层实现之一。红黑树是一种自平衡的二叉查找树，它通过颜色标记节点来保证树的平衡性。红黑树的关键特点是：每个节点或是红色，或是黑色，并且通过一系列规则保持平衡，以确保树的查找操作不会退化成链表。

4.1.1 AVL树与红黑树的比较

红黑树和AVL树都是平衡二叉查找树，它们的时间复杂度为O(log n)。然而，红黑树的平衡条件稍微放宽，因此比AVL树插入和删除时的性能更好。在需要频繁修改数据的场景中，红黑树通常表现更优。

五、总结：根据需求选择合适的容器

• set：适用于需要存储唯一且自动排序的元素的场景，如去重操作和排序。
• multiset：适用于存储允许重复的元素且需要自动排序的场景，如统计频率。
• map：适用于存储唯一的键值对，并根据key快速查找value的场景，如字典。
• multimap：适用于存储多个相同key的键值对，并且要求自动排序的场景，如多值映射。

通过了解这些容器的特点、实现方式以及应用场景，你可以在实际开发中做出更为合理的选择，提升程序的效率和可维护性。