STL学习

STL基础

STL从广义上分为：容器，算法，迭代器
容器和算法之间通过迭代器进行无缝连接

STL 的六大组件

STL六大组件分别是：容器、算法、迭代器、仿函数、适配器、空间适配器

容器：各种数据结构，如vector，list、deque、set、map等用来存放数据
算法：各种常用的算法，如sort、find等
迭代器：扮演了容器与算法之间的胶合剂
仿函数：行为类似函数，可以作为算法的某一种策略
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
空间适配器：负责空间的配置与管理

容器分为序列式容器和关联式容器

序列式容器：强调值的排序，序列式容器中的每一个元素均有固定的位置
关联式容器：二叉树结构，个元素之间没有严格的物理上的顺序关系

算法：解决问题的方法，有限的步骤，解决逻辑或数学上的问题
算法分为质变算法和非质变算法

质变算法：指质变过程中会更改区间内的元素的内容
非质变算法：在运算过程中不会更改区间内的元素内容

迭代器：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方法
每个容器都有自己的专属迭代器
迭代器的使用类似于指针

vector

vector初始化

int main() {// v1 是一个元素类型为 int 的空 vectorvector<int> v1;// 使用 v1 中所有元素初始化 v2vector<int> v2(v1);vector<int> v2 = v1;// v3 中包含了 3 个值为 1 的元素vector<int> v3(3, 1);// v3 中包含了 4 个默认值初始化的元素vector<int> v4(4);//使用2, 3, 4初始化 v5vector<int> v5{ 2, 3, 4 };// 二维数组初始化vector<vector<int>> v;
}

vector常用操作

int main() {vector<int> v;// 如果 v 为空则返回 true，否则返回 falsev.empty();// 返回 v 中元素的个数v.size();// 向 vector 的尾端添加值为 1 的元素。// 注意：vector 不支持 push_front 操作。v.push_back(1);// 返回 v 中第 3 个位置上元素的引用，不能用下标操作添加元素int n = v[3];// 删除尾元素，返回void。vector同样 不支持 pop_front 操作。// 若想在同时弹出元素的值，就必须在执行弹出之前保存它（可以使用 v.back()）。v.pop_back();// 返回 v 中最后一个元素的引用int m = v.back();// 返回 v 中第一个元素的引用int n = v.front();vector<int> a{ 2, 0, 2, 2, 0, 3, 0, 9 };a.resize(15);  //修改容器大小，变长了用0填充，短了删除尾部元素a.resize(15,100);  // 变长用100填充int n = a.capacity();   //返回容量大小
}

遍历vector

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;void myPrint(int val) {cout << val << endl;
}int main() {// 创建vector容器vector<int> v;// 向容器的末尾插入数值v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);// v.begin()指向第一个元素的迭代器vector<int>::iterator itBegin = v.begin();// v.end()指向最后一个元素的下一个元素的迭代器vector<int>::iterator itEnd = v.end();// 遍历vwhile (itBegin != itEnd) {cout << *itBegin << endl;itBegin++;}// 遍历容器中的元素，并将元素作为参数传递给myPrint函数for_each(v.begin(), v.end(), myPrint);
}

插入数据

int main(void)
{vector<int> a{ 1, 2, 3, };auto it1 = a.begin();  // 返回一个迭代器类型，一般来说我们并不关心迭代器具体的数据类型auto it2 = a.insert((it1 + 1), { 6, 7, 8 });  // 利用迭代器在第二个元素之前插入数据
}

删除元素

int main(void)
{vector<int> a{ 1, 2, 3, };auto it1 = a.begin();  // 返回一个迭代器类型，一般来说我们并不关心迭代器具体的数据类型auto it2 = a.erase(it1 + 1);  // 删除元素 2,返回值为元素删除后被删除元素的当前位置的值
}

容器嵌套

int main() {// 创建vector容器vector<vector<int>> v;vector<int> v1;vector<int> v2;vector<int> v3;vector<int> v4;for (int i = 0; i < 4; i++) {v1.push_back(10);v2.push_back(20);v3.push_back(30);v4.push_back(40);}v.push_back(v1);v.push_back(v2);v.push_back(v3);v.push_back(v4);for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {cout << *vit << endl;}}
}

算法操作

int main(void)
{vector<int> a{ 2, 0, 2, 2, 0, 3, 0, 9 };sort(a.begin(), a.end());  //排序// 将重复的内容放在末尾，然后删除末尾元素auto end_unique = unique(a.begin(), a.end());a.erase(end_unique, a.end());// 将送其中的元素进行翻转逆序reverse(a.begin(), a.end());// 找到最大值和最小值auto it = max_element(a.begin(), a.end());auto it = min_element(a.begin(), a.end());for (int i : a)cout << i << " ";// 互换容器vector<int> b;a.swap(b);  //将a和b进行互换// 预留100个空间，预留的空间不可访问a.reserve(100);return 0;
}

string

字符串初始化

int main() {// 默认构造string s1;const char* str = "zhangsan";// 通过char数组构造string s2(str);// 通过拷贝构造string s3(s2);// 初始化s4为10个astring s4(10, 'a');
}

字符串幅值

int main() {string s1= "zhangsan";string s2;// 通过另一个字符串进行赋值s2 = s1;string s3;// 赋值一个字符s3 = 'a';// 通过assign赋值s3.assign("lisi");// 将字符串lisishiren的前五个给s3赋值s3.assign("lisishiren", 5);// 将s2的值赋给s3s3.assign(s2);//给s3赋值5个xs3.assign(5,'x');
}

字符串拼接

int main() {string s1= "zhangsan";string s2 = "lisi";// 将s2拼接到s1后面s1 += s2;s1.append(s2);// 追加一个字符s1 += 'c';//追加一个字符串s1 += "lisi";s1.append("lpve");// lpvedfad的前四个字符追加到s1s1.append("lpvedfad",4);//  截取lpvedfad的第4个字符开始的三个字符s1.append("lpvedfad",4,3);
}

查找和替换

字符串比较

int main() {string s1= "zhangsan";string s2 = "lisi";// 比较s1和s2的大小，n=0相等，n<0则s1小，n>0则s1大int n =  s1.compare(s2);
}

字符存取

int main() {string s1= "zhangsan";// 获取第三个字符s1[3];s1.at(3);// 修改第三个字符s1[3]='x';s1.at(3) = 'x';
}

字符插入和删除

int main() {string s1= "zhangsan";// 在位置1插入111s1.insert(1, "111");// 在位置1后面删除三个字符s1.erase(1, 3);
}

获取字串

int main() {string s1= "zhangsan";// 从第一个字符起截取三个字符s1.substr(1, 3);}

deque

deque是一个双向队列（double-ended queue），可以在队列的两端进行元素的插入和删除操作。
deque的特点是可以在队列的两端进行元素的操作，并且可以高效地在队列的任意位置进行元素的插入和删除操作

//deque的定义 deque<int>d1; //定义一个储存数据类型为int的双端队列d1 push_back()//在队列的尾部插入元素。emplace_front()//与push_front()的作用一样 push_front()//在队列的头部插入元素。emplace_back()//与push_back()的作用一样 pop_back()//删除队列尾部的元素。pop_front()//删除队列头部的元素。back()//返回队列尾部元素的引用。front()//返回队列头部元素的引用。clear()//清空队列中的所有元素。empty()//判断队列是否为空。size()//返回队列中元素的个数。begin()//返回头位置的迭代器end()//返回尾+1位置的迭代器rbegin()//返回逆头位置的迭代器 rend()//返回逆尾-1位置的迭代器 insert()//在指定位置插入元素 erase()//在指定位置删除元素 

list

list容器的底层数据结构为带头双向循环链表，这使得 list的元素可以存储在非相邻的内存中
list 在插入删除元素方面很有优势，在列表的任意位置进行插入和删除操作的时间复杂度为O(1)
不能直接通过位置(下标)来直接访问元素，想要访问list的某个元素，必须从list的一端（或已知位置）迭代到该元素
list还需要额外的存储空间来储存前一个元素和后一个元素的链接信息。
list优点

高效的插入和删除：由于std::list是基于带头双向循环链表实现的，插入和删除操作在任意位置都具有常数时间复杂度O(1)，不需要移动其他元素。这使得std::list在需要频繁插入和删除元素的场景下非常高效。
稳定的迭代器：在std::list中进行插入和删除操作不会使得迭代器失效。这意味着在插入或删除元素后，仍然可以继续使用之前获取的迭代器进行遍历和操作。

list的缺点

低效的随机访问
占用额外内存
迭代器不支持指针算术：std::list的迭代器不支持指针算术运算，无法像指针那样直接进行加减操作，这限制了一些操作的灵活性

list构造

list<int> str_a; list<int> lt2(10, 2); //构造含有10个2的int类型容器list<int> lt3(lt2); //拷贝构造int类型的lt2容器的复制品string s("hello world");list<char> lt4(s.begin(), s.end()); //构造string对象某段迭代器区间的内容int arr[] = { 1, 2, 3, 4, 5 };int sz = sizeof(arr) / sizeof(int);list<int> lt5(arr, arr + sz); //构造数组某段区间的复制品  ->本质是调用迭代器区间的构造函数list<int> lt{ 1,2,3,4,5 };  // 直接使用花括号进行构造---C++11允许

list常用接口

int array[] = { 1,2,3,4,5,6,7,8 };list<int> lt(array, array + sizeof(array) / sizeof(array[0]));lt.begin();		//指向第一个元素的迭代器lt.end();		//返回最后一个元素的下一个元素的迭代器lt.rbegin();		//指向最后一个元素的迭代器lt.rend();			//返回第一个元素的前一个元素的迭代器list<int> mylist = { 1, 2 };// 把mylist的大小设为5mylist.resize(5);// 把list大小设为4，不足部分填充5mylist.resize(4, 5);// 判空mylist.empty();mylist.clear(); //清空容器mylist.front();	// 返回头元素mylist.back();	// 返回尾元素// 在list尾部插入一个元素8mylist.push_back(8);// 在list头部插入一个元素8mylist.push_front(8);// 删除mydeue尾部一个元素mylist.pop_back();// 删除mydeue头部一个元素mylist.pop_front();// it指向mylist的第二个元素list<int>::iterator it = mylist.begin() + 1;// 使用insert添加一个元素list<int>::iterator itnew = mylist.insert(it, 10);// 使用insert添加2个元素，value为20mylist.insert(it, 2, 20);list<int> list2{ 10, 20, 30 };// it1指向list2的第一个元素list<int>::iterator it1 = list2.begin();// it2指向list2的最后一个元素后一个位置list<int>::iterator it2 = list2.end();// 使用insert在2之前添加[it1,it2)之间的元素mylist.insert(it, it1, it2);// it指向mylist的第二个元素list<int>::iterator it = mylist.begin() + 1;// 删除it指向的元素，即2，并返回一个迭代器指向2之后的元素list<int>::iterator itnew = mylist.erase(it);// it1指向mylist的第二个元素list<int>::iterator it1 = mylist.begin() + 1;// it2指向mylist的最后一个元素后一个位置list<int>::iterator it2 = mylist.end();// 删除[it1,it2)之间的元素,即删除2，3，4mylist.erase(it1, it2);// 交换list1和list2的元素mylist.swap(list2);// 将list2中所有元素插入到mylist的第一个位置mylist.splice(mylist.begin(), list2);// 将迭代器向后移动两个位置，指向第三个元素std::advance(it, 2);// 将list2的第一个元素(10)插入到mylist的第三个位置mylist.splice(it, list2, list2.begin());std::list<int> list5 = { 1, 2, 3, 4, 5 };std::list<int> list6 = { 10, 20, 30 };// 将list5中第二个到第四个元素移动到list6的末尾auto first = list5.begin();std::advance(first, 1);auto last = list5.begin();std::advance(last, 4);list6.splice(list6.end(), list5, first, last);mylist.remove(2);bool isEven(int n) {return n % 2 == 0;}mylist.remove_if(isEven);mylist.unique();		//删除连续的重复元素 mylist.merge(list2);	//将 list2 合并到 mylist 中,两个列表必须都是完成排序的mylist.reverse();		//将该链表的所有元素的顺序反转