文章

Stl容器

发表于 更新于
作者 klizzz
次阅读 26 分钟阅读
Stl容器

[TOC]

容器的简单概念

一些重要的容器及其简要介绍：

（1）向量（std::vector）

  1. 内存结构：动态数组，支持快速随机访问。通常使用较少的内存，因为它仅存储实际的元素。
  2. 实现原理：动态数组，在内存中连续存储元素，自动调整大小以容纳更多元素。当超出当前容量时，会分配一个更大的内存块，复制现有元素，并释放旧的内存。
  3. 性能特点：
    • 提供高效的随机访问，时间复杂度为 O(1)。
    • 在数组末尾添加或移除元素也很快，O(1)（均摊复杂度）。
    • 在数组中间或开始进行插入或删除操作时效率较低，可能需要移动后面的所有元素，O(n)。
    • 查找元素时效率也较低，O(n)。
  4. 场景使用：需要频繁访问元素，特别是随机访问，或者添加和移除操作主要发生在数组的末尾时。

（2）列表（std::list）

  1. 内存结构：双向链表，支持在任何位置快速插入和删除元素，不支持随机访问，也就是不能像数组那样通过索引直接访问元素。通常使用更多的内存，因为每个元素都需要额外的内存来存储前后元素的指针。
  2. 实现原理：每个元素作为独立的节点存储，每个节点有指向前一个和后一个节点的指针。
  3. 性能特点：
    • 插入和删除操作快，特别是在列表中间进行操作时，因为不需要移动其他元素， O(1)。
    • 不支持快速随机访问，访问元素需要从头或尾部遍历，访问和查找均为 O(n)。
  4. 场景使用：适合于经常需要在序列中间进行插入或删除的场合。

（3）双端队列（std::deque）

  1. 内存结构：动态数组，类似于向量，但可以在头部和尾部进行高效的插入和删除操作。内存消耗介于 std::vector 和 std::list 之间。
  2. 实现原理：通常由一系列固定大小的数组和一个中央控制器组成。中央控制器维护着数组的一个索引，用于快速定位任何元素的位置。当在两端增加元素超出当前块的界限时，会分配新的块并更新中央控制器。
  3. 性能特点：
    • 支持随机访问， O(1)。
    • 在头部和尾部插入或删除的效率很高：O(1)（均摊复杂度）；但在中间插入或删除效率较低：O(n)。
    • 查找元素的效率也很低：O(n)。
  4. 场景使用：当你需要双向的动态数组，且插入和删除主要发生在两端时。

（4）std::map（映射）

  1. 内存结构：基于红黑树实现的，维护键值对。因为红黑树的性质，使用的内存比线性数据结构多。
  2. 实现原理：通过平衡二叉搜索树实现的，通常是红黑树。红黑树是一种自平衡二叉搜索树，它可以保证在最坏的情况下基本操作（如插入、删除和查找）的时间复杂度为 O(log n)。
  3. 性能特点：
    • 元素始终按照键的顺序排序。
    • 查找、插入和删除操作的时间复杂度为 O(log n)。
  4. 场景使用：当你需要双向的动态数组，且插入和删除主要发生在两端时。

红黑树是一种自平衡的二叉搜索树，保持了树的平衡性。在插入和删除节点时，通过旋转和颜色调整等操作，能够保持树的高度平衡，使得整棵树的高度不会过高，从而保证了查找、插入和删除操作的时间复杂度为 O(log n)。

（5）std::set（集合）

  1. 内存结构：基于红黑树实现，维护一个有序的不重复元素集。相比线性容器，会使用更多的内存。
  2. 实现原理：std::set 的实现与 std::map 类似，也是使用红黑树来保持元素有序。std::set 只包含键，没有关联的值。
  3. 性能特点：
    • 元素按顺序存储。
    • 查找、插入和删除操作的时间复杂度为 O(log n)。
  4. 场景使用：当你需要存储不重复的元素并保持顺序时。

（6）std::unordered_map（无序映射）

  1. 内存结构：基于哈希表的键值对集合。内存占用通常高于 std::map，因为哈希表的负载因子和冲突解决策略。
  2. 实现原理：哈希表使用一个哈希函数将键映射到存储桶中，每个桶存储一个元素列表。这允许快速查找，因为哈希函数可以直接定位桶的位置。
  3. 性能特点：
    • 元素不按任何顺序存储。
    • 平均情况下，查找、插入和删除操作的时间复杂度为 O(1)，最坏情况（哈希冲突）为 O(n)。
  4. 场景使用：当你需要快速访问并且元素顺序不重要时。

（7）std::unordered_set（无序集合）

  1. 内存结构：基于哈希表的不重复元素集合。通常比 std::set 使用更多的内存。
  2. 实现原理：与 std::unordered_map 相似，std::unordered_set 也是基于哈希表实现。不同之处在于它只存储键而没有映射的值。提供快速的平均时间复杂度访问。
  3. 性能特点：
    • 元素不按任何顺序存储。
    • 平均情况下，查找、插入和删除操作的时间复杂度为 O(1)，最坏情况（哈希冲突）为 O(n)。
  4. 场景使用：当你需要快速访问并且元素顺序不重要时。

（8）std::multimap (多重映射)

  1. 内存结构：与 std::map 类似，std::multimap 是基于红黑树实现，它允许键对应多个值。内存使用比 std::map 更多，因为它允许键重复。
  2. 实现原理：std::multimap 与 std::map 类似，都是使用红黑树，但它允许多个元素拥有相同的键，即键不唯一。
  3. 性能特点：
    • 允许键值对中的键重复。
    • 查找、插入和删除操作的时间复杂度为 O(log n)。
  4. 场景使用：当你需要一个键对应多个值，并且需要保持数据排序时。

（9）std::multiset (多重集合)

  1. 内存结构：与 std::set 类似，std::multiset 是基于红黑树实现，允许存储重复元素。内存使用比 std::set 更多，因为它允许元素重复。
  2. 实现原理：std::multiset 与 std::set 类似，也是基于红黑树，但它允许相同的元素出现多次，即元素不唯一。
  3. 性能特点：
    • 允许元素重复。
    • 查找、插入和删除操作的时间复杂度为 O(log n)。
  4. 场景使用：当你需要存储可重复的元素并保持顺序时。

（10）std::unordered_multimap (无序多重映射)

  1. 内存结构：与std::unordered_multimap 是一个基于哈希表实现的容器，它可以存储键值对，其中键可以重复。由于哈希表的性质和键的重复性，可能比 std::unordered_map 使用更多内存。
  2. 实现原理：与 std::unordered_map 类似，std::unordered_multimap 是基于哈希表实现，并且允许相同的键对应多个不同的值。
  3. 性能特点：
    • 键可以重复，元素没有特定顺序。
    • 平均情况下，查找、插入和删除操作的时间复杂度为 O(1)，最坏情况下为 O(n)。
  4. 场景使用：当你需要快速存取元素，且允许键重复，元素顺序不重要时。

每种容器都有其优势和用途，选择合适的容器取决于具体应用的需求。例如：

  • std::list ：适用于频繁在序列中间插入或删除元素。
  • std::vector 或 std::deque ：适用于快速随机访问元素。
  • std::set 和 std::map ：需要排序和唯一性保证。
  • std::unordered_set 和 std::unordered_map：不关心排序但重视快速访问的情况。

vector

1. 基本概念

  • 用途：动态数组，能够在尾部高效地添加或移除元素。
  • 实现：在内存中连续存储元素，自动调整大小以容纳更多元素。当超出当前容量时，会分配一个更大的内存块，复制现有元素，并释放旧的内存。

2. 移除一个特定元素

从C++的vector中移除一个特定的元素，可以使用vector的erase和std::remove算法来实现，也就是常说的erase-remove习语：

1
2

std::vector<T>::iterator it = std::remove(vec.begin(), vec.end(), value);
vec.erase(it, vec.end());

这里的value代表要移除的特定元素的值，vec是指向vector的迭代器。这个方法使用了remove算法将要移除的元素移动到vector末尾，并返回指向这些被移除元素的迭代器。然后，通过使用vector的erase方法，从vector中删除这些元素。

**erase-remove习语 **也可以写成下面一行代码的形式：

1

vec.erase(std::remove(vec.begin(), vec.end(), value), vec.end());

3. vector 初始化

std::vector<T> 定义于 <vector>，C++11 是分水岭：引入列表初始化、移动语义、initializer_list；C++17 完善类模板参数推导(CTAD)；C++20 增加 constexpr 支持。

一、C++98 仅支持的初始化（老式写法）

1. 默认空构造
1
2

#include <vector>
std::vector<int> v1; // 空容器，size=0，capacity 通常为 0（平台实现定义）
2. 指定元素个数 + 默认值
1
2
3
4
5

// 创建5个int，全部初始化为0
std::vector<int> v2(5);

// 创建4个string，全部初始化为"abc"
std::vector<std::string> v3(4, "abc");
3. 拷贝另一个 vector（拷贝构造）
1
2

std::vector<int> temp(3, 10);
std::vector<int> v4(temp); // 深拷贝，独立内存
4. 迭代器区间初始化（数组/其他容器）
1
2

int arr[] = {1,2,3,4};
std::vector<int> v5(arr, arr + sizeof(arr)/sizeof(int));
5. 拷贝初始化（= 形式）
1

std::vector<int> v6 = v4; // 拷贝初始化，调用拷贝构造函数（非赋值运算符）

C++98 限制：不能直接用大括号 {} 初始化，没有 initializer_list，不能临时列表赋值。

二、C++11 新增核心初始化方式（最常用）

C++11 引入 std::initializer_list<T>，支持大括号列表初始化，同时支持移动构造。

1. 列表初始化（直接大括号，推荐）
1
2
3
4
5

// 直接写入元素，size自动匹配
std::vector<int> v1{1, 2, 3, 4, 5};

// 等价写法（= 可省略）
std::vector<int> v2 = {10, 20, 30};

⚠️ C++98 不支持此写法，编译报错。

2. 区分 (n, val) 和 {n, val} 陷阱
1
2

std::vector<int> a(2, 9); // 2个元素：[9,9] C++98/11通用
std::vector<int> b{2, 9}; // 2个元素：[2,9] 仅C++11+

括号与大括号语义完全不同，极易踩坑。

3. 移动构造（右值临时vector）
1
2

std::vector<int> getTmp() { return {1,2,3}; }
std::vector<int> v = getTmp(); // C++11 移动，不拷贝内存
4. 初始化后赋值 initializer_list
1
2

std::vector<int> v;
v = {1, 3, 5, 7}; // C++11 允许列表赋值
5. 二维vector便捷初始化
1

std::vector<std::vector<int>> mat = {{1,2}, {3,4}, {5,6}};
6. {} 调用非 initializer_list 构造函数（迭代器区间）

当 {} 内的元素类型与 value_type 不兼容时，编译器会回退到普通构造函数。例如用一对迭代器初始化：

1
2
3
4
5

vector<int> seq_dig{12, 23, 34, 45, 56};
auto l = lower_bound(begin(seq_dig), end(seq_dig), 20);
auto r = upper_bound(begin(seq_dig), end(seq_dig), 50);
std::vector<int> v{l, r};  // l, r 是迭代器，不匹配 initializer_list<int>
                            // 回退调用 vector(InputIt, InputIt)

这与高频易错点 #5 互补——”列表初始化优先匹配 initializer_list，匹配不上才尝试其他构造函数“。这篇文章前面 {1,2,3} 走的全是 initializer_list，这里则是另一条路径。

三、C++17 新增：CTAD 类模板参数推导

无需显式写模板类型，编译器自动推导 T

1
2
3
4

// C++17 起合法，C++11/14 编译报错
std::vector v1{1, 2, 3};        // 推导 vector<int>
std::vector v2{"aa", "bb"};     // 推导 vector<const char*>（注意：不是 vector<std::string>！）
std::vector v3(5, 0);           // 推导 vector<int>

⚠️ 陷阱："aa" 是 const char[3]，CTAD 推导为 const char*，不会自动变成 std::string。 要得到 vector<std::string>，需使用 std::string_literals：

1
2

using namespace std::string_literals;
std::vector v2{"aa"s, "bb"s};  // 正确推导 vector<std::string>

配合迭代器也能推导：

1
2

int arr[] = {1,2,3};
std::vector v4(std::begin(arr), std::end(arr));

四、C++20/23：constexpr vector（编译期初始化）

C++20 允许在 constexpr 函数内瞬态使用 vector（在函数内创建并销毁，分配的内存不能逃逸到编译期之外）：

1
2
3
4
5

// ✅ C++20：constexpr 函数内瞬态使用
constexpr auto func() {
    std::vector<double> v{1.1, 2.2};
    return v.size();  // v 在此销毁，内存瞬态释放
}

声明 constexpr vector 变量则是 C++23 才支持的特性（P1004R2）：

1
2

// ✅ C++23：可声明 constexpr vector 变量
constexpr std::vector<int> vec{1,2,3,4};

C++17 及更早：vector 完全不能用于 constexpr 上下文。

高频易错点

  1. (count, value) vs {val1, val2} C++11 后大括号是元素列表，圆括号是数量+初值，语义不同。
  2. C++98 不能写 vector<int> v{1,2}，必须用数组+迭代器迂回。
  3. CTAD 仅 C++17 支持，老编译器需手动指定模板参数。
  4. constexpr vector 变量须 C++23；C++20 仅支持 constexpr 函数内瞬态使用（创建→使用→销毁，内存不逃逸）。
  5. 列表初始化优先级高于普通构造函数：编译器优先匹配 initializer_list 构造。

C++98 模拟列表初始化兼容写法（无C++11时）：

1
2

int arr[] = {1,2,3,4};
std::vector<int> v(arr, arr + sizeof(arr)/sizeof(int));

std::queue

std::queue 是 C++ 标准模板库（STL）中的一个容器适配器，提供了先进先出（FIFO）的数据结构。std::queue 的底层通常使用 std::deque 或 std::list 实现，但默认情况下，它使用 std::deque。

以下是一些 std::queue 的基本操作和用法：

  1. 创建一个队列：

    1
2
3

    #include <queue>
   
std::queue<int> q;

  2. 向队列中添加元素（入队）：

    1
2
3

    q.push(1);
q.push(2);
q.push(3);

  3. 从队列中移除元素（出队）：

    1

    q.pop();

  4. 获取队列前端的元素：

    1

    int frontElement = q.front();

  5. 获取队列尾端的元素：

    1

    int backElement = q.back();

  6. 检查队列是否为空：

    1

    bool isEmpty = q.empty();

  7. 获取队列中的元素数量：

    1

    size_t size = q.size();

这是一个小例子，展示了如何使用 std::queue：

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

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    // 入队元素
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // 获取队首和队尾元素
    std::cout << "Front element: " << myQueue.front() << std::endl;
    std::cout << "Back element: " << myQueue.back() << std::endl;

    // 出队元素
    myQueue.pop();

    // 再次获取队首元素
    std::cout << "Front element after pop: " << myQueue.front() << std::endl;

    // 检查队列是否为空
    if (!myQueue.empty()) {
        std::cout << "The queue is not empty" << std::endl;
    }

    // 获取队列大小
    std::cout << "Queue size: " << myQueue.size() << std::endl;

    return 0;
}

在上述代码中，我们创建了一个 std::queue 的实例，然后通过 push 方法添加了一些整数。我们使用 front 和 back 方法来查看队列的第一个和最后一个元素。通过调用 pop 方法，我们移除了队列最前面的元素，队首的元素随之改变。最后，我们检查队列是否为空并输出队列的大小。

std::deque

std::deque 即 double-ended queue（双端队列），是 C++ 标准模板库（STL）中的一种序列容器。与 std::vector 类似，std::deque 支持随机访问迭代器，这意味着可以通过下标运算符访问元素，但其主要特点是在容器的前端和后端插入和删除元素都非常高效。

std::deque 在某些实现中是由一个或多个固定大小数组组成的，中间通过索引进行连接，这种结构使得它在头尾两端操作元素时比 std::vector 更有效率，因为它不需要移动所有元素。

以下是 std::deque 的一些基本用法：

  1. 头文件

    1

    #include <deque>

  2. 创建 std::deque 对象

    1

    std::deque<int> myDeque; // 创建一个空的双端队列

  3. 添加元素

    1
2

    myDeque.push_back(10);   // 在队列末尾添加一个元素
myDeque.push_front(20);  // 在队列开头添加一个元素

  4. 访问元素

    1
2
3
4

    int back = myDeque.back();   // 访问最后一个元素
int front = myDeque.front(); // 访问第一个元素
int at = myDeque.at(1);      // 访问指定位置的元素，带越界检查
int subscript = myDeque[1];  // 访问指定位置的元素，不带越界检查

  5. 删除元素

    1
2

    myDeque.pop_back();  // 删除最后一个元素
myDeque.pop_front(); // 删除第一个元素

  6. 大小和容量

    1
2
3

    size_t size = myDeque.size();       // 获取双端队列中元素的数量
bool isEmpty = myDeque.empty();     // 判断双端队列是否为空
myDeque.resize(5);                  // 改变双端队列的大小，如果变大，则添加默认初始化的元素

  7. 迭代器

    1
2
3
4

    for(auto it = myDeque.begin(); it != myDeque.end(); ++it) {
    std::cout << *it << ' ';
}
std::cout << '\n';

  8. 清空容器

    1

    myDeque.clear(); // 清空双端队列的所有元素

std::deque 适用于需要频繁插入和删除头尾元素的场景。例如，它可以用作队列或双端队列的基础实现，在这些用例中，std::deque 的性能通常优于 std::vector。

std::stack

std::stack 提供了以下几个基本操作：

  • push: 将一个元素添加到栈顶。pu
  • pop: 移除栈顶元素。
  • top: 访问栈顶元素。
  • empty: 检查栈是否为空。
  • size: 返回栈中元素的个数。

std::stack 默认底层使用 std::deque 实现，但是你也可以指定其他类型的容器（比如 std::vector 或 std::list），只要这个容器支持 back(), push_back(), 和 pop_back() 操作。

以下是如何使用 std::stack 的一个简单例子：

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

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // 添加元素到栈顶
    s.push(1);
    s.push(2);
    s.push(3);

    // 显示栈顶元素
    std::cout << "栈顶元素是: " << s.top() << std::endl;

    // 移除栈顶元素
    s.pop();

    // 再次显示栈顶元素
    std::cout << "现在栈顶元素是: " << s.top() << std::endl;

    // 检查栈是否为空
    if (!s.empty()) {
        std::cout << "栈不为空" << std::endl;
    }

    // 显示栈的大小
    std::cout << "栈的大小是: " << s.size() << std::endl;

    return 0;
}

参考文章1234567

  1. 来源：ChatGPT ↩︎

  2. C++ STL 容器 ↩︎

  3. C++入门：用最简洁的代码，讲解std::vector动态数组功能 ↩︎

  4. C++ STL常见容器 ↩︎

  5. C++ STL之vector详解 ↩︎

  6. 现代C++中的多映射（std::multimap）是什么？ ↩︎

  7. C++vector push_back和emplace_back的区别 ↩︎

技术, 代码基础知识
技术 代码 基础知识 C++
本文由作者按照 CC BY 4.0 进行授权