前言：C++标准库中常用的容器有vector、list、map与set，分别属于序列容器（vector与list）和关联容器（map与set）。本文从底层实现原理、特性、使用场景等几方面进行解读。

目录

一、序列容器vector（动态数组）

1）底层实现

2）特性

3）适用场景

二、序列容器list（双向链表）

1）底层实现

2）特性

3）适用场景

三、关联容器map（键值对）

1）底层实现

2）特性

3）扩展：unordered_map

4）适用场景

四、关联容器set（有序唯一集合）

1）底层实现

2）特性

3）扩展：unordered_set

4）适用场景

五、详细示例

1）vector

2）list

3）map

4）set

---

一、序列容器vector（动态数组）

1）底层实现

Vector封装了数组，它是基于连续内存的动态数组，容量不足时，自动扩容（通常扩容为原容量的1.5-2倍，扩容需要重新分配内存并拷贝元素）。

2）特性

• 访问性能：支持随机访问，支持[]运算符，访问时间复杂度O(1)
• 增删操作：元素增删，尾部增删（push_back()，pop_back()），中间增删需移动元素，时间复杂度相应增大(O(n))
• 内存性能：如需扩容，则开销较大（需要重新分配内存并进行元素拷贝）

3）适用场景

需频繁随机访问、尾部增删为主的场景（如快速查询）。

二、序列容器list（双向链表）

1）底层实现

List封装了链表，基于双向链表实现，每个节点包括数据域和前驱/后继指针，各节点分散存储。

2）特性

• 访问性能：仅支持顺序访问，随机访问需遍历，时间复杂度O(n)
• 增删操作：可在任意位置增删，时间复杂度O(1)
• 内存性能：无扩容开销，但节点需额外存储指针，增大了内存开销

3）适用场景

需频繁任意位置增删元素、对访问效率要求不高的场景。

三、关联容器map（键值对）

1）底层实现

基于自平衡的二叉树（红黑树），键值对按照键的升序排序存储。

2）特性

• 存储结构：每个元素pair<const Key，Value>形式，键唯一且不可修改，值可修改
• 增删查找：按键访问，时间复杂度为O(log(n))
• 有序性：元素按键的升序自动排序，支持范围遍历

3）扩展：unordered_map

unordered_map基于哈希表实现，键无序，增删查找时间复杂度O(1)

4）适用场景

需要键值对映射、需要按键快速查找的场景

四、关联容器set（有序唯一集合）

1）底层实现

基于红黑树实现，存储唯一的键，无值（或 键即值）

2）特性

• 存储结构：元素为键本身，且键唯一 不可修改
• 增删查找：时间复杂度O(log(n))
• 有序性：元素自动按照键的升序排列，支持范围查询

3）扩展：unordered_set

基于哈希表实现，元素无序，其唯一性由哈希值保证。

4）适用场景

需要存储唯一元素、有序遍历的场景。

五、详细示例

1）vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 初始化vector
    vector<int> vec = {1, 2, 3, 4, 5};

    // 尾部插入元素
    vec.push_back(6);
    vec.emplace_back(7); // 更高效的构造插入

    // 遍历方式1：下标
    cout << "下标遍历: ";
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i] << " ";
    }
    cout << endl;

    // 遍历方式2：迭代器
    cout << "迭代器遍历: ";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 遍历方式3：范围for
    cout << "范围for遍历: ";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    // 插入元素（中间位置）
    vec.insert(vec.begin() + 2, 10); // 在索引2处插入10

    // 删除元素（尾部）
    vec.pop_back();

    // 删除元素（指定位置）
    vec.erase(vec.begin() + 3);

    // 清空vector
    // vec.clear();

    cout << "修改后vector: ";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

2）list

#include <iostream>
#include <list>
using namespace std;

int main() {
    // 初始化list
    list<int> lst = {10, 20, 30, 40};

    // 头部/尾部插入
    lst.push_front(5);
    lst.push_back(45);

    // 中间插入
    auto it = lst.begin();
    advance(it, 2); // 移动迭代器到第3个元素位置
    lst.insert(it, 15);

    // 遍历
    cout << "list遍历: ";
    for (int num : lst) {
        cout << num << " ";
    }
    cout << endl;

    // 删除元素
    lst.pop_front(); // 删除头部
    lst.erase(it);   // 删除指定位置（需注意迭代器有效性）

    // 排序
    lst.sort();

    cout << "排序后list: ";
    for (int num : lst) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

3）map

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    // 初始化map（键值对：string -> int）
    map<string, int> mp = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 95}};

    // 插入元素
    mp["David"] = 88;
    mp.emplace("Eve", 92); // 更高效

    // 遍历
    cout << "map遍历: " << endl;
    for (auto& pair : mp) {
        cout << pair.first << ": " << pair.second << endl;
    }

    // 查找元素
    string key = "Bob";
    auto it = mp.find(key);
    if (it != mp.end()) {
        cout << key << "的分数: " << it->second << endl;
    } else {
        cout << key << "不存在" << endl;
    }

    // 修改值
    mp["Alice"] = 95;

    // 删除元素
    mp.erase("Charlie");

    cout << "修改后map: " << endl;
    for (auto& pair : mp) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

4）set

#include <iostream>
#include <set>
using namespace std;

int main() {
    // 初始化set（自动去重+排序）
    set<int> st = {5, 2, 8, 2, 10, 5};

    // 插入元素
    st.insert(3);
    st.emplace(7);

    // 遍历
    cout << "set遍历: ";
    for (int num : st) {
        cout << num << " ";
    }
    cout << endl;

    // 查找元素
    int target = 8;
    if (st.count(target)) { // count返回0或1
        cout << target << "存在于set中" << endl;
    }

    // 删除元素
    st.erase(2);

    // 清空set
    // st.clear();

    cout << "修改后set: ";
    for (int num : st) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

写在后面：上述代码中，提到了emplace与emplace_back，是C++11新增的特性，其相比于push与push_back效率会更高，感兴趣的同学研究研究此文章：C++ STL vector添加元素（push_back()和emplace_back()）详解 - C语言中文网