一文读懂 c++ 容器

序列式容器

vector (向量)

动态数组
用于存储动态大小的数组，提供了快速的随机访问和数组型接口，并能够在运行时动态增长或收缩(尾部添加/删除操作)。

案例

#include <vector>
#include <iostream>

int main() {
   
   
#if 0
	std::vector<int> vec = {
   
   10, 20, 30};
#else
    // 初始化一个空的 vector
    std::vector<int> vec;
    // 添加元素至末尾
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
#endif
    // 访问元素
    std::cout << "First element: " << vec[0] << '\n'; // 使用下标操作符
    std::cout << "Second element: " << vec.at(1) << '\n'; // 使用 .at() 方法，带边界检查

    // 获取 vector 的大小
    std::cout << "The vector size is: " << vec.size() << '\n';

    // 遍历 vector
    for (size_t i = 0; i < vec.size(); ++i) {
   
   
        std::cout << vec[i] << ' ';
    }
    std::cout << '\n';

    // 使用迭代器遍历
    for (auto it = vec.begin(); it != vec.end(); ++it) {
   
   
        std::cout << *it << ' ';
    }
    std::cout << '\n';
    
    // 使用范围基于的 for 循环
    for (int num : vec) {
   
   
        std::cout << num << ' ';
    }
    std::cout << '\n';

    // 移除最后一个元素
    vec.pop_back();

    // 清空 vector
    vec.clear();
    
    return 0;
}

使用场景

1. 当你需要一个可以动态改变大小的数组时： std::vector允许在运行时添加和删除元素。因此，如果数据集合的大小不是固定的，使用vector会非常方面。
2. 当需要频繁访问元素（通过下标），而不需要在中间插入或删除元素时： std::vector提供了对其元素的快速随机访问（时间复杂度为O(1)），但在中间插入或删除操作会导致内部元素的移动，时间复杂度较高（平均为O(n)）
3. 当要求内存连续存储时： std::vector的所有元素都是在一个连续的内存块内存储的，这意味着可以获得数据局部性的优势，并且可以利用指针算术直接访问元素
4. 在进行大量元素插入或移除操作时，通常在末端操作： 对于std::vector，在末尾添加（push_back()）或移除（pop_back()）元素效率最高，因为这些操作不需要移动除新增或移除元素之外的任何元素

总结

选择std::vector时应该注意的是，为了支持动态扩展，它可能会在内存中实现多次分配和复制。当vector容量不足以容纳更多元素时，它将进行重新分配，并将所有元素复制到新的内存地址。为了减少这种分配和复制的开销，如果知道大致所需的容量，可以使用reserve()方法预先分配足够的空间。

deque (双端队列)

双端动态数组
允许在容器的两端快速插入和删除对象。与 std::vector 不同的是，std::deque 支持在两端高效地添加或移除元素，非常适合用作队列或双端队列数据结构。

案例

#include <deque>
#include <iostream>

int main() {
   
   
#if 0
	std::deque<int> d = {
   
    10, 20 };
#else
    std::deque<int> d;
    // 在末尾添加元素
    d.push_back(10);
    d.push_back(20);
#endif
    // 在开头添加元素
    d.push_front(0);
    d.push_front(-10);

    // 访问元素
    std::cout << "First element: " << d.front() << '\n'; // 访问第一个元素
    std::cout << "Last element: " << d.back() << '\n';   // 访问最后一个元素

    // 下标访问元素（但不如 std::vector 那么快）
    std::cout << "Element at index 2: " << d[2] << '\n';

    // 使用迭代器遍历
    for (std::deque<int>::iterator it = d.begin(); it != d.end(); ++it) {
   
   
        std::cout << *it << ' ';
    }
    std::cout << '\n';

    // 使用范围基于的 for 循环
    for (int n : d) {
   
   
        std::cout << n << ' ';
    }
    std::cout << '\n';

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

    return 0;
}

使用场景

1. 两端操作： 如果你的应用场景需要在容器的两端添加或删除元素，使用 std::deque 是非常合适的。它在两端的插入和删除效率都很高
2. 作为真正的双端队列（Double-ended queue）： std::deque 可被用作队列（先进先出结构）或栈（先进后出结构），因为它提供了一致的接口来操作容器的两端
3. 大量插入或删除： 如果需要在开始位置频繁插入或删除元素，std::vector 在这种情况下可能会有较差的性能，因为每次都需要移动元素。相比之下，std::deque 在两端插入和删除都有良好的性能
4. 随机访问： 尽管 std::deque 也提供了随机访问能力，但由于其内部可能是块状链表结构，访问中间元素的效率可能不如 std::vector 那么快。因此，当你需要结合两端插入/删除和不太频繁的随机访问时，std::deque 是一个不错的选择
5. 作为适配器的基础容器： C++ 标准库中的 stack 和 queue 容器适配器可以使用 std::deque 作为默认的底层容器，尽管 stack 通常用 std::deque（或 std::vector），而 queue 通常专门使用 std::deque，因为 stack 不需要两端操作，而 queue 需要

总结

总的来说，std::deque 在需要灵活操作两端元素的场合表现良好，特别是当你不确定需要的容量大小，并且插入或删除操作在元素集的两端比中间更频繁时，它是一个很好的选择。由于其对两端操作的优化，std::deque 在特定应用场景下，性能可能优于 std::vector。

list (链表)

双向链表
通过双向指针连接各个元素。与数组（如 std::vector）或块状连续存储（如 std::deque）不同，std::list 中的元素在内存中并不连续存放，这使得它非常适合在中间位置进行快速插入和删除操作。

案例

#include <list>
#include <iostream>

int main() {
   
   
    // 初始化列表
#if 0
    std::list<int> mylist = {
   
   2, 4, 6, 8};
#else
	std::list<int> mylist;
	mylist.push_front(6);