sort(排序):
template <class RandomAccessIterator> void sort ( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
该方法用于排序,comp用于指定元素比较的函数
类似的有stable_sort(保持比较相等元素的原顺序)
partial_sort(部分排序):template <class RandomAccessIterator> void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp );对序列进行部分排序,对first和middle之间的元素进行排序~~其余的不管
partial_sort_copy是该算法的copy版本:
template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last ); template <class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp );关于二分查找的操作:
nth_element:template <class RandomAccessIterator> void nth_element ( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void nth_element ( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp );将第n个元素放在第n个位置
结果为:vector<int>::iterator it;
// set some values:
for (int i=1; i<10; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
random_shuffle (myvector.begin(), myvector.end());
// using default comparison (operator <):
nth_element (myvector.begin(), myvector.begin()+5, myvector.end());
myvector contains: 3 1 4 2 5 6 9 7 8
lower_bound:
template <class ForwardIterator, class T> ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value ); template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );该方法会找到序列中可以存放value的值的迭代器部分。与之相对应的方法是upper_bound方法可以如下使用:
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
vector<int>::iterator low,up;
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
low=lower_bound (v.begin(), v.end(), 20); // ^
up= upper_bound (v.begin(), v.end(), 20); //
结果为:
lower_bound at position 3
upper_bound at position 6
equal_range:
template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator> equal_range ( ForwardIterator first, ForwardIterator last, const T& value ); template <class ForwardIterator, class T, class Compare> pair<ForwardIterator,ForwardIterator> equal_range ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
返回的是一个pair.
pair.first是value的起始位置,pair.second是结束位置(不包括在内~)
binary_search(二分查找):template <class ForwardIterator, class T> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value ); template <class ForwardIterator, class T, class Compare> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
测试有序序列中是否包含要查找的元素。