[toc]

STL容器

容器 类型 特点
vector 序列容器：动态数组 元素连续，容量会自动收缩和扩张
deque 序列容器：双端队列 分段数组实现
list 关联容器：双向链表 双向链表实现
set 关联容器：集合 红黑树实现；元素有序，不重复
map 关联容器：键值对
multiset 集合 允许重复元素
multimap
unordered_set 集合 散列实现
unordered_map 键值对 散列实现

deque<Key>

顺序的双端队列
实现方式是：多个顺序表
双端队列deque.PNG

unordered_set<Key, Hasher, Equal>

这是一个通过散列实现的集合容器，元素不能重复。可以自己提供散列函数和比较函数。
通过仿函数提供散列方法和比较方法：Hasher和Equal

  1. struct Hasher {
  2.     int operator()(const char c) {
  3.         return c - 'a';
  4.     }
  5. };

迭代器

以vector为例

STL容器 - 图2

在循环中删除迭代器指向的元素
  1. vector<int> a = { 0, 1, 2, 3, 4, 5 };
  2. for (auto it = a.begin(); it != a.end();) {
  3.     if (*it == 3) {
  4.         it = a.erease(it);
  5.     }
  6.     else {
  7.         ++it;
  8.     }
  9. }
  • erase返回指向下一个元素的迭代器，应该使用这个返回值来覆盖原来的迭代器。

    适配器

    | 适配器 | 类型 | 特点 | | —- | —- | —- | | stack | 栈 | 将任何序列容器转化为栈；默认deque | | queue | 队列 | 将任何序列容器转化为队列，默认deque | | priority_queue | 优先队列 | 序列容器转化为优先队列 |