c++ STL

[wittyResry]

lower_bound(ForwardIterator first, ForwardIterator last, const T& val)

template <class ForwardIterator, class T> ForwardIterator lower_bound
(ForwardIterator first, ForwardIterator last, const T& val);

template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound 
(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

• 调用lower_bound之前必须确定序列为有序序列，否则调用出错。第一个版本排序根据底层的 <(小于)操作符，跳过小于的。
• Value of the lower bound to search for in the range. For (1), T shall be a type supporting being compared with elements of the range [first,last) as the right-hand side operand of operator<.

  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;
  }

• Binary function that accepts two arguments (the first of the type pointed by ForwardIterator, and the second, always val), and returns a value convertible to bool. The value returned indicates whether the first argument is considered to go before the second. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

[wittyResry]

set lower_bound

• 既然是 set 容器，不存在距离这个概念。如果你真想有个顺序，就用 vector。能进行算术运算的迭代器只有随机访问迭代器，要求容器元素存储在连续内存空间里，vector，string，deque的迭代器是有加减法的。但是map，set，multimap, multiset的迭代器是没有加减法的，list也不可以。