鸭梨公共文档

主题

STL 容器 ​

统一按照 C++11 标准编写参考 C++ 程序设计语言（第四部分）

1. 顺序容器 ​

模板参数 A 是一个分配器，容器用它来分配和释放内存：

c++
template<typename T, typename A = allocator<T>>
class vector {
}
顺序容器功能
vector<T, A>类型为 T 的默认容器，空间连续
list<T, A>T 类型的双向链表
forward_list<T, A>T 类型的单链表
deque<T, A>T 类型的双端队列，向量和链表的混合

2. 有序关联容器 ​

  • C 是比较类型
  • A 是分配器类型
    • 对于映射，A 默认为 std::allocator<std::pair<const K, T>>
    • 对于集合，A 默认为 std::allocator<K>
  • K 的默认序标准是 std::less<K>
有序关联容器功能
map<K, V, C, A>K 到 V 的有序映射 (K, V) 的有序序列
multimap<K, V, C, A>允许关键字重复的映射
set<K, C, A>K 类型的有序集合
multiset<K, C, A>允许关键字重复的集合

这些容器通常用平衡二叉树（通常是红黑树）实现。

3. 无序关联容器 ​

  • H 是哈希函数类型
  • E 是相等性测试，默认是 std::equal_to<K>
  • A 是分配器类型
  • K 的默认哈希函数类型 H 为 std:hash<K>
无序关联容器功能
unordered_map<K, V, H, E, A>从 K 到 V 的无序映射
unordered_multimap<K, V, H, E, A>允许关键字重复的无序映射
unordered_set<K, H, E, A>K 类型的无序集合
unordered_multiset<K, H, E, A>允许关键字重复的无序集合

这些容器都使用溢出链表法的哈希表实现。

4. 容器适配器 ​

容器适配器功能
priority_queue<T, C, Cmp>T 的优先级队列，Cmp 是优先级函数类型
queue<T, C>T 的队列
stack<T, C>T 的栈
  • priority_queue 的默认优先级函数 Cmp 为 std::less<T>
  • queue 的默认容器类型 C 为 std::deque<T>
  • stack 和 priority_queue 的默认容器类型 C 为 std::vector<T>

5. 拟容器 ​

有一些数据类型具有和容器类似的特征，这些类型被称为拟容器，列举最常见的拟容器：

  • 对于 basic_string，A 是其分配器，Tr 是字符萃取
拟容器功能
T[N]内置数组，没有任何成员函数
array<T, N>固定大小的数组，N 个连续储存的类型为 T 的元素
basic_string<C, Tr, A>类型为 C 的字符序列
stringbasic_string<char>
u16stringbasic_string<char16_t>
u32stringbasic_string<char32_t>
wstringbasic_string<wchar_t>
valarray<T>T 类型的数值向量
bitset<N>N 个二进制位的集合
vector<bool>vector<T> 的特例化版本，紧凑的二进制位

6. 总结 ​

总结上面的容器类型：

  • 关联容器都是链式结构（树结构），节点类型为其成员 value_type（对于映射是 std::pair<const K, V>，对于集合是 K）
  • 排序一个序关系（如 <）来排序
  • 尽量使用 vector、string 或者 array 这样的容器，可以避免错误
  • 优先选择标准的 string，避免其他类型的字符串