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());