■ map

std::mapというコンテナがあるけれどメモリ効率とかサイズとかを考えると実はあんまり汎用ではない。コンテナの変更より検索の方が多い場合、std::vectorにstd::pairを入れてソートして二分検索した方が速いことが多い。std::mapはメモリの確保・開放の回数が多いし、連続したメモリに取られるわけでもないので。

QMAILでは、CEをサポートしなくちゃいけない（つまりC++例外処理が使えない）こともあって、std::mapを使うのは不可能に近い。というようなこともあって、std::vectorにstd::pairを入れる。

たとえば、intからintへのマップの場合、

typedef std::vector<std::pair<int, int> > Map; 

みたいにして使う。

これを検索するには、std::lower_boundを使うのだけれど、比較して欲しいのはキーだけなので、そのままだと上手く行かない。というわけで、こんな風に書く。

Map m;
// ここで要素を追加
std::sort(m.begin(), m.end(),
  binary_compose_f_gx_hy(
    std::less<Map::value_type::first_type>(),
    std::select1st<Map::value_type>(),
    std::select1st<Map::value_type>()));
// 検索
Map::const_iterator it = std::lower_bound(
  m.begin(), m.end(),
  Map::value_type(5, 0),
  binary_compose_f_gx_hy(
    std::less<Map::value_type::first_type>(),
    std::select1st<Map::value_type>(),
    std::select1st<Map::value_type>()));
if (it != m.end() && (*it).first == 5) {
  // 見つかった
}

binary_compose_f_gx_hyは、boostのものと基本的には同じ。

template<class Op1, Op2, Op3>
struct binary_compose_f_gx_hy_t :
  public std::binary_function<typename Op2::argument_type,
    typename Op3::argument_type, typename Op1::result_type>
{
  binary_compose_f_gx_hy_t(
    const Op1& op1, const Op2& op2, const Op3& op3) :
    op1_(op1), op2_(op2), op3_(op3) {}
  result_type operator()(const first_argument_type& x,
    const second_argument_type& y) const
    { return op1_(op2_(x), op3_(y)); }
  Op1 op1_;
  Op2 op2_;
  Op3 op3_;
};


template<class Op1, class Op2, class Op3>
binary_compose_f_gx_hy_t<Op1, Op2, Op3>
  binary_compose_f_gx_hy(
  const Op1& op1, const Op2& op2, const Op3& op3)
{
  return binary_compose_f_gx_hy_t<Op1, Op2, Op3>(
    op1, op2, op3);
}

select1stはほんとは標準ではないけれど、STLportには入っているのでそのまま使う。

時には、二分検索しないでリニアサーチした方が速い場合もある。そのときには、

Map::const_iterator it = std::find_if(m.begin(), m.end(),
  std::bind2nd(
    binary_compose_f_gx_hy(
      std::equal_to<Map::value_type::first_type>(),
      std::select1st<Map::value_type>(),
      std::identity<Map::value_type::first_type>()),
    5));
if (it != m.end()) {
  // 見つかった
}

みたくする。identityもほんとは標準ではないけど。