云栈社区»论坛 › 技术文档「 Note & Doc 」 › C++ STL容器详解与实战：从vector到unordered_map的选型指南 ...

发回帖发新帖

581 积分	0 好友	75 主题

发消息

C++ STL容器详解与实战：从vector到unordered_map的选型指南

发表于 5 天前 | 查看: 18| 回复: 0

在 C++ 编程中，标准模板库（STL）是一个强大的工具库。其中，STL 容器作为其核心部分，扮演着数据管理基石的角色。无论是开发游戏管理大量角色信息，还是处理金融数据进行存储与查询，STL 容器都提供了一种高效且便捷的数据组织方式，使我们无需重复实现底层数据结构。

STL 容器主要分为三大类：顺序容器、关联容器和无序（哈希）容器。每一类都基于不同的数据结构实现，拥有独特的特性，适用于解决特定的编程问题。

一、C++ STL 容器是什么？

STL，即标准模板库，是 C++ 标准库的重要组成部分，它提供了一系列泛型的数据结构和算法。STL 容器是用于存储和管理数据的类模板，其设计与 C/C++ 语言特性深度结合，极大地简化了编程中数据结构的实现。

STL 容器具有泛型性，可以存储任意类型的数据，从基本类型到自定义的类对象，这极大地提高了代码的复用性。例如，vector<int> 存储整数，而 vector<MyClass> 则可以存储自定义类对象的集合。

在性能方面，STL 容器经过了精心优化。不同的容器针对不同操作进行了权衡。例如，vector 基于动态数组，在内存中连续存储元素，因此随机访问效率极高（时间复杂度 O(1)）。而 list 基于双向链表，在任意位置插入和删除元素仅需修改指针（时间复杂度 O(1)），非常适合频繁修改的场景。

此外，容器提供了丰富易用的接口，如 push_back、erase、find 等，封装了底层操作的复杂性，让开发者能更专注于业务逻辑。

二、顺序容器：数据的线性舞台

顺序容器将元素按插入的线性顺序排列。它们就像是一列按序排队的演员，适用于存储任务列表或有序数据记录。

2.1 vector：动态数组的崛起

vector 是动态数组的典范。其底层实现确保了强大的随机访问能力，通过索引可以在常数时间 O(1) 内访问任何元素。例如，在存储学生成绩的 vector 中，可以快速查询任意学生的成绩。

然而，vector 在中间位置插入或删除元素时性能较差。因为需要移动后续的所有元素，时间复杂度为 O(n)。在尾部进行操作则效率很高，平均为 O(1)。

让我们通过一段代码感受 vector 的用法：

#include <iostream>
#include <vector>

int main() {
    // 创建一个 vector，用于存储整数
    std::vector<int> numbers;

    // 在 vector 尾部插入元素
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);

    // 遍历 vector 并输出元素
    std::cout << "vector 中的元素: ";
    for (size_t i = 0; i < numbers.size(); ++i) {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;

    // 随机访问 vector 中的元素
    std::cout << "访问第二个元素: " << numbers[1] << std::endl;

    // 在 vector 中间插入元素
    numbers.insert(numbers.begin() + 1, 99);
    std::cout << "插入元素后的 vector: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除 vector 中的元素
    numbers.erase(numbers.begin() + 2);
    std::cout << "删除元素后的 vector: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.2 list：链表的灵活之舞

list 实现了双向链表。每个节点包含数据及指向前后节点的指针。这种结构让其在任意位置的插入和删除操作都异常高效，时间复杂度为 O(1)，因为你只需修改相邻节点的指针。

但 list 不支持随机访问。要访问第 n 个元素，必须从头部或尾部开始遍历，时间复杂度为 O(n)。

下面是一段操作 list 的代码：

#include <iostream>
#include <list>

int main() {
    // 创建一个 list，用于存储整数
    std::list<int> numbers;

    // 在 list 尾部插入元素
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);

    // 遍历 list 并输出元素
    std::cout << "list 中的元素: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 在 list 头部插入元素
    numbers.push_front(99);
    std::cout << "在头部插入元素后的 list: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除 list 中的元素
    numbers.erase(std::next(numbers.begin()));
    std::cout << "删除元素后的 list: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.3 deque：双端队列的平衡之道

deque，即双端队列，它融合了 vector 和 list 的部分优点。它支持像 vector 一样的随机访问，同时又在两端（头部和尾部）提供了像 list 一样高效的插入和删除操作（时间复杂度 O(1)）。这使其成为实现任务队列或缓存的理想选择。

#include <iostream>
#include <deque>

int main() {
    // 创建一个 deque，用于存储整数
    std::deque<int> numbers;

    // 在 deque 尾部插入元素
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);

    // 在 deque 头部插入元素
    numbers.push_front(99);

    // 遍历 deque 并输出元素
    std::cout << "deque 中的元素: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 随机访问 deque 中的元素
    std::cout << "访问第二个元素: " << numbers[1] << std::endl;

    // 删除 deque 头部的元素
    numbers.pop_front();
    std::cout << "删除头部元素后的 deque: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除 deque 尾部的元素
    numbers.pop_back();
    std::cout << "删除尾部元素后的 deque: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.4 array：静态数组的稳健步伐

array 是 STL 中的静态数组，其大小在编译时确定，不可改变。相比传统的 C 风格数组，它更安全，提供了 size() 成员函数和带边界检查的 at() 访问方法。

#include <iostream>
#include <array>

int main() {
    // 创建一个 array，用于存储 5 个整数
    std::array<int, 5> numbers = {1, 2, 3, 4, 5};

    // 遍历 array 并输出元素
    std::cout << "array 中的元素: ";
    for (size_t i = 0; i < numbers.size(); ++i) {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;

    // 访问 array 中的元素
    std::cout << "访问第三个元素: " << numbers.at(2) << std::endl;

    return 0;
}

2.5 forward_list：单向链表的轻量前行

forward_list 实现了单向链表。每个节点只包含数据和指向下一个节点的指针，因此比 list 更节省内存。它支持高效的头部插入和删除（O(1)），但只支持单向遍历，且不支持随机访问。

#include <iostream>
#include <forward_list>

int main() {
    // 创建一个 forward_list，用于存储整数
    std::forward_list<int> numbers;

    // 在 forward_list 头部插入元素
    numbers.push_front(1);
    numbers.push_front(2);
    numbers.push_front(3);

    // 遍历 forward_list 并输出元素
    std::cout << "forward_list 中的元素: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除 forward_list 中的元素
    numbers.pop_front();
    std::cout << "删除元素后的 forward_list: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.6 string：字符的有序集合

string 本质上也是一个顺序容器，用于存储字符序列。它的大小可动态调整，并提供了丰富的字符串操作函数，如 append, substr, find 等。

#include <iostream>
#include <string>

int main() {
    // 创建一个 string 对象
    std::string str = "Hello";

    // 追加字符串
    str.append(" World");
    std::cout << "追加后的字符串: " << str << std::endl;

    // 获取子字符串
    std::string sub = str.substr(0, 5);
    std::cout << "子字符串: " << sub << std::endl;

    // 查找子字符串
    size_t pos = str.find("World");
    if (pos != std::string::npos) {
        std::cout << "找到了子字符串，位置是: " << pos << std::endl;
    } else {
        std::cout << "未找到子字符串" << std::endl;
    }

    return 0;
}

三、关联容器：键值对的有序世界

关联容器存储键值对，并按键（Key）自动排序（通常是升序）。其查找、插入和删除操作的平均时间复杂度为 O(log n)，基于红黑树实现。理解其底层有助于我们分析算法时间复杂度。

3.1 set：有序集合的纯净之境

set 存储唯一且自动排序的元素。你不能直接修改 set 中的元素值，因为这会破坏顺序。如需修改，必须先删除再插入新元素。

#include <iostream>
#include <set>

int main() {
    // 创建一个 set，用于存储整数
    std::set<int> numbers;

    // 插入元素
    numbers.insert(3);
    numbers.insert(1);
    numbers.insert(4);
    numbers.insert(1); // 重复元素，不会被插入
    numbers.insert(5);

    // 遍历 set 并输出元素
    std::cout << "set 中的元素: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = numbers.find(4);
    if (it != numbers.end()) {
        std::cout << "找到了元素 4" << std::endl;
    } else {
        std::cout << "未找到元素 4" << std::endl;
    }

    // 删除元素
    numbers.erase(3);
    std::cout << "删除元素 3 后的 set: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.2 multiset：允许重复的有序集合

multiset 与 set 类似，但允许存储重复的元素。它适用于需要统计频率并保持顺序的场景。

#include <iostream>
#include <set>

int main() {
    // 创建一个 multiset，用于存储整数
    std::multiset<int> numbers;

    // 插入元素
    numbers.insert(3);
    numbers.insert(1);
    numbers.insert(4);
    numbers.insert(1); // 重复元素，会被插入
    numbers.insert(5);

    // 遍历 multiset 并输出元素
    std::cout << "multiset 中的元素: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 统计元素 1 出现的次数
    int count = numbers.count(1);
    std::cout << "元素 1 出现的次数: " << count << std::endl;

    return 0;
}

3.3 map：有序键值对的映射之桥

map 存储唯一的键及其关联的值，并按键排序。你可以使用 operator[] 通过键快速访问值（如果键不存在，则会插入一个具有默认值的键值对）。

#include <iostream>
#include <map>
#include <string>

int main() {
    // 创建一个 map，用于存储学生学号和成绩的映射关系
    std::map<int, int> studentScores;

    // 插入键值对
    studentScores[1] = 90;
    studentScores[2] = 85;
    studentScores[3] = 95;

    // 遍历 map 并输出键值对
    std::cout << "学生学号和成绩的映射关系: " << std::endl;
    for (auto pair : studentScores) {
        std::cout << "学号: " << pair.first << ", 成绩: " << pair.second << std::endl;
    }

    // 通过键查找值
    int score = studentScores[2];
    std::cout << "学号为 2 的学生成绩: " << score << std::endl;

    return 0;
}

3.4 multimap：重复键的有序映射

multimap 允许键重复，适用于一个键对应多个值的场景。

#include <iostream>
#include <map>
#include <string>

int main() {
    // 创建一个 multimap，用于存储学生姓名和年龄的映射关系
    std::multimap<std::string, int> studentAges;

    // 插入键值对
    studentAges.insert({"Alice", 20});
    studentAges.insert({"Bob", 21});
    studentAges.insert({"Alice", 22}); // 键重复，会被插入

    // 遍历 multimap 并输出键值对
    std::cout << "学生姓名和年龄的映射关系: " << std::endl;
    for (auto pair : studentAges) {
        std::cout << "姓名: " << pair.first << ", 年龄: " << pair.second << std::endl;
    }

    return 0;
}

四、无序容器（哈希容器）：哈希表的无序传奇

无序容器基于哈希表实现，元素的存储位置由其键的哈希值决定。在平均情况下，其查找、插入和删除操作的时间复杂度为 O(1)，但在最坏情况（哈希冲突严重）下会退化到 O(n)。

4.1 unordered_set：哈希表的无序集合

unordered_set 存储唯一元素，但不保持任何顺序。其性能在平均情况下非常出色。

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个 unordered_set，用于存储整数
    std::unordered_set<int> numbers;

    // 插入元素
    numbers.insert(3);
    numbers.insert(1);
    numbers.insert(4);
    numbers.insert(1); // 重复元素，不会被插入
    numbers.insert(5);

    // 遍历 unordered_set 并输出元素
    std::cout << "unordered_set 中的元素: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = numbers.find(4);
    if (it != numbers.end()) {
        std::cout << "找到了元素 4" << std::endl;
    } else {
        std::cout << "未找到元素 4" << std::endl;
    }

    // 删除元素
    numbers.erase(3);
    std::cout << "删除元素 3 后的 unordered_set: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

4.2 unordered_multiset：允许重复的无序集合

unordered_multiset 允许元素重复。

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个 unordered_multiset，用于存储整数
    std::unordered_multiset<int> numbers;

    // 插入元素
    numbers.insert(3);
    numbers.insert(1);
    numbers.insert(4);
    numbers.insert(1); // 重复元素，会被插入
    numbers.insert(5);

    // 遍历 unordered_multiset 并输出元素
    std::cout << "unordered_multiset 中的元素: ";
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 统计元素 1 出现的次数
    int count = numbers.count(1);
    std::cout << "元素 1 出现的次数: " << count << std::endl;

    return 0;
}

4.3 unordered_map：哈希表的无序键值对映射

unordered_map 存储唯一的键及其关联的值，顺序不确定。

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 创建一个 unordered_map，用于存储单词和定义的映射关系
    std::unordered_map<std::string, std::string> wordDefinitions;

    // 插入键值对
    wordDefinitions["apple"] = "A round fruit with red or green skin and a white inside.";
    wordDefinitions["banana"] = "A long, curved fruit with yellow skin.";

    // 遍历 unordered_map 并输出键值对
    std::cout << "单词和定义的映射关系: " << std::endl;
    for (auto pair : wordDefinitions) {
        std::cout << "单词: " << pair.first << ", 定义: " << pair.second << std::endl;
    }

    // 通过键查找值
    std::string definition = wordDefinitions["apple"];
    std::cout << "单词 apple 的定义: " << definition << std::endl;

    return 0;
}

4.4 unordered_multimap：重复键的无序映射

unordered_multimap 允许键重复。

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 创建一个 unordered_multimap，用于存储人名和电话号码的映射关系
    std::unordered_multimap<std::string, std::string> phoneNumbers;

    // 插入键值对
    phoneNumbers.insert({"Alice", "123-456-7890"});
    phoneNumbers.insert({"Bob", "234-567-8901"});
    phoneNumbers.insert({"Alice", "345-678-9012"}); // 键重复，会被插入

    // 遍历 unordered_multimap 并输出键值对
    std::cout << "人名和电话号码的映射关系: " << std::endl;
    for (auto pair : phoneNumbers) {
        std::cout << "人名: " << pair.first << ", 电话号码: " << pair.second << std::endl;
    }

    return 0;
}

五、STL 容器使用技巧与注意事项

5.1 容器选择技巧

选择容器时应基于具体场景：

频繁随机访问：首选 vector 或 deque（时间复杂度 O(1)）。
频繁在两端插入/删除：选择 deque（O(1)）。
频繁在任意位置插入/删除：选择 list（O(1)），但牺牲随机访问。
需要元素有序且唯一：选择 set（O(log n)）。
需要元素有序，允许重复：选择 multiset。
需要快速查找键值对，不关心顺序：首选 unordered_map 或 unordered_set（平均 O(1)）。

5.2 内存管理注意事项

以 vector 为例，其动态扩容会带来性能开销。如果预先知道元素的大致数量，应使用 reserve() 方法预分配内存，避免多次重新分配和复制。

当容器存储大型对象时，考虑使用智能指针（如 std::unique_ptr）来管理，避免昂贵的拷贝操作，优化内存管理。

5.3 迭代器使用注意点

迭代器失效是常见问题：

vector/deque：插入（非尾部）或删除操作可能导致插入点/删除点之后的迭代器失效。特别是 vector 扩容会导致所有迭代器失效。
list/forward_list：插入操作不会使任何迭代器失效；删除操作仅使指向被删除元素的迭代器失效。
关联容器 (set, map等)：插入不会使迭代器失效；删除仅使指向被删除元素的迭代器失效。

安全做法：在遍历中删除元素时，使用 erase 返回的迭代器进行更新，或使用 std::remove_if 等算法。

掌握这些核心容器的特性和适用场景，能帮助你在 C++ 项目中做出更优的数据结构选择，编写出高效、健壮的代码。如果你想深入探讨更多 C++ 编程技巧或与其他开发者交流，欢迎访问云栈社区分享你的见解。

上一篇：2018款MacBook Pro电池更换体验：意外获得M4 Max顶配新机
下一篇：Go编程避坑指南：开发中必须掌握的10个核心细节与最佳实践

C＋＋, STL, 容器, 数据结构, 编程优化