跳转至

数据结构/容器

序列容器

序列容器在内存中按顺序存储数据。

  • vector：向量，可以动态增长，支持快速随机访问。在尾部之外的位置插入或删除元素可能较慢。
  • deque：双端队列，支持在头尾两端快速插入和删除操作。
    • priority_queue：优先队列，或者说是最大堆
  • list：双向链表，支持在任何位置快速插入和删除操作，但不支持快速随机访问。
  • forward_list：单向链表，只支持单向顺序访问，在任何位置的插入和删除操作都很快。
  • array：固定大小的数组，支持快速随机访问，但大小在编译时必须确定且之后不能更改。
  • string：与 vector 类似，专门用于字符的容器。

vector

构造函数有很多，常用的有以下几个：

std::vector<int> v(5, 10); // 创建一个有5个元素的vector，每个元素的值都是10
std::vector<int> v(5); // 创建一个有5个元素的vector，每个元素默认初始化（对于int类型，初始化为0）
std::vector<int> v = {1, 2, 3, 4, 5}; // 使用列表初始化vector

关联容器

关联容器使用比较函数自动排序，并提供快速的查找能力。

  • set：集合，包含键的有序集合，每个键只能出现一次。
  • multiset：多重集合，与 set 相似，但允许键值重复。
  • map：映射，基于键值对的集合，每个键只能关联一个值。他键是按照顺序排列的，而不是哈希表，底层通常使用红黑树来实现。
    • C++的map，如果使用一个不存在的key进行索引，会返回value类型默认值。
  • multimap：多重映射，与 map 相似，但一个键可以关联多个值。

无序关联容器

无序关联容器使用哈希表实现，提供平均常数时间的快速访问。

  • unordered_set：无序集合，包含键的集合，但不自动排序。
  • unordered_multiset：无序多重集合，允许键值重复。
  • unordered_map：无序映射，基于键值对，但不排序。
  • unordered_multimap：无序多重映射，一个键可以关联多个值。

从C++17开始，支持使用这样的方式遍历映射。

for (auto &[k,v] : map) {

}

在STL（标准模板库）中，容器的设计优化方向侧重于吞吐量（throughput） 而非 延迟（latency）。例如，STL容器默认的内存管理策略（如动态扩容、内存池）倾向于减少总体时间开销，但可能增加单次操作的波动，std::vector扩容时需复制原有数据，导致单次插入的延迟不稳定，std::unordered_map的哈希冲突处理（如开链法）可能影响单次查询的延迟。