容器的排序
并不是所有的STL容器都是可以用sort函数的，像vector，string是可以使用sort函数的，但是像set，map这种容器本身有序，故不允许使用sort排序
同样，在没有写cmp函数的时候，也是默认从小到大进行排序
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { vector<int> v; for (int i = 0; i < 10; i ++ ) v.push_back(i); sort(v.begin(), v.end()); for (int i = 0; i < 10; i ++ ) cout << v[i] << ' '; return 0; }
输出结果为：0 1 2 3 4 5 6 7 8 9
如果我们想从大到小排序：
#include <iostream> #include <algorithm> #include <vector> using namespace std; bool cmp(int a, int b) { return a > b; } int main() { vector<int> v; for (int i = 0; i < 10; i ++ ) v.push_back(i); sort(v.begin(), v.end(), cmp); for (int i = 0; i < 10; i ++ ) cout << v[i] << ' '; return 0; }
输出结果为：9 8 7 6 5 4 3 2 1 0
再来看string的排序：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; int main() { string str[3] = {"bbbb", "cc", "aaa"}; sort(str, str + 3); for (int i = 0; i < 3; i ++ ) cout << str[i] << endl; return 0; }
输出结果为：
aaa
bbbb
cc
如果在上面这个例子中，我们要按照字符串长度从小到大排序：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; bool cmp(string str1, string str2) { return str1.length() < str2.length(); } int main() { string str[3] = {"bbbb", "cc", "aaa"}; sort(str, str + 3, cmp); for (int i = 0; i < 3; i ++ ) 3 cout << str[i] << endl; return 0; }
输出结果为：
cc
aaa
bbbb
7.lower_bound() 和 upper_bound()
lower_bound() 和 upper_bound()需要在一个有序数组或容器中
lower_bound(first, last, val)是用来寻找数组或容器的[first, last)范围内第一个值大于等于val的元素的位置，如果是数组就返回该位置的指针，如果是容器，就返回该位置的迭代器
upper_bound(first, last, val)是用来寻找数组或容器的[first, last)范围内第一个值大于val的元素的位置，如果是数组就返回该位置的指针，如果是容器，就返回该位置的迭代器
显然，如果数组或容器中没有需要寻找的元素，则lower_bound()和upper_bound()均返回可以插入该元素的位置的指针或迭代器（即假设存在该元素的时候，该元素应当在的位置），lower_bound()和upper_bound()的时间复杂度均为O(log(last - first))
#include <iostream> #include <algorithm> using namespace std; int main() { int a[10] = {1, 2, 2, 3, 3, 3, 5, 5, 5, 5}; //注意数组的下标是从0开始的 //寻找-1 cout << lower_bound(a, a + 10, -1) - a << ' ' << upper_bound(a, a + 10, -1) - a << endl; //寻找1 cout << lower_bound(a, a + 10, 1) - a << ' ' << upper_bound(a, a + 10, 1) - a << endl; //寻找3 cout << lower_bound(a, a + 10, 3) - a << ' ' << upper_bound(a, a + 10, 3) - a << endl; //寻找4 cout << lower_bound(a, a + 10, 4) - a << ' ' << upper_bound(a, a + 10, 4) - a << endl; //寻找6 cout << lower_bound(a, a + 10, 6) - a << ' ' << upper_bound(a, a + 10, 6) - a << endl; return 0; }
输出结果为：
0 0
0 1
3 6
6 6
10 10
