STL¶

A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.

C++ 的容器（container），用来存储数据的，通常是不同的数据结构。

每一种容器，有自己特有的特点。都能存储数据，但是因为优点不同，所以适用在不同的场景。

他们有很多的共性操作，使用相同的成员函数，以英文单词字面意思出现。

`vector<int>`¶

vector<int>，动态数组

Vectors are sequence containers representing arrays that can change in size.

区别于静态数组 int a[110]，动态数组占用的存储空间，是根据实际情况动态调整的。

静态数组，要求开到全局变量。

动态数组，建议开到局部变量。

基本操作¶

定义

vector<int> A;        // 一个空的vector

vector<int> A = {3, 5, 6, 8};

vector<int> A(n);     // 一个大小是n的vector，但没有初始化

vector<int> A(n, 0);  // 一个大小是n的vector，每一位都是0

输入

int n;
vector<int> A;  // 如果定义的是空的vector，就需要一个数一个数push_back()

cin >> n;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    A.push_back(x);
}

int n;
cin >> n;

vector<int> A(n);  // 如果定义了vector的大小，那么就可以使用下标访问方式
for (int i = 0; i < n; i++) cin >> A[i];

int n;
cin >> n;

vector<int> A(n);
for (auto &x : A) cin >> x;  // C++11的写法

输出

for (int i = 0, len = A.size(); i < len; i++) cout << A[i] << ' ';

for (auto x : A) cout << x << ' ';  // C++11写法

大小

A.size();

排序

sort(A.begin(), A.end());

sort(A.begin(), A.end(), cmp);  // 自定义cmp函数

弹出最后一个元素

A.pop_back();

其他¶

// 清空vector
A.clear();       

// 翻转（通常用于先sort从小到大排序，然后reverse，实现从大到小排序）
reverse(A.begin(), A.end()); 

// 迭代器访问
for (vector<int>::iterator it = a.begin(); it != a.end(); it++) cout << *it << ' ';

// 二分查找
vector<int>::iterator up = upper_bound(a.begin(), a.end(), 10);
vector<int>::iterator low = lower_bound(a.begin(), a.end(), 10);
cout << *low << ' ' << *up << '\n';
cout  << low - a.begin() << ' ' << up - a.begin() << '\n';

// iterator，迭代器
// 用于遍历容器内的元素，是一个指针

// 去重操作
// 先排序，得到unique的位置，然后把从unique位置往后，全部删除
sort(A.begin(), A.end());
vector<int>::iterator it = unique(A.begin(), A.end());
A.erase(it, A.end());  
// 或者这样写
A.erase(unique(A.begin(), A.end()), A.end());

`set<int>`¶

set<int>，集合

A set is a data structure that maintains a collection of elements. The basic operations of sets are element insertion, search and removal.The benefit of the set structure is that it maintains the order of the elements.

set 默认是有序的，每个元素只能存一份。

通常用来维护一个元素只存一份、自动排序、二分查找的场景。

基本操作¶

定义

set<int> st;

set<int> st = {3, 5, 6, 8};

输入

set<int> st;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    st.insert(x);
}

输出

set 不支持下标访问。

for (auto x : st) cout << st << ' ';

判断集合是否有某个元素

if (st.count(x) != 0) ...

删除一个元素

st.erase(x);

大小

st.size();

其他¶

输出最小值

printf("最小值 %d\n", *st.begin());

输出最大值

printf("最大值 %d\n", *(--st.end()));
printf("最大值 %d\n", *st.rbegin());

二分查找

// 第一个大于等于
set<int>::iterator it = st.lower_bound(x);
if (it != st.end()) cout << *it << '\n';

// 第一个大于
set<int>::iterator it = st.upper_bound(x);
if (it != st.end()) cout << *it << '\n';

// 最后一个小于
set<int>::iterator it = st.lower_bound(x);
if (it != st.begin()){
    it--;
    cout << *it << '\n';
}

`map<int, int>`¶

map<int, int>，映射

Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.

map通常用来维护一个东西存了多少个。

基本操作¶

定义

map<int, int> mp;    // 第一关键字int，第二关键字int

map<string, int> m;   // 第一关键string，第二关键字int

维护每个元素有多少个

map<int, int> mp;

int n, x;
cin >> n;
while (n--) {
    cin >> x;
    mp[x]++;                 // 维护x这个数值，出现了多少次

    cout << mp[x] << endl;   // 输出x，出现了多少次
}

map<string, int> mp;

int n;
string s;
cin >> n;
while (n--) {
    cin >> s;
    mp[s]++;                 // 维护这个字符串，出现了多少次

    cout << mp[s] << endl;   // 输出这个字符串，出现了多少次
}

判断元素是否存在

if (mp.count(x) != 0) ...

遍历map中的每个元素

for (auto x : mp) {
    cout << x.first << " " << x.second << "\n";
}

`stack<int>`¶

stack<int>，栈

Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.

A stack is a data structure that provides two O(1) time operations: adding an element to the top, and removing an element from the top. It is only possible to access the top element of a stack.

有了 stack，就不用手动模拟栈了。

基本操作¶

定义

stack<int> st;

入栈

st.push(x);

出栈

st.pop();

访问栈顶元素

st.top();

判断栈是否为空

if (!st.empty()) ...

if (st.size() != 0) ...

对于一个空的栈，进行出栈和访问栈顶元素的操作，会带来 segment fault（段错误）

`queue<int>`¶

queue<int>，队列

queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

A queue also provides two O(1) time operations: adding an element to the end of the queue, and removing the first element in the queue. It is only possible to access the first and last element of a queue.

有了 queue，就不用手动模拟栈了。

基本操作¶

定义

queue<int> q;

入队

q.push(x);

出队

q.pop();

访问队头元素

q.front();

判断队列是否为空

if (!q.empty()) ...

if (q.size() != 0) ...

`pair<int, int>`¶

pair<int, int>，键值对

This class couples together a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public members first and second.

pair 用来表达类似行列坐标的数据结构。

同时，pair 数组的排序，默认按第一关键字从小到大排序。

省去写 struct 的麻烦。

基本操作¶

定义

pair<int, int> a, b;         // 一个键值对

vector<pair<int, int>> A;    // vector里存的是pair
pair<int, int> a[110];       // 静态数组里存的是pair
set<pair<int>> st;           // 集合里存的是pair

typedef pair<int, int> PII;  // 定义简写
vector<PII> A;

输入

int n;
cin >> n;

vector<pair<int, int>> A(n);
for (int i = 0; i < n; i++) cin >> A[i].first >> A[i].second;

// .first 访问第一关键字
// .second 访问第二关键字

pair<int, int> a = {3, 4};

输出

for (auto x : A) cout << x.first << ' ' << x.second << endl;

排序

vector<pair<int, int>> A;
A.push_back({3, 5});
A.push_back({3, 2});
A.push_back({1, 3});

sort(A.begin(), A.end());  // 按第一关键字从小到大排序。如果相同，按第二关键字从小到大

/*
1 3
3 2
3 5
*/

STL¶

vector<int>¶

基本操作¶

其他¶

set<int>¶

基本操作¶

其他¶

map<int, int>¶

基本操作¶

stack<int>¶

基本操作¶

queue<int>¶

基本操作¶

pair<int, int>¶

基本操作¶

`vector<int>`¶

`set<int>`¶

`map<int, int>`¶

`stack<int>`¶

`queue<int>`¶

`pair<int, int>`¶