STL入門

作者：blue

時間：2024.3

0.概述

本文討論部分常用的STL的運用

1.pair

pair是將2個數據組合成一組數據，

pair的實現是一個結構體，主要的兩個成員變量是first second

pair<int ,double> p1;//注意中間要有逗號p1.first = 1;p1.second = 2.5;cout<<p1.first<<' '<<p1.second<<endl;//輸出結果：1 2.5

還可以利用make_pair創建新的pair對象：

pair<int, double> p1;
p1 = make_pair(1, 1.2);        //make_pair
cout << p1.first << p1.second << endl;//output: 1 1.2int a = 8;string m = "James";pair<int, string> newone;newone = make_pair(a, m);
cout << newone.first << newone.second << endl;//output: 8 James

通過tie獲取pair元素值

std::pair<std::string, int> getPreson() {return std::make_pair("Sven", 25);
}int main(int argc, char **argv) {std::string name;int ages;std::tie(name, ages) = getPreson();std::cout << "name: " << name << ", ages: " << ages << std::endl;return 0;
}

2.set(集合)

集合是存儲排序鍵的關聯容器，其中每個鍵都是唯一的，可以插入或刪除但不能更改。

begin()	返回一個指向集合中第一個元素的迭代器
end()	返回指向末尾的迭代器
empty()	如果set為空，則返回true
insert()	在集合中插入元素。
clear()	刪除set容器中的所有的元素

初始化

template< class T,            class Compare = less<T>,    class Alloc = allocator<T>   > class set;

基本上就是三個參數，第一個是值，第二個比較器，用于比較內容，默認為less即降序，第三個是內存配置器，負責內存的分配和銷毀。

在實際使用中，我們僅僅為其分配值就足以滿足大部分需求。

set<int> s;    //直接指定值的類型創建，其他為默認方法

#include <iostream>
#include <set>
using namespace std;
int main()
{                   /*兩個‘>’之間最好有空格*/set<pair<double, double> > s;     //建立一個其中類型為pair<double,double>的集合，名為sint x1, y1, x2, y2;for (x1 = 0; x1 < 20; x1++){for (y1 = 0; y1 < 21; y1++){for (x2 = x1 + 1; x2 < 20; x2++){for (y2 = 0; y2 < 21; y2++){double k = double(x1 - x2) / (y1 - y2);double b = double(x2 * y1 - x1 * y2) / (x2 - x1);s.insert({ k,b });     //將元素值插入到集合s當中，集合會自動去重。}}}}printf("%lld", s.size() + 20);return 0;
}

set中元素的遍歷

關鍵是要聲明迭代器變量，遍歷方法與數組類似，可以用while循環也可以用for循環，但用for循環時條件運算符不能用 <，而用 ！= 進行判斷，還特別需要注意指針運算符

#include<iostream>
#include<set>
using namespace std;set<int>all;
int main()
{//生成待處理的數據for(int i=0;i<100;i++)all.insert(i);//遍歷set,用迭代器類型?????? 注意這種for(set<int>::iterator i=all.begin();i!=all.end();i++)cout<<*i<<endl; //注意指針運算符return 0;
}

3.vector

vector是一個十分有用的容器

簡單地說，vector是一個能夠*存放任意類型的動態數組*，能夠增加和壓縮數據。

實例：
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
signed main()
{int i;vector<int> a;           //定義for(i=0;i<=100;i++){a.push_back(i);      //尾部壓入}for(i=0;i<a.size();i++)   //把其當數組來遍歷 {printf("%lld ",a[i]);}reverse(a.begin(),a.end());   //逆轉容器中的值 printf("\n");                        //??，注意這里要用"!="for(vector<int>::iterator j=a.begin();j!=a.end();j++)  //把他用迭代器指針來遍歷 {//??注意迭代器調用，用指針printf("%lld ",*j);}return 0; 
}

運行結果

排序

sort(vec.begin(),vec.end());(默認是按升序排列,即從小到大).bool cmp(int a,int b)
{return a>b;
}
調用時:sort(vec.begin(),vec.end(),Cmp)，這樣就降序排序。

4.string字符串類型

C++ string中的find()函數 - 王陸 - 博客園 (cnblogs.com)

為什么 string.find()返回值是-1_string中find函數-1為什么是18446744073709551615-CSDN博客

兩篇文章結合著看

0順子日期 - 藍橋云課 (lanqiao.cn)

本題考查了對字符串類型的應用

#include <iostream>
#include <string>
using namespace std;
int main()
{int ans=0;string t1="012",t2="123";for(int i=1;i<=12;i++){for(int j=1;j<=31;j++){string str="2022";if(i>=10) str+=to_string(i);else{str+='0';str+=to_string(i);}if(j>=10) str+=to_string(j);else{str+='0';str+=to_string(j);}if(str.find(t1)!=-1||str.find(t2)!=-1) ans++;}}printf("%d",ans);return 0;
}

C++:cin、cin.getline()、getline()的用法_getline(cin,s)函數用法-CSDN博客

關于string，輸入帶空格或tab的字符串的有趣的用法。

C++中substr()函數用法詳解_c++ substr-CSDN博客

string的用法總讓人大吃一驚，還能這樣用？

 s.substr(pos, len)//string a=s.substr(0,3);s中從pos開始的len個字符的拷貝

5.queue，deque，priority_queue

隊列

queue<type> q
q.push(x) //將x放入隊列
q.front() //返回隊首元素但不刪除
q.pop()   //刪除隊首元素
q.back()  //返回隊尾元素
q.size()  //返回元素個數
q.empty() //檢查隊列是否為空，空則返回true

雙端隊列

由于雙端隊列，隊首隊尾都可以入隊與出隊的特點，他的入隊出隊操作與普通的queue不同，要格外注意

deque<type> dq
dp[i] //返回隊列中下標為i的元素
dq.front() //返回隊頭
dq.back()  //返回隊尾
dq.pop_back()//刪除隊尾，不返回值
dq.pop_front()//刪除隊頭，不返回值
dq.push_back(x)//在隊尾添加一個元素x
dq.push_front(x)//在隊頭添加一個元素x

雙端隊列的一個重要應用——單調隊列

①單調隊列與滑動窗口

#include <iostream>
#include <queue>
using namespace std;
int main()
{           //數組從下標1開始存儲，這個0是占位 int a[]={0,2,6,5,7,8,6};int m=3;//窗口的大小 deque<int> Q;//存放元素的下標 //滑動窗口的邊界為  [i-m+1,i] for(int i=1;i<=6;i++)  //維護窗口的最小值，保持隊首元素永遠是窗口內最小的 {while(!Q.empty()&&a[Q.back()]>a[i]) Q.pop_back();  //新進元素更優，隊尾出隊 Q.push_back(i);//存儲的是下標 if(Q.front()<i-m+1) Q.pop_front(); //隊首已在窗口之外，隊首出隊 if(i>=m) printf("%d ",a[Q.front()]);//窗口充滿，可以輸出 }printf("\n");for(int i=1;i<=6;i++) //維護窗口的最大值 {while(!Q.empty()&&a[Q.back()]<a[i]) Q.pop_back();Q.push_back(i);if(Q.front()<i-m+1) Q.pop_front();if(i>=m) printf("%d ",a[Q.front()]);} return 0;
}

優先隊列（priority_queue）

默認大頂堆

priority_queue <Type, Container, Functional> 隊列名 //類型，容器類型，比較方式priority_queue <int,vector<int>,greater<int> > q;//升序隊列（最小值優先）priority_queue <int,vector<int>,less<int> >q;    //降序隊列，最大值優先（默認的）

由于優先隊列是以堆的形式存儲數據的，所以隊首的元素應該是堆頂（top），這一點要和其他隊列區分開來

q.size();//返回q里元素個數
q.empty();//返回q是否為空，空則返回1，否則返回0
q.push(k);//在q的末尾插入k
q.pop();//刪掉q的第一個元素
q.top();//返回q的第一個元素

自定義優先級（要注意和自定義排序區分開，不要搞混了）

結構體自定義優先級

6.list的用法

詳解C++STL容器系列（二）—— list的詳細用法和與vector的對比_vector assign swap 區別-CSDN博客

掌握stl中list的用法

P1996 約瑟夫問題 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

#include <iostream>
#include <list>
using namespace std;
int main()
{int n,m;cin>>n>>m;list<int> a;for(int i=1;i<=n;i++) a.push_back(i);list<int>::iterator it=a.begin();while(a.size()>1){for(int i=1;i<m;i++){it++;if(it==a.end()) it=a.begin();}cout<<*it<<" ";list<int>::iterator next=++it;if(next==a.end()) next=a.begin();//end()成員函數返回指向末尾位置的迭代器。這個“末尾位置”            指的是最后一個元素再往后一位，也就是說end()所指的位置不包含有效元素，它相當于一個虛設的節點。a.erase(--it);it=next;}cout<<*it;return 0;
}