526互联

在OI类竞赛中经常使用的C++STL模板类

发布时间 2023-12-02 14:41:52作者: BryceAi

vector 变长数组

vector的初始化

vector<int> a; // 定义一个空的vector，且元素类型为int
vector<int> a(n); // 定义一个长度为n，元素类型为int的vector，且每个元素都是0
vector<int> a(n, x); // 定义一个长度为n，元素类型为int，且每个元素都是x的vector
vector<int> b(a); // 定义一个a的拷贝
// 也可以定义vector的数组
vector<int> c[10];

vector的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.clear(); // 清空a 时间复杂度O(n)
a.push_back(x); // 在a的最后添加一个元素x 时间复杂度O(1)
a.pop_back(); // 删除a的最后一个元素 时间复杂度O(1)
a.front(); // 返回a的第一个元素 时间复杂度O(1)
a.back(); // 返回a的最后一个元素 时间复杂度O(1)

vector的遍历

// 下标遍历
for (int i = 0; i < a.size(); i++) {
    cout << a[i] << endl;
}
// 迭代器遍历
for (vector<int>::iterator it = a.begin(); it != a.end(); it++) {
    cout << *it << endl;
}
// C++11的范围for循环 由于部分比赛平台不支持C++11，所以不推荐使用
for (auto x : a) {
    cout << x << endl;
}

vector支持比较运算

两个vector的比较是从第一个元素开始，依次往后比较
如果两个vector的元素个数不同，则元素个数多的大
如果两个vector的元素个数相同，则从第一个元素开始，依次往后比较
如果两个vector的元素不同，则第一个不同的元素较大的vector大
如果两个vector的元素全部相同，则两个vector相等

vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 3};
vector<int> c = {1, 2, 4};
cout << (a < b) << endl; // 0
cout << (a < c) << endl; // 1
cout << (a == b) << endl; // 1

pair 二元组

pair的初始化

pair<int, int> a; // 定义一个空的pair，且元素类型为int和int
pair<int, int> a(1, 2); // 定义一个pair，且元素类型为int和int，且第一个元素为1，第二个元素为2
pair<int, int> a = make_pair(1, 2); // 定义一个pair，且元素类型为int和int，且第一个元素为1，第二个元素为2

pair的常用操作

a.first; // 返回a的第一个元素 时间复杂度O(1)
a.second; // 返回a的第二个元素 时间复杂度O(1)
a = make_pair(1, 2); // 将a的第一个元素赋值为1，第二个元素赋值为2 时间复杂度O(1)
pair<int, pair<int, int> > b(1, make_pair(2, 3)); // 定义一个pair，且元素类型为int和pair<int, int>，且第一个元素为1，第二个元素为pair<int, int>(2, 3)

pair支持比较运算

两个pair的比较是先比较第一个元素，如果第一个元素相同，则比较第二个元素
如果第一个元素不同，则第一个元素较大的pair大
如果第一个元素相同，则第二个元素较大的pair大
如果两个pair的元素全部相同，则两个pair相等

pair<int, int> a = {1, 2};
pair<int, int> b = {1, 2};
pair<int, int> c = {1, 3};
cout << (a < b) << endl; // 0
cout << (a < c) << endl; // 1
cout << (a == b) << endl; // 1

string 字符串

string的初始化

string a; // 定义一个空的string
string a = "abc"; // 定义一个string，且内容为abc
string a = b; // 定义一个string，且内容为b的拷贝

string的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.clear(); // 清空a 时间复杂度O(n)
// a.push_back(x); // 在a的最后添加一个元素x 时间复杂度O(1)
// a.pop_back(); // 删除a的最后一个元素 时间复杂度O(1)
// a.front(); // 返回a的第一个元素 时间复杂度O(1)
// a.back(); // 返回a的最后一个元素 时间复杂度O(1)
a.substr(pos, len); // 返回a从pos开始长度为len的子串 时间复杂度O(len)
// a.find(x); // 返回a中第一个x的下标，如果不存在则返回string::npos 时间复杂度O(n)
// a.find(x, pos); // 返回a中从pos开始第一个x的下标，如果不存在则返回string::npos 时间复杂度O(n)
// a.find(s); // 返回a中第一个s的下标，如果不存在则返回string::npos 时间复杂度O(n)
// a.find(s, pos); // 返回a中从pos开始第一个s的下标，如果不存在则返回string::npos 时间复杂度O(n)
a.c_str(); // 返回a的C风格字符串 时间复杂度O(1)

string支持比较运算

两个string的比较是从第一个字符开始，依次往后比较
如果两个string的字符个数不同，则字符个数多的大
如果两个string的字符个数相同，则从第一个字符开始，依次往后比较
如果两个string的字符不同，则第一个不同的字符较大的string大
如果两个string的字符全部相同，则两个string相等

string a = "abc";
string b = "abc";
string c = "abd";
cout << (a < b) << endl; // 0
cout << (a < c) << endl; // 1
cout << (a == b) << endl; // 1

queue 队列

queue的初始化

queue<int> a; // 定义一个空的queue，且元素类型为int
queue<int> a(b); // 定义一个b的拷贝

queue的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.push(x); // 在a的最后添加一个元素x 时间复杂度O(1)
a.pop(); // 删除a的第一个元素 时间复杂度O(1)
a.front(); // 返回a的第一个元素 时间复杂度O(1)
a.back(); // 返回a的最后一个元素 时间复杂度O(1)

queue的遍历

while (!a.empty()) {
    cout << a.front() << endl;
    a.pop();
}

priority_queue 优先队列

默认是大根堆

priority_queue的初始化

priority_queue<int> a; // 定义一个空的priority_queue，且元素类型为int
priority_queue<int> a(b); // 定义一个b的拷贝
priority_queue<int, vector<int>, greater<int> > a; // 定义一个空的priority_queue，且元素类型为int，且为小根堆
priority_queue<int, vector<int>, greater<int> > a(b); // 定义一个b的拷贝，且为小根堆

priority_queue的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.push(x); // 在a的最后添加一个元素x 时间复杂度O(logn)
a.pop(); // 删除a的第一个元素 时间复杂度O(logn)
a.top(); // 返回a的第一个元素 时间复杂度O(1)

priority_queue的遍历

while (!a.empty()) {
    cout << a.top() << endl;
    a.pop();
}

priority_queue的自定义比较函数

struct cmp {
    bool operator() (int a, int b) {
        return a > b;
    }
};
priority_queue<int, vector<int>, cmp> a;

stack 栈

stack的初始化

stack<int> a; // 定义一个空的stack，且元素类型为int
stack<int> a(b); // 定义一个b的拷贝

stack的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.push(x); // 在a的最后添加一个元素x 时间复杂度O(1)
a.pop(); // 删除a的第一个元素 时间复杂度O(1)
a.top(); // 返回a的第一个元素 时间复杂度O(1)

stack的遍历

while (!a.empty()) {
    cout << a.top() << endl;
    a.pop();
}

deque 双端队列

deque的初始化

deque<int> a; // 定义一个空的deque，且元素类型为int
deque<int> a(n); // 定义一个长度为n，元素类型为int的deque，且每个元素都是0
deque<int> a(n, x); // 定义一个长度为n，元素类型为int，且每个元素都是x的deque
deque<int> a(b); // 定义一个b的拷贝

deque的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.clear(); // 清空a 时间复杂度O(n)
a.push_back(x); // 在a的最后添加一个元素x 时间复杂度O(1)
a.pop_back(); // 删除a的最后一个元素 时间复杂度O(1)
a.push_front(x); // 在a的最前面添加一个元素x 时间复杂度O(1)
a.pop_front(); // 删除a的最前面一个元素 时间复杂度O(1)
a.front(); // 返回a的第一个元素 时间复杂度O(1)
a.back(); // 返回a的最后一个元素 时间复杂度O(1)

deque的遍历

// 下标遍历
for (int i = 0; i < a.size(); i++) {
    cout << a[i] << endl;
}
// 迭代器遍历
for (deque<int>::iterator it = a.begin(); it != a.end(); it++) {
    cout << *it << endl;
}
// C++11的范围for循环 由于部分比赛平台不支持C++11，所以不推荐使用
for (auto x : a) {
    cout << x << endl;
}

由于deque的速度比较慢，所以在比赛中一般不使用deque

set, multiset

基于平衡二叉树（红黑树），动态维护有序序列

set初始化

set<int> a; // 定义一个空的set，且元素类型为int
set<int> a(b); // 定义一个b的拷贝

set的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.clear(); // 清空a 时间复杂度O(n)
a.insert(x); // 在a中插入一个元素x 时间复杂度O(logn)
a.erase(x); // 删除a中值为x的元素 时间复杂度O(logn)
a.erase(it); // 删除a中迭代器为it的元素 时间复杂度O(logn)
a.find(x); // 返回a中值为x的元素的迭代器，如果不存在则返回a.end() 时间复杂度O(logn)
a.count(x); // 返回a中值为x的元素的个数 时间复杂度O(logn)
a.lower_bound(x); // 返回a中第一个大于等于x的元素的迭代器，如果不存在则返回a.end() 时间复杂度O(logn)
a.upper_bound(x); // 返回a中第一个大于x的元素的迭代器，如果不存在则返回a.end() 时间复杂度O(logn)
a.front(); // 返回a的第一个元素 时间复杂度O(1)
a.back(); // 返回a的最后一个元素 时间复杂度O(1)
a.begin(); // 返回a的第一个元素的迭代器 时间复杂度O(1)
a.end(); // 返回a的最后一个元素的迭代器 时间复杂度O(1)

multi_set的操作和set的操作完全一样, 只是multi_set允许有重复元素

map, multimap

基于平衡二叉树（红黑树），动态维护有序序列

map初始化

map<int, int> a; // 定义一个空的map，且元素类型为int和int
map<int, int> a(b); // 定义一个b的拷贝

map的常用操作

a.size(); // 返回a的元素个数 时间复杂度O(1)
a.empty(); // 判断a是否为空 时间复杂度O(1)
a.clear(); // 清空a 时间复杂度O(n)
a.insert(make_pair(x, y)); // 在a中插入一个元素x，且值为y 时间复杂度O(logn)
a.erase(x); // 删除a中键为x的元素 时间复杂度O(logn)
a.erase(it); // 删除a中迭代器为it的元素 时间复杂度O(logn)
a.find(x); // 返回a中键为x的元素的迭代器，如果不存在则返回a.end() 时间复杂度O(logn)
a.count(x); // 返回a中键为x的元素的个数 时间复杂度O(logn)
a.lower_bound(x); // 返回a中第一个大于等于x的元素的迭代器，如果不存在则返回a.end() 时间复杂度O(logn)
a.upper_bound(x); // 返回a中第一个大于x的元素的迭代器，如果不存在则返回a.end() 时间复杂度O(logn)
a.front(); // 返回a的第一个元素 时间复杂度O(1)
a.back(); // 返回a的最后一个元素 时间复杂度O(1)
a.begin(); // 返回a的第一个元素的迭代器 时间复杂度O(1)
a.end(); // 返回a的最后一个元素的迭代器 时间复杂度O(1)
a[x]; // 返回a中键为x的元素的值，如果不存在则插入一个键为x的元素，且值为0 时间复杂度O(logn)
a.at(x); // 返回a中键为x的元素的值，如果不存在则抛出异常 时间复杂度O(logn)

multi_map的操作和map的操作完全一样, 只是multi_map允许有重复元素

unordered_set, unordered_map, unordered_multiset, unordered_multimap 哈希表

不支持自定义比较函数，但是不支持lower_bound, upper_bound, 因为哈希表是无序的
其他操作和set, map, multi_set, multi_map完全一样，只是底层实现不同，哈希表的时间复杂度为O(1)

bitset 压位

bitset的初始化

bitset<100> a; // 定义一个长度为100的bitset
bitset<100> a(string("1111111111")); // 定义一个长度为100的bitset，且值为1111111111
bitset<100> a(0x7fffffff); // 定义一个长度为100的bitset，且值为0x7fffffff
bitset<100> a(a); // 定义一个a的拷贝

bitset的常用操作

a.count(); // 返回a中1的个数 时间复杂度O(n)
a.size(); // 返回a的长度 时间复杂度O(1)
a.any(); // 判断a中是否有1 时间复杂度O(n)
a.none(); // 判断a中是否没有1 时间复杂度O(n)
a.set(); // 将a中所有位都变成1 时间复杂度O(n)
a.set(pos); // 将a中下标为pos的位变成1 时间复杂度O(1)
a.reset(); // 将a中所有位都变成0 时间复杂度O(n)
a.reset(pos); // 将a中下标为pos的位变成0 时间复杂度O(1)
a.flip(); // 将a中所有位取反 时间复杂度O(n)
a.flip(pos); // 将a中下标为pos的位取反 时间复杂度O(1)
a[pos]; // 返回a中下标为pos的位的值 时间复杂度O(1)