# STL 函數介紹
資訊之芽 6/9
哲學三 林子期

---

## `stl::sort`

STL 提供簡單好用的排序

----

### 預設排序，由小到大

#include<iostream>
#include<algorithm>

int main() {
    int myints[] = {3,5,2,4};
    std::sort(myints, myints+4);
    for(int i = 0; i < 4; i++)
        std::cout << myints[i] << " ";
}

----

### 也可以用來排 string

#include<iostream>
#include<algorithm>

int main() {
    std::string mystrings[] = {"one", "two", "three", "four"};
    std::sort(mystrings, mystrings+4);
    for(int i = 0; i < 4; i++)
        std::cout << mystrings[i] << " ";
}

能被 < 比較的都可以！

----

### 第三個參數——比較函數

#include<iostream>
#include<algorithm>

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int myints[] = {3,5,2,4};
    std::sort(myints, myints+4, cmp);
    for(int i = 0; i < 4; i++)
        std::cout << myints[i] << " ";
}

----

### 能用來比較不能直接比的東西
例如：將代表學生們的 struct 依座號排序

#include<iostream>
#include<algorithm>

struct Student {
    int number;
    std::string name;
};

bool cmp(Student a, Student b) {
    return a.number < b.number;
}

----

int main() {
    Student students[4];
    for(int i = 0; i < 4; i++) {
        std::cout << "Input number and name of student " << i << ":\n";
        std::cin >> students[i].number >> students[i].name;
    }
    std::sort(students, students+4, cmp);
    for(int i = 0; i < 4; i++)
        std::cout << students[i].name << " ";
}

---

## `stl::next_permutation`
好用的枚舉函數

----

* 每對一個陣列區間呼叫一次，會將這個區間排列為「下一個順序」
* 例如 1 2 3 的所有排序為
* 1 2 3
* 1 3 2
* 2 1 3
* 2 3 1
* 3 1 2
* 3 2 1

----

當陣列為其中一種內容時呼叫 `next_permutation` 會將內容變為下一種
* 1 2 3 -> 1 3 2
* 2 3 1 -> 3 1 2

----

當發現是最後一種排序（3 2 1）時，`next_permutation` 會將陣列排成第一種並回傳 false。

int myints[] = {1,2,3};

std::cout << "The 3! permutations:\n";
do {
  std::cout << myints[0] << ' '
            << myints[1] << ' '
            << myints[2] << '\n';
} while ( std::next_permutation(myints,myints+3) );

----

跟 `std::sort` 相同，也能使用 cmp 函數

bool cmp(int a, int b) {
  return a > b;
}

int main () {
  int myints[] = {1,2,3};

  std::cout << "The 3! permutations:\n";
  do {
    std::cout << myints[0] << ' '
              << myints[1] << ' '
              << myints[2] << '\n';
  } while ( std::next_permutation(myints, myints+3, cmp) );
  return 0;
}

---

兩者都能用在 vector 上！
起始與結束位置使用 `begin()` 與 `end()`

std::vector<int> a({2,1,3,7,4});
std::sort(a.begin(), a.end());