STL 篇

序列

vector

vector，array，list，deque

• Iterators
  • begin end
  • rbegin rend 反向的迭代器
• Element Access
  • at 检查边界，超出抛出错误
  • operator[] 不检查错误，超出为UB
  • front 最前面的元素，常数复杂度
  • back
• Capacity
  • empty
  • size
  • reserve 提前预留内存空间，提高效率
  • capacity 已经申请的内存空间
• Modifiers
  • clear 清除长度（内存不清除）
  • erase
erase(iterator pos) / erase(iterator first, iterator last)
  • insert
insert(iterator pos, T&& value)
    返回 iterator
  • swap 可以拿来清除内存
  • push_back 在后面加入
  • pop_back 弹出最后面（对空 vec 操作为 UB）

deque

和上面也差不多，但多了几个成员函数

• Modifiers:
  • push_front 在前面加入
  • pop_front 弹出最前面（对空 deque 操作为 UB）

关联

set，map

参考下面吧 值得注意的是多了这些函数

• Lookup:
  • lower_bound 时间复杂度 O(logn) ，与之相比，algorithm 里的 lower_bound 就要慢了
  • upper_bound
• Iterators
  • rbegin rend 反向的迭代器

无序关联（c++11）

unordered_set，unordered_multiset，unordered_map，unordered_multimap

慎用这些容器，虽然它们表面的复杂度是 O(1)，但是随着容器变大，哈希冲突加剧，操作复杂度可能会线性增长，特别是离散化的场景，不要偷懒

unordered_map

• Lookup:
  • operator[] 没有右值的情况下存在 key 返回 value，不存在调用默认 constructor 设值并返回
  • at 与 [] 类似，但是没有右值且 key 不存在的情况下抛出错误
  • count 返回 0 或 1（key 是唯一捏）
  • find 返回元素指针
  • contains （c++20）字如其名
• Modifiers
  • clear 清除长度（内存不清除）
  • erase
erase(iterator pos) / erase(iterator first, iterator last)
  • insert
insert(make_pair(_,_)) / insert({_,_} / insert({{_,_},{_,_}})
    返回 std::pair<iterator, bool>
  • swap 可以拿来清除内存
• Capacity
  • size empty
• Iterator
  • begin end

unordered_set

• Lookup:
  • count 返回 0 或 1（key 是唯一捏）
  • find 返回元素指针
  • contains （c++20）字如其名
• Modifiers
  • clear 清除长度（内存不清除）
  • erase
erase(iterator pos) / erase(iterator first, iterator last)
  • insert
    返回 std::pair<iterator, bool>
  • swap 可以拿来清除内存
• Capacity
  • size empty
• Iterator
  • begin end

Utility 篇

pair

生成: make_pair(t1,t2)
比较运算：第一个和第二个元素
访问: p.first p.second
解构赋值: tie(x,y)=make_pair(t1,t2)(其实是 tuple 的啦)(c++11)

tuple

生成: make_tuple(t1,t2,...)
访问:

// Index-based access
std::cout << "( " << std::get<0>(t)
<< ", " << std::get<1>(t)
<< ", " << std::get<2>(t)
<< " )\n";

// Type-based access (C++14 or later)
std::cout << "( " << std::get<int>(t)
<< ", " << std::get<const char*>(t)
<< ", " << std::get<double>(t)
<< " )\n";

解构赋值: tie(x,y)=make_tuple(t1,t2) (c++11)