STL汇总

STL容器

参考：C++ STL总结 | 行码棋 (wyqz.top)

vector：动态数组

• 顺序结构，允许随机访问
• 插入、删除操作效率低，查询效率高

代码	含义
c.front()	返回第一个数据O(1)
c.back()	返回数组中的最后一个数据 O(1)
c.pop_back()	删除最后一个数据O(1）
c.push_back(element)	在尾部加一个数据O(1)
c.size()	返回实际数据个数（unsigned类型）O(1)
c.clear()	清除元素个数O(N)，N为元素个数
c.resize(n, v)	改变数组大小为n,n个空间数值赋为v，如果没有默认赋值为0
c.insert(it, x)	向任意迭代器it插入一个元素x ，O(N)
例：c.insert(c.begin() + 2,-1)	将-1插入c[2]的位置
c.erase(first,last)	删除[first,last)的所有元素，O(N)
c.begin()	返回首元素的迭代器（通俗来说就是地址）O(1)
c.end()	返回最后一个元素后一个位置的迭代器（地址）O(1)
c.empty()	判断是否为空，为空返回真，反之返回假 O(1)

vector初始化

vector的初始化常借助resize和assign

resize的不指定value时的初始值如下：

int -- 0

string -- ""

bool -- false

double -- 0.0

时间复杂度\(O(n)\)

vector<int > v = {1,2,3};

//resize不会改变原有数据，常用于初始化和拓展
v.resize(5);       // 大小调整为5, 元素值默认 -> {1,2,3,0,0}
v.resize(7, 10);   // 大小调整为7，每个元素初始化为10 -> {1,2,3,0,0,10,10}

//assign会直接覆盖原有数据
v.assign(5, 10);  // 用5个10填充v -> {10,10,10,10,10}

vector复制操作

C++中Vector的所有赋值方式都是深拷贝

//1：赋值运算符
v2 = v1;  // 拷贝 vec1 到 vec2
//2：拷贝构造函数
vector<int> v2(v1);
//3：assign
v2.assign(vec1.begin(), vec1.end());

stack：栈

• 不允许sort排序

代码	含义
s.push(ele)	元素ele入栈，增加元素 O(1)
s.pop()	移除栈顶元素 O(1)
s.top()	取得栈顶元素（但不删除）O(1)
s.empty()	检测栈内是否为空，空为真 O(1)
s.size()	返回栈内元素的个数 O(1)

• 数组模拟栈

通过一个数组对栈进行模拟，一个存放下标的变量top模拟指向栈顶的指针。

一般来说单调栈和单调队列写法均可使用额外变量 tt 或 hh 来进行模拟

特点： 比STL的stack速度更快，遍历元素方便

int sta[100]; // 栈 从左至右为栈底到栈顶
int top = -1; // tt 代表栈顶指针,初始栈内无元素，tt为-1
for(int i = 0; i <= 5; ++i) {
    //入栈 
    sta[++top] = i;
}
// 出栈
int top_element = sta[top--]; 

queue：队列

• 不允许sort排序

代码	含义
q.front()	返回队首元素 O(1)
q.back()	返回队尾元素 O(1)
q.push(element)	尾部添加一个元素element 进队O(1)
q.pop()	删除第一个元素 出队 O(1)
q.size()	返回队列中元素个数，返回值类型unsigned int O(1)
q.empty()	判断是否为空，队列为空，返回true O(1)

• 数组模拟队列

使用q[]数组模拟队列

rear表示队尾元素的下标，初始值为0

front表示队首元素的下标，初始值为0

const int N = 1e5 + 5;
int q[N];
int main() {
    int hh = 0,rear = 0;
//   入队 
    q[rear++] = 1;
    q[rear++] = 2; 
//    出队 
    while(front != rear) {
        int t = q[front++];
        cout<<t<<endl;
    }
    return 0;
 } 

deque：双端队列

• 和vectot一样，可以随机访问，也可以sort排序

代码	含义
push_back(x)/push_front(x)	把x插入队尾后 / 队首 O(1)
back()/front()	返回队尾 / 队首元素 O(1)
pop_back() / pop_front()	删除队尾 / 队首元素 O(1)
erase(iterator it)	删除双端队列中的某一个元素
erase(iterator first,iterator last)	删除双端队列中[first,last)中的元素
empty()	判断deque是否空 O(1)
size()	返回deque的元素数量 O(1)
clear()	清空deque

priority_queue：优先队列（堆）

代码	含义
q.top()	访问队首元素 O(1)
q.push()	入队 O(logN)
q.pop()	堆顶（队首）元素出队 O(logN)
q.size()	队列元素个数 O(1)
q.empty()	是否为空 O(1)
注意没有clear()！	不提供该方法
优先队列只能通过top()访问队首元素（优先级最高的元素）

• 大小根堆的设置方法，也可以自定义比较函数

priority_queue<int> pq; // 默认大根堆, 即每次取出的元素是队列中的最大值 
priority_queue<int, vector<int>, greater<int>> q; // 小根堆, 每次取出的元素是队列中的最小值
priority_queue<int, vector<int>, less<int>> q //大根堆
    
struct cmp1 { bool operator()(int x, int y) { return x > y; } }; 
struct cmp2 { bool operator()(const int x, const int y) { return x < y; } }; priority_queue<int, vector<int>, cmp1> q1; //小根堆 
priority_queue<int, vector<int>, cmp2> q2; // 大根堆

set：集合（红黑树）

代码	含义
s.begin()	返回set容器的第一个元素的地址（迭代器）O(1)
s.end()	返回set容器的最后一个元素的下一个地址（迭代器）O(1)
s.rbegin()	返回逆序迭代器，指向容器元素最后一个位置O(1)
s.rend()	返回逆序迭代器，指向容器第一个元素前面的位置O(1)
s.clear()	删除set容器中的所有的元素,返回unsigned int类型O(N)
s.empty()	判断set容器是否为空O(1)
s.insert()	插入一个元素 O（log n）
s.size()	返回当前set容器中的元素个数O(1)
erase(iterator)	删除定位器iterator指向的值
erase(first,second）	删除定位器first和second之间的值
erase(key_value)	删除键值key_value的值
查找
s.find(element)	查找set中的某一元素，有则返回该元素对应的迭代器，无则返回s.end() O(logN)
s.count(element)	返回set中的元素出现的个数，由于set中无重复元素，只能返回0 和 1。此函数相当于查询element是否出现 > O(logN)
s.lower_bound(k)	返回大于等于k的第一个元素的迭代器O(logN)
s.upper_bound(k)	返回大于k的第一个元素的迭代器O(logN)

map：映射（红黑树）

• 优点：

  • map元素有序（这是map最大的优点，其元素的有序性在很多应用中都会简化很多的操作）；

  • 其红黑树的结构使得map的很多操作都可在O(logn)下完成；

  • map的各项性能较为稳定，与元素插入顺序无关；

  • map支持范围查找。

• 缺点：

  • 占用的空间大：红黑树的每一个节点需要保存其父节点位置、孩子节点位置及红/黑性质，因此每一个节点占用空间大。

  • 查询平均时间不如unordered_map。

代码	含义
mp.find(key)	返回键为key的映射的迭代器存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end() O(logN)
mp.erase(it)	删除迭代器对应的键和值O(1)
mp.erase(key)	根据映射的键删除键和值 O(logN)
mp.erase(first,last)	删除左闭右开区间迭代器对应的键和值 O(last−first)
mp.size()	返回映射的对数O(1)
mp.clear()	清空map中的所有元素O(N)
mp.insert()	插入元素，插入时要构造键值对
mp.empty()	如果map为空，返回true，否则返回false
mp.begin()	返回指向map第一个元素的迭代器（地址）
mp.end()	返回指向map尾部的迭代器（最后一个元素的下一个地址）
mp.rbegin()	返回指向map最后一个元素的迭代器（地址）
mp.rend()	返回指向map第一个元素前面(上一个）的逆向迭代器（地址）
mp.count(key)	查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0
mp.lower_bound()	返回一个迭代器，指向键值>= key的第一个元素
mp.upper_bound()	返回一个迭代器，指向键值> key的第一个元素

unordered_map：哈希表

unorder_map是链式存储法的哈希表，每个key值对应的链表，叫做一个“桶”

• 优点：
  • 查询速度快，平均性能接近于常数时间O(1)；
• 缺点：
  • 元素无序；
  • unordered_map相对于map空间占用更大，且其利用率不高；
  • 查询性能不太稳定，最坏时间复杂度可达到O(n)。

代码	含义
mp.begin()	返回指向map第一个元素的迭代器（地址）
mp.end()	返回指向map尾部的迭代器（最后一个元素的下一个地址）
mp.empty()	空则返回true，非空返回false
mp.size()	返回哈希表的大小
mp.at(key)	根据key值，查找value，若不存在，抛出异常
mp.find(key)	存在该key值则返回该位置上的迭代器，否则返回mp.end()
mp.clear()	清空表
mp.find(key)	存在该key值则返回该位置上的迭代器，否则返回mp.end()
mp.count(key)	该key值对应value存在，返回1，否则为0
mp.emplace(key)	向容器中添加新键值对（旧值不会被新值覆盖），效率对比insert()高
mp.insert(pair)	向容器中添加新键值对（旧值被新值覆盖）

• mp[key] = value 和 insert（pair）都会覆盖旧value，而emplace不会。

string：字符串

• 运算符特性：

1.支持比较运算符（>,>=,<,<=,==,!=）。支持string与C-string的比较（如 str < "hello"）。

在使用>,>=,<,<=这些操作符的时候是根据“当前字符特性”将字符按 字典顺序 进行逐一得 比较。

字典排序靠前的字符小， 比较的顺序是从前向后比较，遇到不相等的字符就按这个位置上的两个字符的比较结果确定两个字符串的大小（前面减后面）。

2.支持+运算符，代表拼接字符串：string字符串可以拼接，通过”+”运算符进行拼接。

string s1 = "123";
string s2 = "456";
string s = s1 + s2;
cout << s;   //123456

• 获取字符串长度

代码	含义
s.size()和s.length()	返回string对象的字符个数，他们执行效果相同
s.max_size()	返回string对象最多包含的字符数，超出会抛出length_error异常
s.capacity()	重新分配内存之前，string对象能包含的最大字符数

• 插入

代码	含义
s.push_back()	在末尾插入
s.insert(pos,str)	在pos位置后插入str
s.append(str)	在s字符串结尾添加str字符串

• 删除

代码	含义
erase(iterator p)	删除字符串中p所指的字符
erase(iterator first, iterator last)	删除字符串中迭代器区间[first,last)上所有字符
erase(pos, len)	删除字符串中从索引位置pos开始的len个字符
clear()	删除字符串中所有字符

• 字符替换

代码	含义
s.replace(pos,n,str)	把当前字符串从索引pos开始的n个字符替换为str
s.replace(pos,n,n1,c)	把当前字符串从索引pos开始的n个字符替换为n1个字符c
s.replace(it1,it2,str)	把当前字符串[it1,it2)区间替换为str it1 ,it2为迭代器哦

• 大小写转换

代码	含义
tolower(s[i])	转换为小写
toupper(s[i])	转换为大写

• 分割

代码	含义
s.substr(pos,n)	截取从pos索引开始的n个字符

• 查找

代码	含义
s.find (str, pos)	在当前字符串的pos索引位置（默认为0）开始，查找子串str，返回找到的位置索引，-1表示查找不到子串
s.find (c, pos)	在当前字符串的pos索引位置（默认为0）开始，查找字符c，返回找到的位置索引，-1表示查找不到字符
s.rfind (str, pos)	在当前字符串的pos索引位置开始，反向查找子串s，返回找到的位置索引，-1表示查找不到子串
s.rfind (c, pos)	在当前字符串的pos索引位置开始，反向查找字符c，返回找到的位置索引，-1表示查找不到字符
s.find_first_of (str, pos)	在当前字符串的pos索引位置（默认为0）开始，查找子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_first_not_of (str,pos)	在当前字符串的pos索引位置（默认为0）开始，查找第一个不位于子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_last_of(str, pos)	在当前字符串的pos索引位置开始，查找最后一个位于子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_last_not_of ( str, pos)	在当前字符串的pos索引位置开始，查找最后一个不位于子串s的字符，返回找到的位置索引，-1表示查找不到子串

sort：排序

O(NlogN)

• 对数组正常升序排序

sort(a , a + n);
vector<int> v; // vector数组定义
sort(v.begin(), v.end());

• 使用第三个参数，进行降序排序

sort(a, a + n, greater<int>());
sort(a, a + n, less<int>());

• 自定义排序规则

bool cmp(node a, node b) {
    return a.x > b.x;
}
sort(node, node + n, cmp); 
// 只接受以函数为形式的自定义排序规则，无法接受以结构体为形式的自定义排序规则

• stable_sort使用方法和sort一样，但排序时不会改变相等元素的相对位置，是稳定排序

STL函数

有序序列的二分查找

45 正确区分count、find、binary_search、lower_bound、upper_bound和equal_range_find lowbound-CSDN博客

1.binary_search

找得到返回1，找不到返回0

int a[] = {12, 45, 3, 98, 21, 7};
sort(a, a+6);
cout << "result:" << binary_search(a, a+6, 12) << endl;//1
cout << "result:" << binary_search(a, a+6, 77) << endl;//0

如果sort中使用了自定义排序规则，binary_search里一样要引用该参数

结构体写法：

struct Rule {
    bool operator()(const int & a1, const int & a2) const{
        return a1%10 < a2%10;
    }
};
int a[] = {12, 45, 3, 98, 21, 7};
sort(a, a+6, Rule());
cout << "result:" << binary_search(a, a+6, 8, Rule()) << endl;
// 注意：这里查找的是 x % 10 == 8, 而不是 x == 8；

函数写法：

bool cmp(const int & a1, const int & a2) {
	return a1%10 < a2%10;
};

int a[] = {12, 45, 3, 98, 21, 7};
sort(a, a+6, cmp);
cout << "result:" << binary_search(a, a+6, 8, cmp) << endl;

2.lower_bound、upper_bound

使用方法和bianry_search一样，lower_bound返回的是一个 >= 查找元素的迭代器/指针，upper_bound为 > 。

bool cmp(const int & a1, const int & a2) {
	return a1%10 < a2%10;
};

int a[] = {12, 45, 3, 98, 21, 7};
sort(a, a+6, cmp);
cout << "result:" << *lower_bound(a, a+6, 8, cmp) << endl;

getline

读入字符串，遇空格，回车结束

string s; cin >> s;

读入一行字符串（包括空格），遇回车结束

string s; getline(cin, s);

注意: getline(cin, s)会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或cin.get()

错误读取：

int n;
string s;
cin >> n;
getline(cin, s); //此时读取相当于读取了前一个回车字符

正确读取：

int n;
string s;
cin >> n;
getchar(); //cin.get()
getline(cin, s);//可正确读入下一行的输入

set_union/intersection/difference：并集/交集/差集

set_union, set_intersection,set_difference：

复杂度：O(N+M)

注意：两个集合必须为有序集合，所以下面演示代码使用了排序。

vector容器可以替换成set容器，因为set自动会对元素进行排序。

函数的参数有五个，前两个为第一个容器的首尾迭代器，第三四个为第二个容器的首尾迭代器，最后一个为插入位置，即将结果插入到哪个地址之后。

vector<int> a = {4, 5, 2, 1, 8}, b = {5, 3, 8, 9, 2};
sort(a.begin(), a.end()); // 1 2 4 5 8
sort(b.begin(), b.end()); // 2 3 5 8 9
vector<int> c, d, e;
// a并b：1 2 3 4 5 8 9
set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()));
// a交b：2 5 8
set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(d, d.begin()));
// a差b： 1 4
set_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(e, e.begin()));

reverse：翻转序列

复杂度： O(N)

reverse(beg,end)

例如：

vector<int > v = {1,2,3,4,5};//1,2,3,4,5
reverse(v.begin(),v.end());
//v == 5,4,3,2,1

unique：删除重复元素

unique(beg, end)

复杂度： O(N)

用于去除相邻的重复元素

unique函数返回一个指向去重后的末尾指针，但是数组size没有改变，需要删除操作

同样兼容c数组

vector<int> v = {1,1,1,2,2,2,3,3,3};
sort(v.begin(),v.end());
auto it = unique(v.begin(),v.end());
//v == 1，2，3，2，2，2，3，3，3
v.erase(it,v.end());
//v == 1，2，3

next_permutation：全排列函数

复杂度： O(N)

next_permutation：如果数组存在下一个全排列，返回 bool = 1，并移动到下一位，否则返回0

perv_permutaion是前者的逆操作

这两个函数同样兼容c数组，操作与vector相同

vector<int> v = {1,2,3,4,5};
while(next_permutation(v.begin(),v.end())){
	int len = v.size();
	for(int i = 0 ; i < len ; i ++){
		cout<<v[i]<<" ";
	}
	cout<<endl;
}

auto

auto可以根据等号后面的值来自动适配变量类型，也可以简化遍历书写

常见用法：

for(auto x : range) // 拷贝元素 for(auto &&x : range)// 修改元素 for(const auto &x : range) // 只读元素（无法修改）

vector<int > v = {1,2,3,4,5,6,7};
for(auto i : v){
	i = 2*i;
	cout<<i<<' ';
}
cout<<endl;
//2 4 6 8 10 12 14
for(vector<int >::iterator it = v.begin(); it != v.end() ; it ++){
	cout<<*it<<" ";
}
//auto：
//1 2 3 4 5 6 7
//auto &&：
//2 4 6 8 10 12 14
//const auto &,报错