STL介绍1：vector、pair、string、queue、map

一、vector：变长数组、倍增思想 1.常用函数

size()：返回元素个数

empty()：返回是否为空

clear()：清空

front() / bcak()

push_back() / pop_back()：尾部插入和删除

2.存储方式 #include<iostream> #include<vector> using namespace std; int main(){ vector<int> a(3, 9); // 长度为3，每个元素的值为9 for(auto x : a) cout << x << '\n'; a.clear(); // 清空元素 if(a.empty() == true) printf("Empty\n"); // 判空 else printf("Not Empty\n"); return 0; }  3.三种遍历方式 #include<iostream> #include<vector> using namespace std; int main(){ vector<int> a; for(int i = 0; i < 10; i++) a.push_back(i); for(int i = 0; i < a.size(); i++) cout << a[i] << ' '; cout << '\n'; for(vector<int>::iterator i = a.begin(); i!=a.end();i++) cout << *i << ' '; // 迭代器遍历，类似于指针 cout << '\n'; for(auto x : a) cout << x << ' '; // C++范围遍历 return 0; } 4.支持比较运算（按照字典序） #include<iostream> #include<vector> using namespace std; int main(){ vector<int> a(4,3), b(3,4); if(a < b) cout << "a < b" << ' '; return 0; } 二、pair<int, int>：存储二元组 1.使用方法

first, 第一个元素 second, 第二个元素 支持比较运算，以first为第一关键字，以second为第二关键字（字典序） 

2.示例  #include<iostream> #include<cstring> using namespace std; int main(){ pair<int, string> p1, p2; //p.first // first是第一个元素 //p.second // seconds是第二个元素 p1 = make_pair(10,"haha"); p2 = {20,"xixi"}; cout << p1.first << ' ' << p1.second << '\n'; cout << p2.first << ' ' << p2.second << '\n'; return 0; } 三、string：字符串 1.使用方法

size() / length()  返回字符串长度 empty() clear() substr(起始下标，(子串长度))  返回子串 c_str()  返回字符串所在字符数组的起始地址

2.示例 #include<iostream> #include<cstring> using namespace std; int main(){ string a = "abc"; a += "def"; a += "g"; cout << a <<'\n'; cout << a.substr(1,3) << '\n'; // 返回下标为1~3的字串 printf("%s\n",a.c_str()); return 0; }  四、queue：先进先出的队列 1.使用方法

size() empty() push()  向队尾插入一个元素 front()  返回队头元素 back()  返回队尾元素 pop()  弹出队头元素

2.示例 #include<iostream> #include<queue> using namespace std; int main(){ queue<int> q; for(int i = 0; i < 10; i++){ q.push(i); } for(int i = q.front(); i <= q.back(); i++){ cout << i <<' '; } cout << '\n'; q.pop(); // 弹出队头元素 cout << q.front(); return 0; } 五、map：映射 1.定义方式 map<key, value> mp：键key是映射前的类型，值value是映射后的类型 #include<iostream> #include<map> using namespace std; int main(){ map<int, char> mp; mp[1] = 'A'; mp[2] = 'B'; mp[3] = 'C'; mp[4] = 'D'; for(int i = 1; i <= 4; i++){ cout << mp[i] << ' '; } cout << '\n'; for(auto x = mp.begin(); x != mp.end(); x++){ // 迭代器访问 cout << x->first << ' ' << x->second << '\n'; // first可以当作key, second可以当作value } cout << "映射对数：" << mp.size() << ' '; return 0; }  2.find(key)：查找键为key的映射 #include<iostream> #include<map> using namespace std; int main(){ map<int, char> mp; mp[1] = 'A'; mp[2] = 'B'; mp[3] = 'C'; mp[4] = 'D'; auto x1 = mp.find(1); auto x2 = mp.find(4); cout << x1->first << ' ' << x1->second << '\n'; cout << x2->first << ' ' << x2->second << ' '; return 0; } 3.erase()：删除单个元素或是区间内所有元素 #include<iostream> #include<map> using namespace std; int main(){ map<int, char> mp; mp[1] = 'A'; mp[2] = 'B'; mp[3] = 'C'; mp[4] = 'D'; auto x = mp.find(1); // 迭代器删除方法，时间复杂度为O(1) mp.erase(x); // 删除1 A mp.erase(2); // key删除方法，时间复杂度为O(logN) for(auto x = mp.begin(); x != mp.end(); x++){ cout << x->first << ' ' << x->second << '\n'; } return 0; } 4.lower_bound() 和 upper_bound()

lower_bound(Key key)：

功能：返回第一个大于或等于key的元素的迭代器。

时间复杂度：O(log n)。

upper_bound(Key key)：

功能：返回第一个大于key的元素的迭代器。

时间复杂度：O(log n)。

#include <iostream> #include <map> using namespace std; int main() { map<int, string> myMap = { {1, "Apple"}, {3, "Banana"}, {5, "Cherry"} }; auto x1 = myMap.lower_bound(2); // 找到第一个 >=2的键，即3 cout << "lower_bound(2): " << x1->second << '\n'; // 输出 Banana auto x2 = myMap.upper_bound(3); // 找到第一个 >3的键，即5 cout << "upper_bound(3): " << x2->second << '\n'; // 输出 Cherry return 0; }