Partitions:
is_partitioned
template <class InputIterator, class UnaryPredicate> bool is_partitioned (InputIterator first, InputIterator last, UnaryPredicate pred);
如果pred返回true的范围[first，last）中的所有元素都在其返回false的元素之前，则返回true。 如果范围为空，函数将返回true。
template <class InputIterator, class UnaryPredicate>bool is_partitioned (InputIterator first, InputIterator last, UnaryPredicate pred)
{while (first!=last && pred(*first)) {++first;}while (first!=last) {if (pred(*first)) return false;++first;}return true;
}// is_partitioned example
#include <iostream> // std::cout
#include <algorithm> // std::is_partitioned
#include <array> // std::arraybool IsOdd (int i) { return (i%2)==1; }int main () {std::array<int,7> foo {1,2,3,4,5,6,7};// print contents:std::cout << "foo:"; for (int& x:foo) std::cout << ' ' << x;if ( std::is_partitioned(foo.begin(),foo.end(),IsOdd) )std::cout << " (partitioned)\n";elsestd::cout << " (not partitioned)\n";// partition array:std::partition (foo.begin(),foo.end(),IsOdd);// print contents again:std::cout << "foo:"; for (int& x:foo) std::cout << ' ' << x;if ( std::is_partitioned(foo.begin(),foo.end(),IsOdd) )std::cout << " (partitioned)\n";elsestd::cout << " (not partitioned)\n";return 0;
}
Possible output:
foo: 1 2 3 4 5 6 7 (not partitioned) foo: 1 7 3 5 4 6 2 (partitioned) |
partition
重新排列范围[first，last）中的元素，使pred返回true的所有元素都在其返回false的所有元素之前。迭代器返回的点指向第二组的第一个元素。
每组内的相对排序不一定与调用前相同。请参阅stable_partition，了解具有类似行为但在每个组中具有稳定排序的函数。
template <class BidirectionalIterator, class UnaryPredicate>BidirectionalIterator partition (BidirectionalIterator first,BidirectionalIterator last, UnaryPredicate pred)
{while (first!=last) {while (pred(*first)) {++first;if (first==last) return first;}do {--last;if (first==last) return first;} while (!pred(*last));swap (*first,*last);++first;}return first;
}// partition algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::partition
#include <vector> // std::vectorbool IsOdd (int i) { return (i%2)==1; }int main () {std::vector<int> myvector;// set some values:for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9std::vector<int>::iterator bound;bound = std::partition (myvector.begin(), myvector.end(), IsOdd);// print out content:std::cout << "odd elements:";for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it)std::cout << ' ' << *it;std::cout << '\n';std::cout << "even elements:";for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
Possible output:
odd elements: 1 9 3 7 5 even elements: 6 4 8 2 |
stable_partition
重新排列范围[first,last)中的元素，使得pred返回true的所有元素都在其返回false的所有元素之前，并且与函数partition不同，每个组中元素的相对顺序都得到了保留。
// stable_partition example
#include <iostream> // std::cout
#include <algorithm> // std::stable_partition
#include <vector> // std::vectorbool IsOdd (int i) { return (i%2)==1; }int main () {std::vector<int> myvector;// set some values:for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9std::vector<int>::iterator bound;bound = std::stable_partition (myvector.begin(), myvector.end(), IsOdd);// print out content:std::cout << "odd elements:";for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it)std::cout << ' ' << *it;std::cout << '\n';std::cout << "even elements:";for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}Output:
odd elements: 1 3 5 7 9 even elements: 2 4 6 8 |
partition_copy
将pred返回true的范围[first，last）中的元素复制到result_true所指向的范围中，将未返回true的元素复制在result_false所指向范围中。
template <class InputIterator, class OutputIterator1,class OutputIterator2, class UnaryPredicate pred>pair<OutputIterator1,OutputIterator2>partition_copy (InputIterator first, InputIterator last,OutputIterator1 result_true, OutputIterator2 result_false,UnaryPredicate pred)
{while (first!=last) {if (pred(*first)) {*result_true = *first;++result_true;}else {*result_false = *first;++result_false;}++first;}return std::make_pair (result_true,result_false);
}// partition_copy example
#include <iostream> // std::cout
#include <algorithm> // std::partition_copy, std::count_if
#include <vector> // std::vectorbool IsOdd (int i) { return (i%2)==1; }int main () {std::vector<int> foo {1,2,3,4,5,6,7,8,9};std::vector<int> odd, even;// resize vectors to proper size:unsigned n = std::count_if (foo.begin(), foo.end(), IsOdd);odd.resize(n); even.resize(foo.size()-n);// partition:std::partition_copy (foo.begin(), foo.end(), odd.begin(), even.begin(), IsOdd);// print contents:std::cout << "odd: "; for (int& x:odd) std::cout << ' ' << x; std::cout << '\n';std::cout << "even: "; for (int& x:even) std::cout << ' ' << x; std::cout << '\n';return 0;
}Output:
odd: 1 3 5 7 9 even: 2 4 6 8 |
partition_point
向分区范围[first，last）中pred不为true的第一个元素返回迭代器，指示其分区点。
范围中的元素应该已经被分区，就好像partition是用相同的参数调用的一样。
该函数通过比较排序范围中的非连续元素来优化执行的比较次数，这对于随机访问迭代器特别有效。
template <class ForwardIterator, class UnaryPredicate>ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,UnaryPredicate pred)
{auto n = distance(first,last);while (n>0){ForwardIterator it = first;auto step = n/2;std::advance (it,step);if (pred(*it)) { first=++it; n-=step+1; }else n=step;}return first;
}// partition_point example
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vectorbool IsOdd (int i) { return (i%2)==1; }int main () {std::vector<int> foo {1,2,3,4,5,6,7,8,9};std::vector<int> odd;std::partition (foo.begin(),foo.end(),IsOdd);auto it = std::partition_point(foo.begin(),foo.end(),IsOdd);odd.assign (foo.begin(),it);// print contents of odd:std::cout << "odd:";for (int& x:odd) std::cout << ' ' << x;std::cout << '\n';return 0;
}Output:
odd: 1 3 5 7 9 |
Sorting
sort
| default (1) | template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); |
|---|---|
| custom (2) | template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
按升序对范围 [first,last)中的元素进行排序。 第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。 等效元素不能保证保持其原始相对顺序（请参见stable_sort）。
// sort algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::sort
#include <vector> // std::vectorbool myfunction (int i,int j) { return (i<j); }struct myclass {bool operator() (int i,int j) { return (i<j);}
} myobject;int main () {int myints[] = {32,71,12,45,26,80,53,33};std::vector<int> myvector (myints, myints+8); // 32 71 12 45 26 80 53 33// using default comparison (operator <):std::sort (myvector.begin(), myvector.begin()+4); //(12 32 45 71)26 80 53 33// using function as compstd::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)// using object as compstd::sort (myvector.begin(), myvector.end(), myobject); //(12 26 32 33 45 53 71 80)// print out content:std::cout << "myvector contains:";for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}Output:
myvector contains: 12 26 32 33 45 53 71 80 |
stable_sort
template <class RandomAccessIterator> void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );template <class RandomAccessIterator, class Compare> void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
对保持等价顺序的元素进行排序
将范围[first,last) 中的元素按升序排序，类似于排序，但stable_sort保留了具有等效值的元素的相对顺序。 第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。
// stable_sort example
#include <iostream> // std::cout
#include <algorithm> // std::stable_sort
#include <vector> // std::vectorbool compare_as_ints (double i,double j)
{return (int(i)<int(j));
}int main () {double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};std::vector<double> myvector;myvector.assign(mydoubles,mydoubles+8);std::cout << "using default comparison:";std::stable_sort (myvector.begin(), myvector.end());for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';myvector.assign(mydoubles,mydoubles+8);std::cout << "using 'compare_as_ints' :";std::stable_sort (myvector.begin(), myvector.end(), compare_as_ints);for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}compare_as_ints是一个只比较元素的积分部分的函数，因此，具有相同积分部分的元素被认为是等价的。stable_sort保留调用之前的相对顺序。
Possible output:
using default comparison: 1.32 1.41 1.62 1.73 2.58 2.72 3.14 4.67 using 'compare_as_ints' : 1.41 1.73 1.32 1.62 2.72 2.58 3.14 4.67 |
partial_sort
| default (1) | template <class RandomAccessIterator> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); |
|---|---|
| custom (2) | template <class RandomAccessIterator, class Compare> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); |
对范围中的元素进行部分排序
重新排列范围中的元素[first,last)，使middle之前的元素是整个范围中最小的元素，并按升序排序，而其余元素则没有任何特定的顺序。 第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。
// partial_sort example
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort
#include <vector> // std::vectorbool myfunction (int i,int j) { return (i<j); }int main () {int myints[] = {9,8,7,6,5,4,3,2,1};std::vector<int> myvector (myints, myints+9);// using default comparison (operator <):std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());// using function as compstd::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);// print out content:std::cout << "myvector contains:";for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
Possible output:
myvector contains: 1 2 3 4 5 9 8 7 6 |
partial_sort_copy
| default (1) | template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy (InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); |
|---|---|
| custom (2) | template <class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy (InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); |
复制并部分排序范围
将[first，last）到[result_first，result_last）范围内的最小元素复制，并对复制的元素进行排序。复制的元素数量与result_firs和result_last之间的距离相同（除非这大于[first、last）中的元素数量）。 范围[first,last)未修改。 第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。
// partial_sort_copy example
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort_copy
#include <vector> // std::vectorbool myfunction (int i,int j) { return (i<j); }int main () {int myints[] = {9,8,7,6,5,4,3,2,1};std::vector<int> myvector (5);// using default comparison (operator <):std::partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());// using function as compstd::partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end(), myfunction);// print out content:std::cout << "myvector contains:";for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}Output:
myvector contains: 1 2 3 4 5 |
is_sorted
| default (1) | template <class ForwardIterator> bool is_sorted (ForwardIterator first, ForwardIterator last); |
|---|---|
| custom (2) | template <class ForwardIterator, class Compare> bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp); |
检查范围是否排序
如果范围[first，last）按升序排序，则返回true。
第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。
template <class ForwardIterator>bool is_sorted (ForwardIterator first, ForwardIterator last)
{if (first==last) return true;ForwardIterator next = first;while (++next!=last) {if (*next<*first) // or, if (comp(*next,*first)) for version (2)return false;++first;}return true;
}// is_sorted example
#include <iostream> // std::cout
#include <algorithm> // std::is_sorted, std::prev_permutation
#include <array> // std::arrayint main () {std::array<int,4> foo {2,4,1,3};do {// try a new permutation:std::prev_permutation(foo.begin(),foo.end());// print range:std::cout << "foo:";for (int& x:foo) std::cout << ' ' << x;std::cout << '\n';} while (!std::is_sorted(foo.begin(),foo.end()));std::cout << "the range is sorted!\n";return 0;
}Output:
foo: 2 3 4 1 foo: 2 3 1 4 foo: 2 1 4 3 foo: 2 1 3 4 foo: 1 4 3 2 foo: 1 4 2 3 foo: 1 3 4 2 foo: 1 3 2 4 foo: 1 2 4 3 foo: 1 2 3 4 the range is sorted! |
is_sorted_until
| default (1) | template <class ForwardIterator> ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last); |
|---|---|
| custom (2) | template <class ForwardIterator, class Compare> ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last, Compare comp); |
查找范围中第一个未排序的元素
将迭代器返回到范围[first，last）中不遵循升序的第一个元素。
对 first和返回的迭代器之间的范围进行排序。
如果对整个范围进行了排序，则函数返回last。
第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。
template <class ForwardIterator>ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last)
{if (first==last) return first;ForwardIterator next = first;while (++next!=last) {if (*next<*first) return next;++first;}return last;
}// is_sorted_until example
#include <iostream> // std::cout
#include <algorithm> // std::is_sorted_until, std::prev_permutation
#include <array> // std::arrayint main () {std::array<int,4> foo {2,4,1,3};std::array<int,4>::iterator it;do {// try a new permutation:std::prev_permutation(foo.begin(),foo.end());// print range:std::cout << "foo:";for (int& x:foo) std::cout << ' ' << x;it=std::is_sorted_until(foo.begin(),foo.end());std::cout << " (" << (it-foo.begin()) << " elements sorted)\n";} while (it!=foo.end());std::cout << "the range is sorted!\n";return 0;
}Output:
foo: 2 3 4 1 (3 elements sorted) foo: 2 3 1 4 (2 elements sorted) foo: 2 1 4 3 (1 elements sorted) foo: 2 1 3 4 (1 elements sorted) foo: 1 4 3 2 (2 elements sorted) foo: 1 4 2 3 (2 elements sorted) foo: 1 3 4 2 (3 elements sorted) foo: 1 3 2 4 (2 elements sorted) foo: 1 2 4 3 (3 elements sorted) foo: 1 2 3 4 (4 elements sorted) the range is sorted! |
nth_element
| default (1) | template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); |
|---|---|
| custom (2) | template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); |
对范围中的元素排序
重新排列范围[first,last)中的元素，使第n个位置的元素是排序序列中该位置的元素。 其他元素没有任何特定的顺序，除了第n个之前的元素没有一个大于它，后面的元素也没有一个小于它。 第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。
// nth_element example
#include <iostream> // std::cout
#include <algorithm> // std::nth_element, std::random_shuffle
#include <vector> // std::vectorbool myfunction (int i,int j) { return (i<j); }int main () {std::vector<int> myvector;// set some values:for (int i=1; i<10; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9std::random_shuffle (myvector.begin(), myvector.end());// using default comparison (operator <):std::nth_element (myvector.begin(), myvector.begin()+5, myvector.end());// using function as compstd::nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);// print out content:std::cout << "myvector contains:";for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}Possible output:
myvector contains: 3 1 4 2 5 6 9 7 8 |
Binary search (operating on partitioned/sorted ranges)
lower_bound
| default (1) | template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); |
|---|---|
| custom (2) | template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); |
将迭代器返回到下界
返回一个迭代器，该迭代器指向范围[first，last）中的第一个元素，该元素的比较值不小于val。
第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。该范围内的元素应已根据相同的标准（运算符<或comp）进行排序，或至少根据值进行分区。
该函数通过比较排序范围中的非连续元素来优化执行的比较次数，这对于随机访问迭代器特别有效。
与upper_bound不同，此函数返回的迭代器所指向的值也可能等效于val，而不仅仅是更大。
template <class ForwardIterator, class T>ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it;iterator_traits<ForwardIterator>::difference_type count, step;count = distance(first,last);while (count>0){it = first; step=count/2; advance (it,step);if (*it<val) { // or: if (comp(*it,val)), for version (2)first=++it;count-=step+1;}else count=step;}return first;
}// lower_bound/upper_bound example
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vectorint main () {int myints[] = {10,20,30,30,20,10,10,20};std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30std::vector<int>::iterator low,up;low=std::lower_bound (v.begin(), v.end(), 20); // ^up= std::upper_bound (v.begin(), v.end(), 20); // ^std::cout << "lower_bound at position " << (low- v.begin()) << '\n';std::cout << "upper_bound at position " << (up - v.begin()) << '\n';return 0;
}Output:
lower_bound at position 3 upper_bound at position 6 |
upper_bound
| default (1) | template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val); |
|---|---|
| custom (2) | template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); |
将迭代器返回到上限
返回一个迭代器，该迭代器指向范围[first，last）中比较大于val的第一个元素。
第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。该范围内的元素应已根据相同的标准（运算符<或comp）进行排序，或至少根据值进行分区。
该函数通过比较排序范围中的非连续元素来优化执行的比较次数，这对于随机访问迭代器特别有效。
与lower_bound不同，此函数返回的迭代器所指向的值不能等于val，只能大于val。
template <class ForwardIterator, class T>ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it;iterator_traits<ForwardIterator>::difference_type count, step;count = std::distance(first,last);while (count>0){it = first; step=count/2; std::advance (it,step);if (!(val<*it)) // or: if (!comp(val,*it)), for version (2){ first=++it; count-=step+1; }else count=step;}return first;
}// lower_bound/upper_bound example
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vectorint main () {int myints[] = {10,20,30,30,20,10,10,20};std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30std::vector<int>::iterator low,up;low=std::lower_bound (v.begin(), v.end(), 20); // ^up= std::upper_bound (v.begin(), v.end(), 20); // ^std::cout << "lower_bound at position " << (low- v.begin()) << '\n';std::cout << "upper_bound at position " << (up - v.begin()) << '\n';return 0;
}Output:
lower_bound at position 3 upper_bound at position 6 |
equal_range
| default (1) | template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val); |
|---|---|
| custom (2) | template <class ForwardIterator, class T, class Compare> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); |
获取相等元素的子范围
返回子范围的边界，该子范围包括值等于val的范围[first，last]的所有元素。
第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。两个元素a和b被认为是等价的，如果（！（a<b）&&！（b<a））或如果（！comp（a，b）&&！comp（b，a））。
该范围内的元素应已根据相同的标准（运算符<或comp）进行排序，或至少根据值进行分区。
如果val不等于范围中的任何值，则返回的子范围的长度为零，两个迭代器都指向比val大的最近值（如果有），或者指向最后一个值（如果val比范围中的所有元素都大）。
template <class ForwardIterator, class T>pair<ForwardIterator,ForwardIterator>equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it = std::lower_bound (first,last,val);return std::make_pair ( it, std::upper_bound(it,last,val) );
}// equal_range example
// equal_range example
#include <iostream> // std::cout
#include <algorithm> // std::equal_range, std::sort
#include <vector> // std::vectorbool mygreater (int i,int j) { return (i>j); }int main () {int myints[] = {10,20,30,30,20,10,10,20};std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds;// using default comparison:std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30bounds=std::equal_range (v.begin(), v.end(), 20); // ^ ^// using "mygreater" as comp:std::sort (v.begin(), v.end(), mygreater); // 30 30 20 20 20 10 10 10bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); // ^ ^std::cout << "bounds at positions " << (bounds.first - v.begin());std::cout << " and " << (bounds.second - v.begin()) << '\n';return 0;
}Output:
bounds at positions 2 and 5 |
binary_search
| default (1) | template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val); |
|---|---|
| custom (2) | template <class ForwardIterator, class T, class Compare> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); |
测试排序序列中是否存在值
如果范围[first，last）中的任何元素等于val，则返回true，否则返回false。
第一个版本使用运算符<比较元素，第二个版本使用comp比较元素。两个元素a和b被认为是等价的，如果（！（a<b）&&！（b<a））或如果（！comp（a，b）&&！comp（b，a））。
该范围内的元素应已根据相同的标准（运算符<或comp）进行排序，或至少根据值进行分区。
该函数通过比较排序范围中的非连续元素来优化执行的比较次数，这对于随机访问迭代器特别有效。
template <class ForwardIterator, class T>bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{first = std::lower_bound(first,last,val);return (first!=last && !(val<*first));
}// binary_search example
#include <iostream> // std::cout
#include <algorithm> // std::binary_search, std::sort
#include <vector> // std::vectorbool myfunction (int i,int j) { return (i<j); }int main () {int myints[] = {1,2,3,4,5,4,3,2,1};std::vector<int> v(myints,myints+9); // 1 2 3 4 5 4 3 2 1// using default comparison:std::sort (v.begin(), v.end());std::cout << "looking for a 3... ";if (std::binary_search (v.begin(), v.end(), 3))std::cout << "found!\n"; else std::cout << "not found.\n";// using myfunction as comp:std::sort (v.begin(), v.end(), myfunction);std::cout << "looking for a 6... ";if (std::binary_search (v.begin(), v.end(), 6, myfunction))std::cout << "found!\n"; else std::cout << "not found.\n";return 0;
}Output:
looking for a 3... found! looking for a 6... not found. |
