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 Amp.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的键，即3cout << "lower_bound(2): " << x1->second << '\n'; // 输出 Bananaauto x2 = myMap.upper_bound(3); // 找到第一个 >3的键，即5cout << "upper_bound(3): " << x2->second << '\n'; // 输出 Cherryreturn 0;
}