STL(Standard Template Library) 即标准模板库
将算法与数据结构分开,又通过迭代器让他们相关联
STL中六大组件：
按初始化,增,删,改,查来进行介绍,有的容器因为其特性没有特定的方法
共有的方法,基于vector容器演示
#include<bits/stdc++.h> //万能头文件,包含算法常用库
using namespace std;
vector<int> s1{ 1,2,3,4,5,6};
vector<int> s2{ 7,8,9,10,11};
//迭代器
//有序的容器都有,end指向最后一个元素的下一个,需要注意
cout <<"begin:" << *(s1.begin()) << " end:" << *(s1.end() - 1)<<endl;
//交换
swap(s1, s2);
//遍历----使用这种语法比较简单
for (const auto x : s1)cout << x << endl;
//比较和赋值
cout << "s1!=s2 : " << (s1 != s2) << endl;
s2 = s1;
cout << "s1==s2 : " << (s1 == s2) << endl;
//大小相关
cout << s1.size() << endl;
cout << s1.empty() << endl;
//清空
s1.clear();
动态数组,支持随机访问和在末尾插入和删除元素；
//初始化
vector<int> s1{ 1,3,4,7,9,3 }; //自定义初始
vector<int> s2(5); //五个元素,初始为零
vector<int> s3(5, 10); //五个元素,初始为10
//增加
s1.push_back(100); //末尾添加
s1.insert(s1.begin() + 3, 99); //中间插入
//删除
s1.pop_back(); //末尾删除
s1.erase(s1.begin() + 1); //删除第2个元素
s1.erase(s1.begin(), s1.end() - 4); //一段清空
//for (int i = 0; i < s1.size(); i++)cout << s1[i]<<endl;
for (auto x : s1)cout << x << endl;
vector<int> a{ 1,34,5,6 };
cout << *(a.begin()) << " " << *(a.end() - 1) << endl; //返回迭代器
cout << a.front() << " " << a.back(); //返回引用
双向链表，支持在任意位置插入和删除元素；
list<int> myList{6,7,8};
//增加
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
myList.push_front(10);
//查找
auto it = find(myList.begin(), myList.end(), 3);
//删除
myList.erase(it);
//修改
it = find(myList.begin(), myList.end(), 1);
*it = 4;
for (const auto x : myList)cout << " " << x;
基于红黑树实现的有序集合
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
set<int> myset;
//增加
myset.insert(1);
myset.insert(3);
myset.insert(2);
//删除
myset.erase(2);
for (it = myset.begin(); it != myset.end(); ++it) cout << *it << " "; cout << "\n\n\n";
//修改
//因为元素是唯一的,修改就删除后再添加就行,不提供特定方法
//查找
it = myset.find(2);
if (it != myset.end()) cout << "element found in set: " << *it << endl;
//输出
set<int>::iterator it;
for (it = myset.begin(); it != myset.end(); ++it) cout << *it << " ";cout << endl;
//交并补
set<int> A = { 1, 2, 3, 4, 5 };
set<int> B = { 4, 5, 6, 7, 8 };
set<int> A_inter_B; // 交集
set<int> A_union_B; // 并集
set<int> A_diff_B; // 差集 A - B
set<int> B_diff_A; // 差集 B - A
set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(A_inter_B, A_inter_B.begin())); // 求交集
set_union(A.begin(), A.end(), B.begin(), B.end(), inserter(A_union_B, A_union_B.begin()));// 求并集
set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(A_diff_B, A_diff_B.begin()));// 求差集 A - B
set_difference(B.begin(), B.end(), A.begin(), A.end(), inserter(B_diff_A, B_diff_A.begin()));// 求差集 B - A
cout << "集合 A：{1, 2, 3, 4, 5}" << endl << "集合 B：{4, 5, 6, 7, 8}" << endl << endl;
cout << "集合 A ∩ B (交集)："; for (auto it = A_inter_B.begin(); it != A_inter_B.end(); ++it) cout << *it << " ";cout << endl;
cout << "集合 A ∪ B (并集)："; for (auto it = A_union_B.begin(); it != A_union_B.end(); ++it) cout << *it << " ";cout << endl;
cout << "集合 A - B (差集)："; for (auto it = A_diff_B.begin(); it != A_diff_B.end(); ++it) cout << *it << " ";cout << endl;
cout << "集合 B - A (差集)："; for (auto it = B_diff_A.begin(); it != B_diff_A.end(); ++it) cout << *it << " ";cout << endl;
}
基于哈希表实现的无序映射表
#include <unordered_map>
unordered_map<string, int> myMap;
//增加
myMap["Alice"] = 25;
myMap["Bob"] = 30;
myMap["Charlie"] = 22;
//删除
if (myMap.erase("Alice") > 0) cout <<"removed from the map" << endl;
//myMap.clear(); //清空
//修改
myMap["Bob"] = 31; cout << "Bob's age is "<<myMap["Bob"] << endl;
//查找
auto it = myMap.find("Bob");
if (it != myMap.end()) cout << "found in the map" << endl;
基于红黑树实现的有序映射表,占用资源更少,增删改查跟unordered_map一样,主要存一些字典数据
可见leetcode 罗马数字转整数
#include<map>
map<char, int> T = { {'I',1},{'V',10},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000} };
基于deque实现的栈；
#include <stack>
stack<int> s;
//增加
s.push(10);
s.push(20);
s.push(30);
//删除
s.pop();
//查询
cout << "栈顶元素为：" << s.top() << endl;
类似于stack
queue<int> myQueue;
//增加
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
//删除 最面的
myQueue.pop();
//查询
cout << myQueue.front()<<" "<<myQueue.back();
双端队列，支持在队列两端进行插入和删除操作；
deque<int> mydeque;
//增加
mydeque.push_front(2);
mydeque.push_front(1);
mydeque.push_front(0);
mydeque.push_back(3);
mydeque.push_back(4);
mydeque.push_back(5);
for (const auto x : mydeque) cout << x << " "; cout << endl;
//删除
mydeque.pop_front();
mydeque.pop_back();
//查询
cout << mydeque.front() << " "<< mydeque.back() << endl;
algorithm
//普通数组
int arr[3]{2,3,1};
bool cmp(int a, int b){return a > b;}
sort(arr,arr+3,cmp);
//vector数组
vector<int> vec{ 1,3,5,3,4 };
sort(vec.begin(),vec.end());
//逆序 reverse
reverse(arr,arr+3);
sort(arr, arr + 3, greater<int>() );
string s{"234351"};
sort(&s[0], &s[6], greater<int>() );
常用比较函数
//常用比较函数
greater<type>();//降序
less<type>();//升序
greater_equal<type>();
less_equal<type>();
//或者使用lamda函数
sort(v.begin(), v.end(), [](int a, int b) -> bool { return a % 2 < b % 2; });
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v{ 1, 2, 3, 5, 7, 8, 10 };
auto lb = std::lower_bound(v.begin(), v.end(), 5);
std::cout << "Lower bound of 5: " << *lb << '\n'; // 5
auto ub = std::upper_bound(v.begin(), v.end(), 5);
std::cout << "Upper bound of 5: " << *ub << '\n'; // 7
}
c++17之后
#include <numeric>
int x = 24, y = 36;
int gcd_xy = gcd(x, y); //12
int lcm_xy = lcm(x, y);//72
都用accumulate实现
#include <numeric>
vector<int> numbers{ 1, 2, 3, 4, 5 };
int sum = accumulate(numbers.begin(), numbers.end(), 0); // 15
int product = accumulate(numbers.begin(), numbers.end(), 1, multiplies<>()); // 120
printf("%d %d", sum, product);
迭代器(iterator)是一种用于访问容器中元素的对象，类似于一个指针。让我们不用管内部结构,简单统一的访问,如引用(*iter)、递增(iter++)、递减(iter–)
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
vector<int>::iterator it;
for (it = v.begin(); it != v.end(); ++it)
cout << *it << " ";
cout << endl;
}