ある区間の上限／下限を求める

STL の upper_bound / lower_bound を使ってみたらハマったので、日記のネタに。

結論を書くと、
std::upper_bound( first, last, x ) は、区間 [ iter, last ) が std::equal_range( first, last, x ) の上界となるような iter を、
std::lower_bound( first, last, x ) は、区間 [ first, iter ) が std::equal_range( first, last, x ) の下界となるような iter を、
それぞれ求める関数です。

つまり、得られた iter は、
upper_bound の場合は上界の最初の要素を指すイテレータで、これは分かりやすいですが、
lower_bound の場合は、下界の最後の要素の「次を」指すイテレータになります。
下界の最後の要素、つまり下限を求めたい場合は、イテレータを一つ前に戻す必要がある、ということです。
まぁ考えてみれば当たり前なのですが、うっかりハマってしまったので、日記に書き残しておく次第。

というか、最初から、ある区間に対して上限と下限を求める関数があればいいんですよね。
こんな感じで：

http://ideone.com/oARV9

#include <algorithm>
#include <iterator>
#include <boost/optional.hpp>

template<class FwdIter, class T>
inline boost::optional<typename std::iterator_traits<FwdIter>::reference>
  sup( FwdIter first, FwdIter last, T const& x )
{
  first = std::upper_bound( first, last, x );
  if( first != last ) {
    return *first;
  }
  else {
    return boost::none;
  }
}

template<class BidirIter, class T>
inline boost::optional<typename std::iterator_traits<BidirIter>::reference>
  inf( BidirIter first, BidirIter last, T const& x )
{
  last = std::lower_bound( first, last, x );
  if( first != last ) {
    return *--last;
  }
  else {
    return boost::none;
  }
}

#include <iostream>

int main()
{
  int a[] = { 1, 2, 3, 3, 4, 6 };
  std::size_t const n = sizeof(a) / sizeof(a[0]);

  std::cout << *sup( a, a+n, 3 ) << std::endl;
  std::cout << *inf( a, a+n, 3 ) << std::endl;
}

結果がイテレータではなく optional な参照なのは、 inf において「見つからなかった」ことを示す適切なイテレータがない為。
last を返す、でもいいのですが、意味論的におかしいので*1、ならば optional の方がいいかな、という判断です。
range-base なら、こういう場合に悩まなくて済む気もしますね。

*1:意味論的には first の前の要素を指すイテレータを返したい