05.STLvector、list、stack、queue
STL标准模板库
standard template library
STL将原来常用的容器和操作进行封装，增加了C++的编码效率
容器
string #include
vector #include
list #include
stack #include
queue #include
set #include
map #include
迭代器
容器和算法之间的粘合剂，可以类比指针
算法
sort（）
max_element()
min_element()
vector容器
1.vector数组基本操作
向量数组（动态数组）
底层是静态数组
没有给向量数组分配空间不能向里面输入值
下面代码错误，因为向量数组v还没有分配空间
会造成非法访问内存空间的段错误
void text1_01(){int n;cin>>n;vector<int> v;for(int i=0;i<=n;i++){cin>>v[i];//错误，因为向量数组v还没有分配空间//会造成非法访问内存空间的段错误}for(int i=0;i<=n;i++){cout<<v[i]<<" ";}
}
v.push_back()和v.pop_back()
v.push_back()方法是分配空间的同时插入数据
v.pop_back()方法删除数据后，它的size大小也跟着改变
#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;void text1_01(){int n;cin>>n;vector<int> v;cout<<"大小："<<v.size()<<endl;for(int i=0;i<n;i++){int x;cin>>x;v.push_back(x);//不但插入数据，而且还分配空间}for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}cout<<endl;v.pop_back();cout<<"大小："<<v.size()<<endl;for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}
}
2.调用vector类的的构造函数，给动态数组分配空间
方法一：缺省参2，分配n个整形空间，默认初始化为0
void text1_01(){int n;cin>>n;vector<int> v(n+1);//分配n个int大小的空间，并且初始化为0for(int i=1;i<=n;i++){cout<<v[i]<<" ";}cout<<endl;
}
方法二：参二为val，分配n个整形空间，则全部初始化为val
void text1_01(){int n;cin>>n;vector<int> v(n+1,100);//分配n个int大小的空间，并且初始化为valfor(int i=1;i<=n;i++){cout<<v[i]<<" ";}cout<<endl;
}
方法三：大括号分配空间和数据
#include<vector>
void text01(){vector<int> v={1,2,3,4,5,6,7,8,9,10};
}
3.打印方式
方法1：cout下标打印
void text1_01(){int n;cin>>n;vector<int> v(n+1,100);//分配n个int大小的空间，并且初始化为0for(int i=1;i<=v.size()-1;i++){cin>>v[i];}for(int i=1;i<=v.size()-1;i++){cout<<v[i]<<" ";}cout<<endl;
}
方法2：iterator(迭代器)打印
v.begin()是指向数组首元素的迭代器
v.end()是指向数组为元素下一位的迭代器，充当结束的标志（无效迭代器）
vector::iterator iter=v.begin()+1
auto iter=v.begin()+1
void text1_01(){int n;cin>>n;vector<int> v(n+1,100);//分配n个int大小的空间，并且初始化为0for(int i=1;i<=v.size()-1;i++){cin>>v[i];}//迭代器可以类比为指针类型//vector<int>::iterator iter=v.begin()+1;for(auto iter=v.begin()+1;iter!=v.end();iter++){cout<<*iter<<" ";}cout<<endl;
}
方法3：for range(C++11)访问
#include <vector>
vector<int> v={1,2,3,4,5,6,7,8,9,10};
void text01(){for(auto it:v){cout<<it<<" ";}
}
4.初始化和打印练习
void text2_01(){//vector<Type> v(count,val)-->申请count个Type大小的val
// vector<int> v0;//没有分配空间int n;cin>>n;vector<int> v0;vector<int> v1{1,2,3,4,5,6,7,8,9,10};vector<int> v2(n);vector<int> v3(n,10);//内置函数push_back()分配空间的同时插入数据cout<<"输入vo:"<<endl;for(int i=0;i<n;i++){int x;cin>>x;v0.push_back(x);}cout<<"push_back输入的for range打印 vo:"<<endl;for(auto it:v0){cout<<it<<" ";}cout<<endl;cout<<"迭代器打印 v1:"<<endl;//迭代器打印for(auto iter=v1.begin();iter!=v1.end();iter++){cout<<*iter<<" ";}cout<<endl;cout<<"输入v2:"<<endl;for(auto& it:v2){cin>>it;}cout<<"for range打印 v2:"<<endl;//for range打印for(auto it:v2){cout<<it<<" ";}cout<<endl;//下标打印cout<<"下标打印 v3:"<<endl;for(int i=0;i<v3.size();i++){cout<<v3[i]<<" ";}
}
5.内置函数
v.erase()
v.insert()
STL中单反涉及迭代器区间的都是左闭右开
void text1_01(){vector<int> v{1,2,3,4,5,6,8,9,10};//分配n个int大小的空间，并且初始化为0//迭代器可以类比为指针类型//vector<int>::iterator iter=v.begin()+1;v.erase(v.begin());for(auto it:v){cout<<it<<" ";}cout<<endl;v.erase(v.begin(),v.begin()+5);for(auto it:v){cout<<it<<" ";}//8 9 10cout<<endl;v.insert(v.begin(),7);for(auto it:v){cout<<it<<" ";}cout<<endl;
}
v.at(i)的定位器和v[i]的区别
v.at(i)定位器如果越界的话会抛出异常
v[i]越界的话会报错
void text1_01(){vector<int> v{1,2,3,4,5,6,8,9,10};//分配n个int大小的空间，并且初始化为0int i;cin>>i;cout<<v[i];
/* cout<<v.at(i);*/
}
v.back();//输出数组的最后一位
v.size()
v.capacity()
void text1_01(){vector<int> v{1,2,3,4,5,6,7,8,9,10};//分配n个int大小的空间，并且初始化为0v.erase(v.begin()+9);cout<<v.size()<<endl;cout<<v.capacity()<<endl; }
6.外置函数sort（）
参数有俩种形式 一种是 参一：首元素地址，参二：尾元素地址的下一位，参三：比较规则
另外一直是，参一：指向首元素的迭代器，参二：指向为元素下一位的迭代器，参三：比较规则
STL里面的容器元素使用sort排序必须穿迭代器，例如string、vector数组
但是非STL容器，sort排序可以不穿迭代器，例如string【】数组，int nums【】数组
string s="hello world";
bool cmp(int left,int right){return left>right;
}
void text1_01(){vector<int> v{1,2,3,4,5,6,7,8,9,10};//分配n个int大小的空间，并且初始化为0sort(v.begin(),v.end(),cmp);for(auto it:v){cout<<it<<" ";}
}
void text1_02(){sort(s.begin(),s.end());for(auto it:s){cout<<it;}
}
7.迭代器与反迭代器
void text1_01(){vector<int> v{5,1,3,2,6,8,1,23,4,9};//分配n个int大小的空间，并且初始化为0sort(v.begin(),v.end());for(auto it:v){cout<<it<<" ";}cout<<endl;sort(v.rbegin(),v.rend());for(auto it:v){cout<<it<<" ";}
}
list容器
0.底层是双向链表
1.基本操作ls.push_back()和ls.pop_back()
2.利用构造函数开辟空间和{ }直接赋值开辟空间
3.打印方式（for range打印、迭代器打印）
4.内置函数
ls.erase、ls.insert、ls.size()、ls.begin()、ls.end()
ls.push_back、ls.push_front()、ls.pop_back()、ls.pop_front()
5.外置函数（list容器没有外置sort函数）
因为即使传入了begin end 迭代器，但是链表是不连续的，所以无法完成排序
bool cmp(int left,int right){return left>right;
}
void text2_01(){list<int> ls{5,4,3,2,1,6,7,8,9,10};
// sort(ls.begin(),ls.end());
// ls.sort();
// for(auto it:ls){
// cout<<it<<" ";
// }ls.sort(cmp);for(auto it:ls){cout<<it<<" ";}cout<<endl;ls.pop_front();ls.push_front(11);for(auto it:ls){cout<<it<<" ";}cout<<endl;
}但是有内置sort函数，内置的不用传迭代器
bool cmp(int left,int right){return left>right;
}
void text2_01(){list<int> ls{5,4,3,2,1,6,7,8,9,10};
// sort(ls.begin(),ls.end());
// ls.sort();
// for(auto it:ls){
// cout<<it<<" ";
// }ls.sort(cmp);for(auto it:ls){cout<<it<<" ";}cout<<endl;
}
void text2_01(){list<int> ls{5,4,3,2,1,6,7,8,9,10};auto p=ls.begin();int key;cin>>key;while(*p!=key){p++;}ls.erase(p);for(auto it:ls){cout<<it<<" ";}cout<<endl;ls.insert(ls.end(),1);for(auto it:ls){cout<<it<<" ";}
// sort(ls.rbegin(),ls.rend());
// sort(ls.begin(),ls.end());
// int n;cin>>n;
// list<int> ls(n,10);
// for(auto it:ls){
// cout<<it<<" ";
// }
// for(int i=1;i<=n;i++){
// int x;cin>>x;
// ls.push_back(x);
// }
// for(auto it:ls){
// cout<<it<<" ";
// }
// cout<<endl;
// ls.pop_back();
// cout<<"for range打印"<<endl;
// for(auto it:ls){
// cout<<it<<" ";
// }
// cout<<endl;
// cout<<"迭代器打印"<<endl;iter++<-->iter=iter->next
// for(auto iter=ls.begin();iter!=ls.end();iter++){
// cout<<*iter<<" ";
// }
}stack容器
后进先出，先进后厨，LIFO
1.stk.push()
2.stk.pop()
3.stk.empty()
4.stk.top()
void text2_01(){stack<int> stk;stk.push(1);stk.push(2);stk.push(3);stk.push(4);while(!stk.empty()){cout<<stk.top()<<" ";stk.pop();}
}