【C++】SLT 六大组件之一：容器总结

–
容器分类：

• 序列式容器：有顺序如 vector
• 关联式容器：有关联如 map、set

---

🔺🔺🔺

1. map / set

---

1.1 常见接口的使用

• insert
• erase
• find
• map 的 operator[]
• iterator

1.2 经典问题

operator[] 的返回值是什么？

value 的引用

底层实现原理是什么？

• 红黑树：
  • 规则
  • 增删查改的效率

一个类型要做 map 和 set 的 K 有什么要求？

• 支持比较大小，因为底层是搜索树

map 和 set 有什么特点？

• 查找的效率为 O(logN)
• 遍历是按照 key 排序的，且可以对 key 去重

1.3 multi 版本的特点

• 允许键值冗余

---

2. unordered_map / unordered_set（C++11）

2.1 常见接口的使用

• insert
• erase
• find
• unordered_map 的 operator[]
• iterator

2.2 经典问题

底层实现原理是什么？

• 哈希表：
  • 规则
  • 增删查改的效率

一个类型要做 unordered_map 和 unordered_set 的 K 有什么要求？

• 能取模或者配一个哈希的仿函数支持转化成整型取模
• 支持 == 比较

unordered_xxx 和 map/set 相比有什么特点？

• 更快，查找的效率平均为 O(1)
• 遍历是无序的，也可以对 key 去重

---

3. vector / list

---

3.1 常见接口的使用

vector：

• push_back / pop_back
• []
• reserve ：只开空间，不能用 []，因为 [] 会检查未初始化数据
  resize ：开空间 + 初始化，使用后，可以用 [] 访问进行修改
• insert / erase
• iterator

3.2 常见问题

vector 和 list 的比较？

• vector 的优点：

  • 适合尾插尾删
  • 支持通过下标随机访问
  • 因为是连续的物理空间，cpu 高速缓存访问，命中率会更高

• vector 的缺点：

  • 头部中间插入需要挪动数据，效率比较低
  • 扩容需要代价

• list 的优点：

  • 任意位置 O(1) 的插入删除
  • 按需申请释放

-list 的缺点

• 不支持随机访问
• list 可能造成内存碎片的问题，不过 空间配置器 可以一定程度上解决

vector 扩容是怎么扩的？

• 一般是 2 倍扩容，但是不是一定，和编译器有关（g++ 2倍，vs 1.5倍）
  • 至于为什么是 2 倍左右？合适呗，一次扩多了浪费，一次扩少了效率低
• C++11 之前 使用的是 拷贝构造
• C++11 之后 使用的是 移动构造

---

🔺🔺

4. string 常见接口的使用

• +=
• find
• insert / erase
• []
• iterator
• c_str
• sub_str
• reserve
• resize
• to_string
• stoi

---

5. stack / queue 常见接口的使用

• push / pop
• top
• front / back
• empty / size

---

6. priority_queue 常见接口的使用

底层是 二叉树 的 堆

• push / pop
• top
• empty / size

7. bitset 常见接口的使用

• set
• reset
• test

---

🔺

8. array（C++11）

• 核心价值：相比 C 的静态数组，[] 绝对检查越界

• 委员会期望代替静态数组，但实际效果不明显

9. forward_list（C++11）

• 使用场景：只头插头删，又想节省一点点空间

• 相同场景下，比起 list 有一点点优势

10. deque

• 使用场景：头尾插入删除多，可能还需要一些下标的随机访问
• 要注意的是，不要大量的下标随机访问，否则效率不如 vector 好