C++ STL 常用函式

所有STL函式都要用到

using namespace std;

vector 陣列

vector 可以被看成一個“超級陣列” ，不會和C語言陣列一樣被限制長度，它既可以和C語言的陣列一樣用下標訪問，也可以像鏈表一樣動態改變長度，

#include<vector>  //頭檔案
vector<int> arr1(100);
int arr2[100];   //該定義類似C語言陣列

vector<int> list;
list.push_back(1);
list.push_back(2);
....

vector 的遍歷

vector<int> arr(100);
vector<int> list;
for(int i=0;i<100;i++)  //用陣列下標的方式，需要定義長度；
{
    scanf("%d",&arr[i]);
    cout<<arr[i]<<endl;
}
for(int i=0;i<100;i++) //用鏈表的方式，可以一直加資料；
{
    int a;
    cin>>a;
    list.push_back(a);
    printf("%d\n",list[i]);
}

vector 常見操作

list為上面定義的一個vector型別的名字，可變
list.size();  // 陣列元素個數 O(1);
list.clear();  // 一鍵清空陣列 O(n);
list.empty();  //陣列是否為空 O(1);
list.begin():  //陣列首元素的下標 O(1);
list.end();  //陣列最后一個元素的下一個元素的下標 O(1);
list.erase(p1);  //洗掉陣列某個下標所在位置的數字 O(n);
list.push_back(1);  //往陣列后面添加元素 O(1);
list.pop_back();  //洗掉陣列最后一個元素 O(1);

vector 在一些元素個數不確定的場合可以很好地節省空間，

string 字串

字串string可以看成一個特殊的vector
string和C語言字串的關系和vector和普通陣列的關系一樣

#include<cstring>  或  #include<string.h>
string str1="hello";
char str2[]="world";
string str3;
str3.push_back('!');
cout<<str1<<" "<<str2<<str3<<endl;
//hello world!

vector有的操作string基本都有
所有引數為字串的地方既可以是string也可以是C字串

str.length(); str.size();      //等同 strlen();
str.insert(1,"aaa");          // 在下標為1處插入一個字符或字串

str.c_str();            //回傳成C語言的字串，回傳后可以用printf輸出
//其中第一個str為string型別字串的名字，
char c[20];
string s="1234";
strcpy(c,s.c_str());  或者  printf("%s",s.c_str());

str.append(str2);   // 把str2拼接到str后面
str.compare(str2);   //等同 strcmp(str,str2);

str == str2;         //等同 strcmp(str,str2)==0;
str += str2;         //等同 str.append(str2);
str += 'a';           //等同 str.push_back('a');

最后三個便是string的特點，也就是這個的方便之處，可以直接用來運算，不用像C語言一樣寫那么多函式，然后后面的sort快排如果要用來排字串也只能排string型別的字串，

algorithm 演算法函式

#include<algorithm>

algorithm和之前的兩個頭檔案不同，它沒有定義什么新的型別，而是定義了很多演算法，極大簡化了代碼量

sort快速排序

sort(arr,arr+n);
排序開始指標
排序結束指標（最后一個元素的下一個元素的指標）
系統默認從小到大的升序排序法

但是sort可以自定義比較函式
比較函式引數是兩個待比較變數，回傳值是bool值
比如從大到小的降序排序函式可以這樣寫

bool cmp(int a,int b)
{
    return a>b;
}
sort(arr,arr+n,cmp);

自己定義的結構體一定要寫比較函式
如下面，比較函式是先比較x坐標，在x坐標相同的情況下比較y坐標

struct point
{
   int x,y;
};
point arr[10000];    //c++可以直接用這個結構體型別名
//不用像C語言一樣要加 typedef 去換一個結構體名
bool cmp(point a,poinrt b)
{
    if(a.x!=b.x)
        return a.x < b.x;
    return a,y < b.y;
}
sort(arr,arr+10,cmp);

next_permutation函式

next_permutation(start,end)
prev_permutation(start,end)
兩個函式一樣，區別在于前者求的是當前排列的下一個排列，后一個求的是當前排列的上一個排列
next_permutation(arr,arr+n)是對陣列arr中的前n個元素進行全排列，同時改變arr陣列的值，
在使用前要對陣列升序排序，否則只能找出該排序后的全排列數

int num[3]={1,2,3};
do
{
    cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
}while(next_permutation(num,num+3));
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
do
{
    cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
}while(next_permutation(num,num+2));
1 2 3
2 1 3
int num[3]={2,1,3};
do
{
    cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
}while(next_permutation(num,num+3));
2 3 1
3 1 2
3 2 1

其他algorithm函式

min(a,b); //回傳較小值 
max(a,b); //回傳較大值

nth_element(a,a+x,a+n);
將陣列中第x小的數放到第x個位置
如a[9]={4,7,6,9,1,8,2,3,5};
nth_element(a,a+2,a+9)  
將下標為2，也就是排序后a[2]位置的數求出來，但是對其他元素沒有排序
當然和sort一樣可以自定義排序的比較函式

swap(a,b); //交換兩個數
reverse(a,a+n); //反轉陣列

unique(a,a+n);  //對陣列進行去重
unique需要在排序好后使用，放回值是最后一個元素的地址
int l=unique(a,a+n)-a;    //l即為去重后陣列的個數

lower_bound(a,a+n,x);  //回傳第一個不小于x的數的地址；
upper_bound(a,a+n,x); //回傳第一個大于x的數的地址；
a[5]={1,2,2,3,4};
int l=lower_bound(a,a+5,2)-a;
int d=upper_bound(a,a+5,2)-a;
// l=1;  d=3;

stack 堆疊

#include<strack>
strack<int> sta;
sta.push(1);    //入堆疊
int a=sta.top();  //取堆疊頂元素
sta.pop();  //出堆疊
sta.empty();  //判空
sta.size();  //堆疊內元素個數

queue 佇列

包含佇列 (queue) 和優先佇列 (priority_queue) 兩種資料結構
兩者用法和stack完全相同

#include<queue>
queue<int> que;
que.push(1);  //入隊
int a=que.front();  //取隊頭元素，這里不是top,而是front
//優先級佇列便還是top
que.pop();
que.empty();
que,size();

map 映射

map包含的第一個資料結構是pair，它可以由任意兩種型別構成，當你偷懶不想寫結構體，又要用到兩個相關聯的變數時可以，用pair，pair自帶比較函式，默認先比第一個元素再比第二個元素

#include<map>
pair<string,int> p1("james","18");
pair<int,double> p2;
p2.first = 1;
p2.second = 2.5;
pair<int,int> p3;
p3=make_pair(0,0);

map的第二個資料結構就是map
map可以看成一個超級陣列，你可以吧字串或者其他型別當成陣列的下標，

map<string,int> stu;
stu["小明“]=170;
stu["小紅“]=150;

以上的頭檔案都不需要記憶，只要

#include<bits/stdc++.h>

就能一鍵包含所有頭檔案（Visual Studio 除外）

學習STL的正確姿勢

1、http://www.cplusplus.com/reference/認真查看STL用法
2、利用好的編譯器的STL自動補全功能，由函式名知道函式的用法，并在實踐中得出真知