STL总结

zifuneko · 2024-04-05 18:32:32 · 算法·理论

\text{https://io.zouht.com/154.html}

\text{1 vector}

连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。

\text{1.1} 常用方法

\text{1.1.1} 构造

vector<类型> arr(长度, [初值])

时间复杂度：O(n)

vector<int> arr;         // 构造int数组
vector<int> arr(100);    // 构造初始长100的int数组
vector<int> arr(100, 1); // 构造初始长100的int数组，初值为1

\text{1.1.2} 添加&删除

• .push_back(元素)：在 \operatorname{vector} 的末尾添加一个元素，数组长度 +1
• .pop_back()：删除 \operatorname{vector} 尾部的一个元素，数组长度 -1

时间复杂度：O(1)

\text{1.1.3} 中括号

和一般数组一样的作用。

\text{1.1.4} 常用方法

\text{1.2} 注意事项

\text{1.2.1} 当心出现

应当心出现 s.size()-1 小于 0 的情况。例如这样：

vector<int> a;
long long n = a.size()-1;

通过二次封装双端队列 (\text{deque}) 容器，实现先进后出的栈数据结构。

\text{2.1} 常用方法

\text{3 queue}

通过二次封装双端队列 (\text{deque}) 容器，实现先进先出的队列数据结构。

\text{3.1} 常用方法

\text{4 priority\_queue}

提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。

\text{4.1} 常用方法

\text{4.1.1} 构造

priority_queue<类型, 容器, 比较器> pque

• 类型：要储存的数据类型
• 容器：储存数据的底层容器，默认为 vector<类型>，竞赛中保持默认即可
• 比较器：比较大小使用的比较器，默认为 less<类型>，可自定义

priority_queue<int> pque1;                            // 储存int的大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 储存int的小顶堆

进出队复杂度 O(\log n)，取堆顶 O(1).

\text{4.2} 使用

持续维护元素的有序性：每次向队列插入大小不定的元素，或者每次从队列里取出大小最小/最大的元素，元素数量 n ，插入操作数量 k.

• 每次插入后进行快速排序：k⋅n \log n
• 使用优先队列维护：k⋅\log n

\text{5 set}

提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。

即不重复且有顺序的集合。

\text{5.1} 常用方法

\text{5.1.1} 构造

set<类型, 比较器> st

• 类型：要储存的数据类型
• 比较器：比较大小使用的比较器，默认为 less<类型>

\text{5.1.2} 遍历

可使用迭代器进行遍历：

for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;

当然，迭代器 set<int>::iterator 的类型未免比较繁杂，可以使用 auto 去替换。

注意：\operatorname{set} 虽说可遍历，但仅可使用迭代器进行遍历，它不存在下标这一概念，无法通过下标访问到数据。

\text{5.1.3} 其他

增删查时间复杂度均为 O(\log n).

\text{5.2} 适用

• 元素去重：[1,1,3,2,4,4]→[1,2,3,4]
• 维护顺序：[1,5,3,7,9]→[1,3,5,7,9]

• 元素是否出现过：元素大小 [−10^{18},10^{18}]，元素数量 10^6，\operatorname{vis} 数组无法实现，通过 \operatorname{set} 可以完成。

\text{6 map}

提供对数时间的有序键值对结构。底层原理是红黑树。

\text{6.1} 常用方法

\text{6.1.1} 构造

map<键类型, 值类型, 比较器> mp

• 键类型：要储存键的数据类型
• 值类型：要储存值的数据类型
• 比较器：键比较大小使用的比较器，默认为 less<类型>，可自定义

map<int, int> mp1;               // int->int 的映射（键从小到大）
map<int, int, greater<int>> st2; // int->int 的映射（键从大到小）

\text{6.1.2} 遍历

可使用迭代器进行遍历：

for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    cout << it->first << ' ' << it->second << endl;

\text{6.1.3} 其他

增删改查时间复杂度均为 O(\log n)

\text{6.2} 适用

需要维护映射的场景可以使用：输入若干字符串，统计每种字符串的出现次数。( map<string, int> mp )

\text{6.3} 注意

\text{6.3.1} 中括号访问时默认值

如果使用中括号访问 \operatorname{map} 时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在性。

map<char, int> mp;
cout << mp.count('a') << endl; // 0
mp['a'];                       // 即使什么都没做，此时mp['a']=0已经插入了
cout << mp.count('a') << endl; // 1
cout << mp['a'] << endl;       // 0

\text{7 string}

储存字符串的容器。

\text{7.1} 常用方法

\text{7.1.1} 构造

构造函数：string(长度, 初值)

string s1;           // 构造字符串，为空
string s2 = "qwq";  // 构造字符串，并赋值qwq
string s3(10, '6');  // 构造字符串，通过构造函数构造为6666666666

\text{7.1.2} 其他方法

\text{7.2} 注意

尾接字符串一定要用 +=

可以使用 \text{sort} 函数进行排序。

string s;
sort(s.begin(), s.end());

没用。

\text{9 algorithm}

\text{9.1 swap()}

交换两个变量的值.

int a = 0, b = 1;
swap(a, b);
// now a = 1, b = 0

int arr[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
swap(arr[4], arr[6]);
// now arr = {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}

\text{9.2 sort()}

快速排序.

默认排序从小到大.

int arr[6] = {1,1,4,5,1,4};
sort(arr, arr+6);

如果要从大到小，则需要传比较器进去。

int arr[6] = {1,1,4,5,1,4};
sort(arr, arr+6, greater<int>());

如果需要完成特殊比较，则需要手写比较器。

比较器函数返回值是 \operatorname{bool} 类型，传参是需要比较的两个元素。记我们定义的该比较操作为 ⋆ ：

• 若 a\ ⋆\ b，则比较器函数应当返回 true
• 若 a\ !⋆\ b，则比较器函数应当返回 false

注意：如果 a=b，比较器函数必须返回 false

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first > b.first;
}

int main()
{
    vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};
    sort(arr.begin(), arr.end(), cmp);
    // arr = [(0, 0), (8, 1), (2, 9), (1, 9)]
}

\text{9.3 lower\_bound() / upper\_bound()}

在已升序排序的元素中，应用二分查找检索指定元素，返回对应元素迭代器位置。找不到则返回尾迭代器。

怎么找 ≤x\ / <x 的第一个元素呢？

减去头迭代器即可转成下标索引。

vector<int> arr{0, 1, 1, 1, 8, 9, 9};
vector<int>::iterator it = lower_bound(arr.begin(), arr.end(), 7);
int idx = it - arr.begin();
// idx = 4

\text{9.4 reverse()}

反转一个可迭代对象的元素顺序。

vector<int> arr(10);
iota(arr.begin(), arr.end(), 1);
// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
reverse(arr.begin(), arr.end());
// 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

\text{9.5 max() / min()}

返回最大值 / 最小值的数值.

int mx = max(1, 2); // 2
int mn = min(1, 2); // 1

在 \text{C++} _{11} 之后，可以使用列表构造语法传入一个列表，这样就能一次性给多个元素找最大值而不用套娃了：

// Before C++11
int mx = max(max(1, 2), max(3, 4)); // 4
int mn = min(min(1, 2), min(3, 4)); // 1

// After C++11
int mx = max({1, 2, 3, 4}); // 4
int mn = min({1, 2, 3, 4}); // 1

\text{9.6 unique()}

消除数组的重复相邻元素，数组长度不变，但是有效数据缩短，返回的是有效数据位置的结尾迭代器。

例如：[1,1,4,5,1,4]→[1,4,5,1,4,?]，?位置为返回的迭代器指向。

单独使用 \operatorname{unique} 并不能达成去重效果，因为它只消除相邻的重复元素。但是如果序列有序，那么它就能去重了。

但是它去重后，序列尾部会产生一些无效数据：[1,1,2,4,4,4,5]→[1,2,4,5,?,?,?]，为了删掉这些无效数据，我们需要结合 \operatorname{erase}.

最终，给 \operatorname{vector} 去重的写法便是：

vector<int> arr{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());

\text{9.7 数学函数}

所有函数参数均支持 \operatorname{int} / \operatorname{long \ long} / \operatorname{float} / \operatorname{double} / \operatorname{long \ double}.

由于浮点误差，有些的数学函数的行为可能与预期不符，导致 \text{WA}。

\text{9.8 gcd() / lcm()}

用于产生连续的值。

vector<int> arr(10);
iota(arr.begin(), arr.end(), 1);
// 1 2 3 4 5 6 7 8 9 10

\text{9.10 next\_permutation()}

返回容器中最大值的指针（序列 [\text{first,end)} 中的最大元素，\text{max\_element()} 默认是从小到大排列，\text{max\_element()} 输出最后一个值），其中 \text{cmp} 为可选择参数，可以是函数指针或函数对象！如果自定义的 \text{cmp} 函数写的是从大到小排列，会导致 \text{max\_element()} 输出最小值的指针。如果有多个最大值，返回的是第一次出现的位置。

作用：返回一个迭代器（输出值的话要在前面加 *），\text{min\_element()} 同理。

max_element(Number,Number+MaxSize)-Number;
//返回数组Number中最大值的下标位置，Number为数组名

*max_element(Number+2,Number+MaxSize-1)
//返回数组Number下标序列[2,MaxSize-1）中的最大值

max_element(Number[0], Number[MaxSize])-Number[0];
//返回二维数组Number[MaxSize][MaxSize]中最大值的位置

\text{10 课上代码}

#include<bits/stdc++.h>
using namespace std;

int main()
{
// vector
vector<int> aa(100, 1); // 构造初始长100的int数组，初值为1
for(int i=0; i<100; i++) cout << aa[i] << ' ';
cout << endl;

// set
set<int> st; cout << st.size() << endl;
st.insert(3); cout << st.size() << endl;
st.insert(1); cout << st.size() << endl;
st.insert(5); cout << st.size() << endl;
//st.erase(5); cout << st.size() << endl;

auto it = st.find(5);
cout << *it << endl;
for(auto it = st.begin(); it != st.end(); it++) cout << *it << ' ';
cout << endl;
// set<int>::iterator it = st.find(5);
// cout << *it;

// map
map<int, int> mp;
mp[-5] = 10;
mp[3] = 100;
for(auto it = mp.begin(); it!=mp.end(); it++)
    cout << it->first << ' ' << it->second << endl;
cout << mp.size() << endl;

//  遍历
vector<int> arr(10);
iota(arr.begin(), arr.end(), 1);
for(int i=0;i<10;i++) cout << arr[i] << ' ';

// next_permutation 全排列
vector<int> a(5);
iota(a.begin(), a.end(), 1);
for(int i=0;i<a.size();i++) cout << a[i] << ' ';
cout << endl;
while(next_permutation(a.begin(), a.end()))
{
    for(int i=0; i<a.size(); i++) cout << a[i] << ' ';
    cout << endl;
}
cout << "*";
for(int i=0;i<a.size();i++) cout << a[i] << ' ';
cout << endl;

// max()/min()
cout << max({1,2,3,4,5,6}) << endl;
cout << min({1,2,3,4,5,6}) << endl;

// unique 去重
vector<int> arr{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end());
arrr.erase(unique(arr.begin(), arrr.end()), arrr.end());
for(int i=0;i<arrr.size();i++) cout << arrr[i] << ' ';

// bitset容器
return 0;
}

本文使用 \href{https://katex.org/}{\KaTeX}