std::sort
&
next_permutation

STL可以排序嗎？

而且我們教的排序只能用在陣列上
那STL的
vector、stack、queue、deque、list可以排序嗎？

STL sort

• 幸好C++ STL的開發者解決了這個問題
• 在<algorithm>裡面一些專門用來排序的函數
• 讓我們一起來看看這些函數吧！

Random Access Iterator?

初學者可以理解成：
有Random Access Iterator的STL容器
都有類似陣列的功能

• 以下為目前教過有Random Access Iterator的容器
  • std::vector
  • std::deque

sort使用方法(STL容器)

sort(起始iterator, 結尾iterator);

std::vector<int> s;
for(int i=0;i<10;++i){
    s.push_back(rand());//隨機產生元素
}
std::sort(s.begin(), s.end());//由小排到大
for(int e:s) std::cout << e << '\n';

sort使用方法(一般陣列)

可以把iterator想成指標
sort(陣列起始位置, 陣列結束位置);

int s[10];
for(int i=0;i<10;++i) s[i] = rand();
std::sort(s, s+10);//由小排到大
for(int e:s) std::cout << e << '\n';

由大排到小？

直接呼叫sort他會幫你把東西由小排到大
那如果要由大排到寫怎麼辦呢？
難道在sort完之後再用for把陣列顛倒?

隱藏的東西

• std::sort其實有第三個隱藏的參數
• 這個參數要填的是一個特定型態的函數！

bool cmp(int a,int b){
    return a > b;
}
int main(){
    vector<int> s = {7, 1, 2, 2, 9, 4, 8, 7};
    sort(s.begin(), s.end(), cmp);
    for(int e:s) cout<<e<<endl;
    return 0;
}

解析

• 以由大排到小為例，Type是要排序的元素型態
• 函數會回傳一個bool值：
  • true: if(a!=b)排序後a會排在b的前面
  • false: if(a!=b)排序後b會排在a的前面

bool function_name(Type a,Type b){
    return a > b;
}

struct排序

• 給你一個struct的陣列
• 你要先依照id由小到大排序
• 如果有id相同的部分就按造val由大到小排序

struct GG{
    int id, val;
};
vector<GG> s;

比較函數

• 原則和一般的比較函數一樣：
  • true: if(a!=b)排序後a會排在b的前面
  • false: if(a!=b)排序後b會排在a的前面

bool cmp(const GG &a, const GG &b){
    if(a.id!=b.id) return a.id < b.id;
    return a.val > b.val;
}

更精簡的寫法

這樣寫更短且函數執行解果不會改變

bool cmp(const GG &a, const GG &b){
    return a.id<b.id||(a.id==b.id&&a.val>b.val);
}

std::stable_sort

• STL也有內建穩定排序
• 使用merge sort
• 用法和std::sort一樣
• 也可以使用比較函數
• 以下附上幾個範例給大家參考

一般陣列

int s[]={7,1,2,2,8,9,5,6};
stable_sort(s, s+8);

STL 容器

vector<int> s={7,1,2,2,8,9,5,6};
stable_sort(s.begin(), s.end());

比較函數

struct P{
    int id, val;
    P(int id, int val):id(id), val(val){}
}
bool cmp(const P &a, const P &b){
    return a.id<b.id||(a.id==b.id&&a.val>b.val);
}
vector<P> s;
int main(){
    for(int i=0;i<5;++i){
        int id=rand();
        s.puah_back(P(id,rand()));
        s.puah_back(P(id,rand()));
    }
    stable_sort(s.begin(), s.end(), cmp);
}

範例

• {1,2,3}的所有排列(依字典順序排)：
  1. {1, 2, 3}
  2. {1, 3, 2}
  3. {2, 1, 3}
  4. {2, 3, 1}
  5. {3, 1, 2}
  6. {3, 2, 1}

下一個排列

• 我們說某個排列\(P\)的下一個排列
• 指的是將所有排列依字典順序排之後
• 編號為\(P\)的編號+1的那個排列
• 例如{1, 3, 2}的下一個排列就是{2, 1, 3}

std::next_permutation

• 傳入的參數和sort一樣
• 他會還傳一個bool
  如果是true表示現在這個排列不是最後一個排列

int s[] = {1, 3, 2};
bool end = next_permutation(s, s+3);
cout<<end<<'\n';
for(int i=0;i<3;++i) cout<<s[i]<<' ';

STL 容器也可以用

vector<int> s = {1, 3, 2};
bool end = next_permutation(s.begin(), s.end());
cout<<end<<'\n';
for(int i=0;i<3;++i) cout<<s[i]<<' ';

產生所有排列

• 只要給出第一個排列
• 不斷呼叫next_permutation
• 直到回傳值變成false就行了

int s[]={1,2,3};
do{
    for(int i=0;i<3;++i){
        if(i) cout<<' ';
        cout<<s[i];
    }
    cout<<'\n';
}while(next_permutation(s, s+3));

比較函數

next_permutation也可以用比較函數喔！
程式碼已經重複出現很多次了我就不放了