劃分序列

partition

重新排列 [first,last) 范圍內的元素，使得 pred 返回 true 的所有元素先于所有返回 false 的元素。迭代器返回指向第二組的第一個元素的點。

每個組內的相對順序不一定與調用之前相同。

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;bool greater50 (int i) { return (i > 50); }
void print_val(int val) { cout << val << ' '; }
int main () {vector<int> myvector = {30, 40, 80, 12, 19, 20, 55, 72};vector<int>::iterator bound;bound = partition (myvector.begin(), myvector.end(), greater50);// print out content:cout << "greater than 50:";for (vector<int>::iterator it=myvector.begin(); it!=bound; ++it)cout << ' ' << *it;cout << '\n';cout << "less than 50:";for (vector<int>::iterator it=bound; it!=myvector.end(); ++it)cout << ' ' << *it;cout << '\n';for_each (myvector.begin(), myvector.end(), print_val);cout << endl;return 0;
}

結果屏幕輸出

greater than 50: 72 55 80
less than 50: 12 19 20 40 30
72 55 80 12 19 20 40 30

stable_partition

重新排列 [first,last) 范圍內的元素，pred 返回 true 的所有元素排在返回 false 的所有元素之前, 但與partition函數不同，這個函數保留每個組內元素的相對順序。

這通常使用內部臨時緩沖區來實現。

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;bool greater30 (int i) { return (i > 30); }
void print_element(int val) { cout << val << " ";}int main () {vector<int> myvector = {4, 80, 5, 30, 6, 9, 50, 60, 1, 15};vector<int>::iterator bound;bound = stable_partition (myvector.begin(), myvector.end(), greater30);// print out content:cout << "greater than 30 elements:";for (vector<int>::iterator it=myvector.begin(); it!=bound; ++it)cout << ' ' << *it;cout << '\n';cout << "greater than or equal 30 elements: ";for (vector<int>::iterator it=bound; it!=myvector.end(); ++it)cout << ' ' << *it;cout << '\n';cout << "all elements: ";for_each (myvector.begin(), myvector.end(), print_element);cout << '\n';return 0;
}

結果屏幕輸出

greater than 30 elements: 80 50 60
greater than or equal 30 elements:  4 5 30 6 9 1 15
all elements: 80 50 60 4 5 30 6 9 1 15

排序

sort

將范圍 [first,last) 中的元素按升序排序。
第一個版本使用operator< 來比較元素，第二個版本使用comp 來比較元素。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>using namespace std;struct personnel {string  name;int     age;
};bool myfunction (int i,int j) { return (i<j); }
void print_element(int val) { cout << val << " " ; }
void print_personnel(personnel person) { cout << person.name << " " << person.age << endl; }struct sort_class {bool operator() (personnel lf, personnel lr) { return (lf.age < lr.age);}
} sort_object;int main () {vector<int> myvector = {32,71,12,45,26,80,53,33}; vector<personnel> persons = {{"John", 30},{"Allison", 25},		  {"Sam", 29},		  {"Alice", 39},		  };// using default comparison (operator <):sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)// print out content:cout << "myvector contains:" << endl;for_each (myvector.begin(), myvector.end(), print_element);cout << '\n';// using object as compsort (persons.begin(), persons.end(), sort_object); // print out content:cout << "sorted personnel:" << endl;for_each (persons.begin(), persons.end(), print_personnel);cout << '\n';return 0;
}

結果屏幕·輸出

myvector contains:
12 32 45 71 26 33 53 80
sorted personnel:
Allison 25
Sam 29
John 30
Alice 39

nth_element

重新排序 [first,last) 范圍內的元素，得到的序列是，第 n 個位置的元素位置是，完全排序后，該元素所在的位置。

在結果序列中，其他元素沒有任何特定的順序，第 n 個元素前面的所有元素，都小于或對于該元素，它后面的元素都大于或等于它。

該算法有兩個版本，第一個版本使用operator< 來比較元素，第二個版本使用comp來比較元素。

#include <iostream>  
#include <algorithm> 
#include <vector> using namespace std;bool myfunction (int i,int j) { return (i<j); }
void print_element(int val)  { cout << val << " "; }struct personnel {string name;int  age;
};struct personnel_comp {bool operator()(personnel lf, personnel lr) {return (lf.age < lr.age);};
} person_comp;int main () {vector<int> myvector = {1, 9, 5, 8, 90, 30, 11};vector<int> v2 = {11, 19, 15, 18, 100, 40, 21, 130, 210};vector<personnel> v_persons = {{"John", 30},{"Allison", 25},		  {"Sam", 29},		  {"Alice", 39},};// using default comparison (operator <):nth_element (myvector.begin(), myvector.begin()+5, myvector.end());cout << "before sort:";for_each (myvector.begin(), myvector.end(), [](int val) ->void {cout << val << " ";});cout << endl;// using default compnth_element (myvector.begin(), myvector.begin()+5, myvector.end());// print out content:cout << " after sort:";for_each (myvector.begin(), myvector.end(),  [](int val) ->void {cout << val << " ";});cout << '\n';// using function as compcout << "before sort:" << endl;for_each (v2.begin(), v2.end(), [](int val) ->void {cout << val << " ";});cout << endl;nth_element (v2.begin(), v2.begin()+6, v2.end(), myfunction);cout << " after sort:";for_each (v2.begin(), v2.end(),  [](int val) ->void {cout << val << " ";});cout << '\n';// using function as compcout << "before sort:" << endl;for_each (v_persons.begin(), v_persons.end(), [](personnel p) ->void {cout << p.name << " " << p.age << endl;});cout << endl;nth_element (v_persons.begin(), v_persons.begin()+3, v_persons.end(), person_comp);cout << " after sort:" << endl;for_each (v_persons.begin(), v_persons.end(),  [](personnel p) ->void {cout << p.name << " " << p.age << endl;});cout << '\n';return 0;
}

程序運行結果屏幕輸出

before sort:9 1 5 8 11 30 90after sort:8 1 5 9 11 30 90
before sort:
11 19 15 18 100 40 21 130 210after sort:19 11 15 18 21 40 100 130 210
before sort:
John 30
Allison 25
Sam 29
Alice 39after sort:
Sam 29
Allison 25
John 30
Alice 39

二分查找

binary_search

如果范圍 [first,last) 中的任何元素值等于 val，則返回 true，否則返回 false。

該算法支持兩種版本。

• 第一個版本，使用operator< 來比較元素，
• 第二個版本，使用comp 來比較元素。如果 (!(a<b) && !(b<a)) 或 if (!comp(a,b) && !comp(b,a))，則 a 和 b 兩個元素被視為相同。

范圍中的元素應已根據相同的標準（operator< 或 comp）進行排序，或者至少根據 val 進行分區。

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;bool myfunction (int i,int j) { return (i<j); }struct personnel {string name;int  age;
};struct personnel_comp {bool operator()(personnel lf, personnel lr) {return (lf.name < lr.name);};
} person_comp;int main () {std::vector<int> v = {1,2,40,30,3,4,5,20,10}; vector<personnel> v_persons = {{"John", 30},{"Allison", 25},		  {"Sam", 29},		  {"Alice", 39},};// using default comparison:sort (v.begin(), v.end());cout << " After sort: " << endl;for_each (v.begin(), v.end(), [](int v)->void{cout << v << " ";});cout << endl;cout << "looking for a 3... ";if (binary_search (v.begin(), v.end(), 3))cout << "found!\n"; else cout << "not found.\n";// using myfunction as comp:sort (v.begin(), v.end(), myfunction);cout << "looking for a 15... ";if (binary_search (v.begin(), v.end(), 15, myfunction))cout << "found!\n"; else cout << "not found.\n";// using personnel_comp as comp:cout << " Before sort: " << endl;for_each (v_persons.begin(), v_persons.end(), [](personnel v)->void{cout << v.name << " " << v.age << endl;});sort (v_persons.begin(), v_persons.end(), person_comp);cout << " After sort: " << endl;for_each (v_persons.begin(), v_persons.end(), [](personnel v)->void{cout << v.name << " " << v.age << endl;});cout << endl;cout << "looking for John... ";personnel person = {"John", 30}; if (binary_search (v_persons.begin(), v_persons.end(), person, person_comp))cout << "found!\n"; else cout << "not found.\n";return 0;
}

上述代碼運行后的屏幕輸出

 After sort:
1 2 3 4 5 10 20 30 40
looking for a 3... found!
looking for a 15... not found.Before sort:
John 30
Allison 25
Sam 29
Alice 39After sort:
Alice 39
Allison 25
John 30
Sam 29looking for John... found!