使用一个东西，不明白它的道理，不高明
——侯捷老师
1. lower_bound()函数
功能：返回第一个不小于val的元素位置的迭代器
1.1 函数声明
// 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);
1.2 等价操作实现
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;
}
1.3 示例程式
void test_lower_bound() {
vector<int> vec {10, 30, 20, 40 ,20, 20, 50};
std::sort(vec.begin(), vec.end());
auto it = std::lower_bound(vec.begin(), vec.end(), 20);
cout << std::distance(vec.begin(), it) << " " << *it << endl;
}
输出结果：1 20
1.4 参考链接
2. upper_bound()函数
功能:返回大于第一个比比较值大的元素位置的迭代器
2.1 函数声明
// 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);
2.2 等价操作实现
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;
}
2.3 示例程式
void test_upper_bound() {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
std::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';
}
输出结果：
lower_bound at position 3
upper_bound at position 6
