STL 筆記整理【學習記錄】

STL ACM方面整理，個人筆記，若有不足，請諒解，

函式：

sort（***）:

sort [ start , end , cmp )

函式用于C++中，對給定區間所有元素進行排序，默認為升序，也可進行降序排序，sort函式進行
排序的時間復雜度為n*log2n，比冒泡之類的排序演算法效率要高的多，
默認從小到大排sort .
stl內置了幾個cmp，一個是greater< int >( )，一個less< int >( );

• less變成升序（從左到右遍歷下標時，陣列元素是從小到大）
  greater變成降序（從左到右遍歷下標時，陣列元素是從大到小）

sort(a,a+n,less<int>());
sort(a,a+n,greater<int>());

也可以自己寫出來降序cmp

/*
	降序的cmp 簡單寫法
*/
bool up(int a,int b){
	return a>b;
}

當然也可以對結構體排序

/*
	例子：先按照體重從小到大，在按照身高從高到低，
*/
#include<iostream>
#include<algorithm>
using namespace std;
/*
	180  67
	184	 75
	176  34
	189  68 
	164  30
	189  67
*/
struct node{
	int weight;
	int high;
}a[50];
bool up_struct(node a,node b){
	if(a.weight==b.weight){
		return a.high > b.high ;
	}else{
		return a.weight < b.weight ;
	}
}
int main(){
	for(int i=0;i<=5;i++){
		cin>>a[i].high>>a[i].weight;
	}
	sort(a,a+6,up_struct);
	for(int i=0;i<=5;i++){
		cout<<a[i].high<<" "<<a[i].weight<<endl;
	}
	//up_struct是自定義的排序規則，
	return 0;
}

lower_bound()函式 (***)：

注意：使用lower_bound()必須提前排序，
在 [first, last) 區域內查找不小于(>=) val 的元素
在 [first, last) 區域內查找第一個不符合 cmp 規則的元素

函式思想是二分，時間復雜度為O log(N)，如果能找到回傳一個正向迭代器，指向該元素，如果找不到，指向last，（由于我比較菜，理解為指標，

#include <iostream>	// std::cout
#include <algorithm>	// std::lower_bound
#include <vector>	// std::vector
using namespace std;
//以普通函式的方式定義查找規則
bool mycomp(int i,int j)
{
    return i>j;
}
//以函式物件的形式定義查找規則
class mycomp2
{
public:
    bool operator()(int i,  int j)
    {
        return i>j;
    }
};

int main()
{
    int a[5] = { 1,2,3,4,5 };
    //從 a 陣列中找到第一個>=3 的元素,必須為非降的
    int *p = lower_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;
    cout << "下標是：" << p-a << endl;
    vector<int> myvector{5,8,6,4,3,0,1,2};
    //根據 mycomp2 規則，從 myvector 容器中找到第一個〈＝3，容器為降序
    vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(),3,mycomp2());
    cout << "*iter = " << *iter;
    cout << "下標是：" << iter-myvector.begin() << endl;
    return 0;
}

upper_bound()函式 (***）：

與lower_bound()同理，可以理解為；upper_bound()是>,而lower_bound是>=

next_permutation (***)：

void next_permutation(begin, end)
void next_permutation(begin, end, comp)

這個函式就是輸出字典序的下一個排序方式，如果沒有，回傳（好像是-1,也或者是flase，記不清）一般配合do while來寫，
樣例如下：

/*
	例如 1 2 3 4 5
排序后是 1 2 3 5 4
*/ 
#include <iostream> 
#include <algorithm>
using namespace std;
int main() {
	int a[3]={1,2,3};
do{
	for(int i=0;i<3;i++) {
		cout<<a[i]<<' ';
	}
	cout <<'\n';
}while(next_permutation(a,a+3));
	return 0;
}

ps:一點自己的理解，沒有考證，我目前理解：next_permutation函式會把所排序陣列按照字典序排出下一個，

prev_permutation函式 (***)：

和 next_permutation 函式一樣，只是上一字典序，

unique函式 (***)：

注意：
使用該函式前，一定要先對序列進行排序，因為這里的去除并非真正意義的erase，而是將不重復的元素放到容器的前面，回傳值是去重之后的尾地址，
引數：
void unique(begin, end)
回傳去重后最后一個元素的下一個位置的迭代器

理解：去重不是把重復的去掉，而是把重復的扔后面，回傳的是尾地址，

容器：

queue 佇列：

先進先出，類似于排隊（不能插隊

常用內部函式：

• size():判斷大小
• empty():判斷是否為空
• push():放入一個元素
• front() :回傳隊頭元素
• back():回傳隊尾元素
• pop():彈出隊頭元素

/*
	簡單測驗幾個函式；
*/
#include<iostream>
#include<queue>
using namespace std;
int main(){
	queue<int> demo;
	if(demo.empty())cout<<"這時候demo是空的"<<endl; 
	demo.push(1);
	demo.push(2);
	demo.push(3);
	demo.pop();
	if(demo.empty())cout<<"這時候demo是有兩個元素的"<<endl;
	int d1=demo.front(); 
	int d2=demo.back();
	cout<<"d1="<<d1<<endl<<"d2="<<d2;
	return 0;
}

priority_queue, 優先佇列，默認是大根堆：

大根堆：放進去的時候就已經從大到小排序了，并且大的在前，

當然也可以定義成小根堆：

priority_queue<int,vector<int>,greater<int> > pq
也可以將元素取負

priority_queue（）常用函式：

• push() 插入一個元素
• top() 回傳堆頂元素（可不是front）
• pop() 彈出堆頂元素

一般操作和queue幾乎相同 ，下面重點記錄一下對結構體的讀入和排序，

/*
	進一步加深了對結構體的理解，原來node與int,double這種類似，是自己寫出來的結構，
*/
#include<iostream>
 using namespace std;
 struct node{
 	int weight;
 	int high;
 }a[10];
 int main(){
 	priority_queue<node> pq;
 	//放入要加{}
 	pq.push({1,2});
 	return 0;
 }

上面代碼會報錯，

/*
struct less : public binary_function<_Tp, _Tp, bool>
    {
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };
 */
 /*
 這就是原因，我也不太懂，但是很容易理解因為他優先佇列會對結構體排序，他不知道咋排，所以會編譯都過不了，
 */

But，想要做到還是可以完成的，

/*
	按照weight從小到大排序，如果weight一樣，按照身高高排序
*/
#include<iostream>
#include<queue>
using namespace std;
struct node{
 	int weight;
 	int high;
 	bool operator <(const node & o)const
 	{
 		if(weight==o.weight)return high<o.high;
 		return weight>o.weight;
	}
 }a;
 int main(){
 	priority_queue<node> pq;
 	pq.push({2,2});
 	pq.push({3,1});
 	pq.push({1,3});
 	cout<<pq.top().high;
 	return 0;
 }

stack, 堆疊：

特點：后入后出

內部常用函式：

• size()
• empty()
• push() 向堆疊頂插入一個元素
• top() 回傳堆疊頂元素
• pop() 彈出堆疊頂元素

deque,雙端佇列：

特別注意：支持陣列運算

內部函式：

• size()
• empty()
• clear()
• front()/back()
• push_back()/pop_back()
• push_front()/pop_front()
• begin()/end()
• [] 支持陣列運算

map

理解為map<標簽，其他型別>

類似于陣列的下角標，map<int，int> 第一個int做到的就是和陣列 a[ ]中括號里面作用類似：
map不止支持int int ，很多其他型別也支持，以后做補充，

map<int,int> a;
a[第一個int]=第二個int；

vector

特征：就是個無限增長的陣列

內部常用函式:

• size() 回傳元素個數
• empty() 回傳是否為空
• clear() 清空
• front()/back()
• push_back()/pop_back()
• begin()/end()
• [ ]支持陣列形式直接訪問

string 字串

內部常用函式:

• size()/length() 回傳字串長度
• empty() 是否為空
• clear() 清空
• substr() 起始下標，(子串長度)) 回傳子串
• c_str() 回傳字串所在字符陣列的起始地址

總結：對STL了解還不是很深，會根據認識的不同程度修改，僅供自己 參考，不常用STL今天沒有總結進去，以后有精力會加入，但是對于ACM確實用到的不多，