文章

Stl容器

发表于
作者 klizzz
20 分钟阅读
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());

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 进行授权