C++STL底子整理

STL

by lqx
vector

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. signed main(){
5.         ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
6.        
7.         vector<int>v1;
8.         for(int i=0;i<=5;i++)v1.push_back(i); //012345
9.         v1.pop_back(); //01234
10.         reverse(v1.begin(),v1.end()); //43210
11.         v1.erase(v1.begin()+2); //将v1[2]删除
12.         for(auto i:v1)cout<<i;cout<<'\n'; //4310
13.        
14.         vector<int>v2(10); //初始化10个0
15.         v2.insert(v2.begin()+2,-1); //将-1插入v2[2]的位置
16.         cout<<"v2.size():"<<v2.size()<<'\n'; //11
17.         for(auto i:v2)cout<<i;cout<<'\n'; //00-100000000
18.        
19.         vector<int>v3(7,4); //初始化7个4
20.         v3.erase(v3.begin()+1,v3.begin()+3); //删除[first,last)元素
21.         for(auto i:v3)cout<<i;cout<<'\n'; //44444
22.        
23.         vector<int>v4{4,2,3,1,4,5,6}; //{}直接赋值
24.         vector<int>v5(v4.begin(),v4.end()); //复制v4的元素
25.         for(auto i:v5)cout<<i;cout<<'\n'; //4231456
27.         //vector离散化模板:v.erase(unique(v.begin(),v.end()),v.end())
28.         sort(v4.begin(),v4.end());
29.         for(auto i:v4)cout<<i;cout<<'\n'; //1234456
30.         v4.erase(unique(v4.begin(),v4.end()),v4.end());
31.         for(auto i:v4)cout<<i;cout<<'\n'; //123456
32.        
33.         vector<int>v[10]; //二维数组 v[0]~v[9]都是一个vector
34.         //vector<vector<int> >v(10);等价
35.         for(int i=1;i<5;i++)v[0].push_back(i);
36.         for(int i=1;i<9;i++)v[1].push_back(i);
37.         cout<<v[0].size()<<' '<<v[1].size()<<'\n'; //4 8
38.         for(auto i:v[0])cout<<i;cout<<'\n'; //1234
39.         for(auto i:v[1])cout<<i;cout<<'\n'; //12345678
40.         return 0;
41. }

复制代码

map

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. signed main(){
5.         ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
6.         map<int,string> mp1;
7.         map<string,int> mp2;
8.         mp1[1]="lqx";mp2["lqx"]=1;
9.         mp1[2]="lts";mp2["lts"]=2;
10.         mp1[3]="lzl";mp2["lzl"]=3;
11.         mp1[4]="djy";mp2["djy"]=4;
12.         cout<<mp1.size()<<' '<<mp2.size()<<'\n'; //4 4
13.         for(int i=1;i<=4;i++)cout<<mp1[i]<<'\n';
14.         string s;cin>>s;
15.         cout<<mp2[s];
16.         return 0;
17. }

复制代码

unordered_map

• unordered_map底层是用哈希表实现的，map底层是用红黑树实现的
  
• unordered_map是不按键值排序的，插入的时间是O(logn),查询时间是O(1)
  
• map是按键值排序的，插入的时间是O(logn),查询时间是O(logn)
  
• unordered_map和map的利用险些是同等的
  

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. signed main(){
5.         ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
6.         unordered_map<int,string> mp1;
7.         unordered_map<string,int> mp2;
8.         mp1[1]="lqx";mp2["lqx"]=1;
9.         mp1[2]="lts";mp2["lts"]=2;
10.         mp1[3]="lzl";mp2["lzl"]=3;
11.         mp1[4]="djy";mp2["djy"]=4;
12.         cout<<mp1.size()<<' '<<mp2.size()<<'\n'; //4 4
13.         for(int i=1;i<=4;i++)cout<<mp1[i]<<'\n';
14.         string s;cin>>s;
15.         cout<<mp2[s];
16.         return 0;
17. }

复制代码

stack

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. signed main(){
5.         stack<int> s,t;
6.         for(int i=1;i<=4;i++)s.push(i);
7.         s.pop();
8.         t.push(s.top());
9.         cout<<s.size()<<'\n'; //3
10.         while(!s.empty()){
11.                 cout<<s.top()<<' ';
12.                 s.pop();
13.         } //3 2 1
14.         cout<<'\n';
15.         while(!t.empty()){
16.                 cout<<t.top()<<' ';
17.                 t.pop();
18.         } //3
19.         return 0;
20. }

复制代码

queue

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. signed main(){
5.         queue<int> s,t;
6.         for(int i=1;i<=4;i++)s.push(i),t.push(s.back());
7.         cout<<s.size()<<'\n'; //4
8.         cout<<s.front()<<' '<<s.back()<<'\n';//1 4
9.         while(!s.empty()){
10.                 cout<<s.front()<<' ';
11.                 s.pop();
12.         } //1 2 3 4
13.         cout<<'\n';
14.         while(!t.empty()){
15.                 cout<<t.front()<<' ';
16.                 t.pop();
17.         } //1 2 3 4
18.         return 0;
19. }

复制代码

deque

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. signed main(){
5.         deque<int> s,t;
6.         for(int i=1;i<=4;i++)s.push_back(i),t.push_back(s.back());
7.         s.push_front(0);
8.         s.push_back(5);
9.         cout<<s.size()<<'\n'; //6
10.         while(!s.empty()){
11.                 cout<<s.front()<<' ';
12.                 s.pop_front();
13.         } //0 1 2 3 4 5
14.         cout<<'\n';
15.         t.pop_front();
16.         t.pop_back();
17.         cout<<t.size()<<'\n'; //2
18.         while(!t.empty()){
19.                 cout<<t.front()<<' ';
20.                 t.pop_front();
21.         } //2 3
22.         return 0;
23. }

复制代码

priority_queue

priority_queue默认大根堆，队首元素最大值

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.         priority_queue<int> q1;//默认大顶堆
5.   //priority_queue<int,vector<int>,less<int>> q1; 等价
6.         priority_queue<int,vector<int>,greater<int>> q2;//小根堆
7.         for(int i=1;i<=5;i++)q1.push(i);
8.         for(int i=1;i<=5;i++)q2.push(i);
9.         while(!q1.empty()){
10.                  cout<<q1.top();
11.                  q1.pop();
12.         } //54321
13.         cout<<'\n';
14.         while(!q2.empty()){
15.                 cout<<q2.top();
16.                 q2.pop();
17.         } //12345
18.         cout<<'\n';
19.         for(int i=1;i<=5;i++)q1.push(i);
20.         for(int i=1;i<=5;i++)q2.push(i);
21.         q1.pop();
22.         q2.pop();
23.         while(!q1.empty()){
24.                  cout<<q1.top();
25.                  q1.pop();
26.         } //4321
27.         cout<<'\n';
28.         while(!q2.empty()){
29.                 cout<<q2.top();
30.                 q2.pop();
31.         } //2345
32.         return 0;
33. }

复制代码

set

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.         set<int> s;//自动排序去重
5.         for(int i=5;i>0;i--)s.insert(i);
6.         s.insert(9);
7.         s.insert(3);
8.         s.erase(2);
9.         cout<<s.size()<<'\n';
10.         for(auto i:s)cout<<i; //13459
11.         cout<<'\n';
12.         //查找元素 s.find(x)==s.end()?"N":"Y"
13.         if(s.find(5)!=s.end())cout<<"5在集合里\n";
14.         else cout<<"5不在集合里\n";
15.         if(s.find(99)!=s.end())cout<<"99在集合里\n";
16.         else cout<<"99不在集合里\n";
17.         return 0;
18. }

复制代码