1.11 C++ STL

一、STL 容器

序列容器：vector、list、forward_list、deque、array、string
关联式容器（自动排序、基于红黑树）：set、map、multiset、multimap
无序关联式容器（基于哈希表）：unordered_set、unordered_map、unordered_multiset、unordered_multimap
适配器容器（是对其他容器的封装）：stack、queue、priority_queue

二、STL 算法

std::vector<int> v {1, 2, 3, 4};
auto it = std::find(v.begin(), v.end(), 3);  // 返回迭代器
if (it != v.end()) std::cout << "Found at: " << it - v.begin();

std::sort(v.begin(), v.end());  // 默认升序
std::sort(v.begin(), v.end(), std::greater<int>());  // 降序

// 1、优先使用 lambda
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

// 2、使用 仿函数
struct Compare {
    bool operator()(int a, int b) const {
        return a < b;  // 升序排序
    }
};
std::sort(v.begin(), v.end(), Compare());

// 3、自定义比较函数
bool compare(int a, int b) {
    return a > b;  // 降序排序
}
std::sort(v.begin(), v.end(), compare);

三、所有容器共有的核心方法

方法	作用	示例（以`vector<int>`为例）
`empty()`	判断容器是否为空	`if (v.empty()) {...}`
`size()`	返回元素数量	`int n = v.size();`
`clear()`	清空容器	`v.clear();`
`swap(c)`	交换两个容器的内容	`v1.swap(v2);`
`begin()`/`end()`	返回迭代器（含const版本）	`auto it = v.begin();`

四、vector

vector<int> a;
vector<int> a(n);
vector<int> a(n,1);
vector<int> a({1,2,3})

v.front() / v.back();
v.push_back(data) / v.emplace_back(data) / v.pop_back();
v.insert(iterator, data) / v.erase(iterator) / v.erase(first, last); 
// 下标 -> 迭代器：v.begin() + index; 
// 迭代器 -> 下标：it - v.begin();

五、string

//1.
string str1; //生成空字符串
//2.
string str2("123456789"); //生成"1234456789"的复制品 
//3.
string str3("12345", 0, 3);//结果为"123" ，从0位置开始，长度为3
//4.
string str4("123456", 5); //结果为"12345" ，长度为5
//5.
string str5(5, '2'); //结果为"22222" ,构造5个字符'2'连接而成的字符串
//6.
string str6(str2, 2); //结果为"3456789"，截取第三个元素（2对应第三位）到最后

// 支持比较运算符：<、<=、>、>=、==、!=；会按字典顺序进行比较;
// 支持 + 运算符：可以进行字符串拼接;

// 新增插入
s.append(str);
// 新增删除
s.erase(ite, len);
// 新增类型转换
stoi(s), stoll(s), stod(s), stold(s);
// 新增分割
s.substr(ite, n);
// 新增查找
s.find("abc"); 返回位置索引，没找到返回 -1；
s.find(char, pos) 例：s.find('i',6);

六、deque：可用 sort 排序

d.push_back(ele)、d.push_front(ele)将元素 ele插入队尾、队首
d.pop_back()、d.pop_front()将队尾元素删除、将队首元素删除
d.front()返回队首元素
d.back()返回队尾元素

七、stack：不可以用 sort 排序

s.push(ele);
s.pop();
s.top();

八、 queue：不可用 sort 排序

q.push(ele);
q.pop();
q.front();
q.back();

九、priority_queue 优先队列：没有 clear 方法

priority_queue<int> q1; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, less<int> > q2; // 大根堆, 每次取出的元素是队列中的最大值，同第一行
priority_queue<int, vector<int>, greater<int> > q3; // 小根堆, 每次取出的元素是队列中的最小值

p.push(ele)；
p.pop()；
p.top()；

十、map（查找效率 O(log n)）

mp.erase(it) / mp.erase(key);
mp.insert({key, value});
mp.find(key); // 返回迭代器
mp.count(key); // 返回 0 或 1

十一、set

与 map 用法一样

十二、pair 二元组

//头文件
#include<utility>

//1.初始化定义
pair<string, int> p("wangyaqi",1);//带初始值的
pair<string, int> p;//不带初始值的

//2.赋值
p = {"wang", 18};
p = make_pair("wang", 18);
p = pair<string, int>("wang", 18);

//定义结构体数组
pair<int,int> p[20];
for(int i = 0; i < 20; i++) {
    //和结构体类似，first代表第一个元素，second代表第二个元素
    cout << p[i].first << " " << p[i].second;
}