STL

标准模板库 STL（Standard Template Library），是 C++ 标准库的一部分，不需要单独安装，只需要#include 头文件。C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。

vector

动态数组。

#include <vector>

vector<int> a;

a.size();   // return size
a.empty();  // return empty or not
a.clear();  // void

for (int i = 0; i < 10; i ++) {
    a.push_back(i); // pop_back
}

// 3 ways to traverse
for (int i = 0; i < a.size(); i ++) {
    cout << a[i] << " ";
}

for (vector<int>::iterator i = a.begin(); i != a.end(); i ++) {
    cout << *i << " ";
}

for (auto x : a) {
    cout << x << " ";
}

// front() and back()
cout << a.front() << " " << a[0] << endl;
cout << a.back() << " " << a[a.size() - 1] << endl;

// compare two vector
vector<int> a(4, 3); // [3, 3, 3, 3]
vector<int> b(3, 4); // [4, 4, 4]
if (a < b) {
    cout << "a < b" << endl; // this, because of dictionary order
}
else {
    cout << "a > b" << endl;
}

系统在分配空间所需要的时间与空间大小无关，只与申请次数有关。因此 vector 采用了倍增的思想，一开始的空间为 32，当我们中的元素个数超过 32 时，申请一倍的空间 64，而不是申请 33，这样做的好处是降低申请次数，节约时间。

pair

数对。

#include <utility>  // maybe not use

pair<int, string> p;

p = make_pair(10, "hello");
p = {20, "abc"};

cout << p.first << " " << p.second << endl;

// compare, first key word, second key word

pair<int, pair<int, string>> p3;
p3 = {20, {30, "abc"}};

string

字符串，有别于 C 语言中的字符数组。

#include <string>

string a = "hello";

a += " world!";
cout << a << endl;

a.size();
a.empty();
a.clear();

// substr(i, len)
cout << a.substr(1, 2) << endl; // a[1~2]
cout << a.substr(1, 20) << endl;
cout << a.substr(1) << endl;

printf("%s\n", a.c_str()); // return address

queue

队列。

#include <queue>

queue<int> q;

q.size();
q.empty();

// FIFO
q.push(1);
q.front();  // front of queue
q.back();   // back of queue
q.pop();    // pop front of queue

priority_queue

优先队列，堆。

#include <priority_queue>

priority_queue<int> pq;  // default max

pq.size();
pq.empty();

pq.push(1);
pq.top();   // return max
pq.pop();

默认是大根堆，如果想要小根堆：

• 插入原数的相反数
• 定义小根堆：priority_queue<int, vector<int>, greater<int>> heap;

stack

栈。

#include <stack>

stack<int> stk;

stk.size();
stk.empty();

stk.push(1);
stk.top();
stk.pop();

deque

双端队列，实际上就是一个加强版的 vector。

#include <deque>

deque<int> d;

d.size();
d.empty();
d.clear();

d.front();
d.back();

d.push_back();
d.pop_back();
d.push_front();
d.pop_front();

cout << d[0] << " " *iter << " " << *d.begin() << endl;

由于 deque 实在是太慢了，比一般数组要慢好几倍，因此一般不用。

set

集合。

#include <set>

set<int> s;         // no repeat
multiset<int> ms;   // allow repeat

s.size();
s.empty();

s.insert(x);
s.find(x);    // return x in or not in
s.count(x);   // return numbers of x

s.erase(x);      // remove all x
s.erase(iter);   // remove *iter, only one

s.lower_bound();  // return >= x minimum, iter
s.upper_bound();  // return > x  minimum, iter

• set 中没有重复元素，插入重复元素会被忽略
• multiset 中允许重复元素
• 操作的时间复杂度都是 $O(\log n)$
• 1, 2, 2, 2, 3 中：
  • s.lower_bound(2) 就是 s.begin() + 1
  • s.upper_bound(2) 就是 s.begin() + 3

map

键值对容器。

#include <map>

map<int> p;
multimap<int> mp;

p.size();
p.empty();

p.insert(make_pair(1, "ABC"));
p.find({1, "ABC"});

p.erase({1, "ABC"});
p.erase(p.begin());

p[2] = "DEF";
cout << p[2] << endl;  // DEF

p.lower_bound();
p.upper_bound();

• 可以像数组一样使用下标索引，但是时间复杂度为 $O(\log n)$。
• map 的排序默认按照 key 从小到大进行排序

哈希表

#include <unordered_set>
#include <unordered_map>

unordered_set<int> us;
unordered_multiset<int> ums;

unordered_map<int> hash;
unordered_multimap<int> mhash;

• 无序集合与无序映射
• 和上述操作一样都支持增删改查，但不支持 lower_bound, upper_bound
• 时间复杂度变为 $O(1)$

bitset

压位。

假如我们需要一个 1024 大小的布尔数组。注意：布尔数组的每一个元素大小是 1 Byte。但是每个 Byte 只用来表示了 true 或者 false，因此可以把 8 个元素压缩到一个字节中，得到的就是 128 Byte 大小的元素。

bitset 就是每个字节上存 8 位。可以把 bool 数组空间缩小到 1/8。

#include <bitset>

bitset<10000> s;

// ~, &, |, ^;
// >>, <<;
// ==, !=
// s[]

s.count(); // return 1 numbers in s

s.any();   // return if at least one 1
s.none();  // return if s == 0

s.set();      // set s = 111111...
s.set(k, v);  // set s[k] = v;
s.reset();    // set s = 000000...

s.flip();     // ~s
s.flip(k);    // s[k] = ~s[k]