map/unordered_mapのキーにカスタムデータ型を使う

C++の標準ライブラリではテーブル（連想配列）系のコンテナとして、ツリー実装のset/map/multiset/multimapが使えます。またC++11規格では、新たにハッシュテーブル実装のunordered_set/unordered_map/unordered_multiset/unordered_multimapが使えるようになっています。unordered系はBoostライブラリやTR1ライブラリとしてすでに随分前から実装されている処理系もあったため、C++erにとっては特別真新しい機能というものではないでしょう。

今回はその連想配列の値（Value）ではなくキー（Key）にカスタムデータ型（ユーザー定義のクラスや構造体）を使う場合の話です。
intやlongなどの組込型、そしてstd::string/std::wstringなどの標準ライブラリの文字列型をキーとして使う場合、特にソート順を変えたり大文字小文字を同一視したりする必要がないのであれば

std::map<int, TCustomStruct> myIndexToCustomStructMap;
std::unordered_map<std::string, TCustomStruct> myNameToCustomStructMap;

な感じでテンプレート引数にキーの型と値の型を渡すだけで簡単に定義できるのですが、ユーザー定義のクラスや構造体をキーとして使う場合、特定の演算子をオーバーロードしたり、ハッシュ関数を定義する関数オブジェクト（ファンクタ）を明示的に定義したりする必要があります。
.NETの場合はSystem.Object.Equals()とSystem.Object.GetHashCode()をオーバーライドするだけでいいので分かりやすいんですが……*1

ぶっちゃけ細かい説明するのが面倒なのでサンプルコードを書きました。Visual C++ 2012で動作確認済み。

#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#ifdef _MSC_VER
#include <conio.h>
#endif

//#define USE_UNORDERED_CONTAINERS

class Vector3F
{
public:
  float X, Y, Z;

  Vector3F()
    : X(), Y(), Z()
  {}

  explicit Vector3F(float x, float y, float z)
    : X(x), Y(y), Z(z)
  {}

  // 順序系／非順序系のコンテナを両方使う場合は同時に定義していても構わない（ロジックに矛盾がない限り）。
  // コンテナの選択は用途に応じた各種操作の計算量オーダーも検討材料のひとつになるが、
  // 一般的にキーの同値性のみが重要な場合、unordered_set/unordered_map が適している。
  // コンテナに格納される順序も重要な場合（ソートされていることが好ましい場合）、set/map が適している。
#ifdef USE_UNORDERED_CONTAINERS
  // 同値判定用の演算子オーバーロード。
  // .NET の System.Object.Equals() に相当。
  // unordered_set/unordered_map ではハッシュ値とともに使われる。
  bool operator ==(const Vector3F& other) const
  {
    return
      this->X == other.X &&
      this->Y == other.Y &&
      this->Z == other.Z;
  }
  bool operator !=(const Vector3F& other) const
  {
    return !(*this == other);
  }
  // .NET の System.Object.GetHashCode() に相当。
  size_t GetHashCode() const
  {
    return
      std::hash<decltype(X)>()(this->X) ^
      std::hash<decltype(Y)>()(this->Y) ^
      std::hash<decltype(Z)>()(this->Z);
  }

  // ハッシュ値取得用の関数オブジェクト。
  struct HashFunctor
  {
    size_t operator ()(const Vector3F& v) const { return v.GetHashCode(); }
  };

  bool IsNearlyEqualTo(const Vector3F& other) const
  {
    return
      fabs(this->X - other.X) < FLT_EPSILON &&
      fabs(this->Y - other.Y) < FLT_EPSILON &&
      fabs(this->Z - other.Z) < FLT_EPSILON;
  }

  // 比較（同値性）を定義する関数オブジェクト。
  struct NearEqualityFunctor
  {
    bool operator ()(const Vector3F& a, const Vector3F& b) const { return a.IsNearlyEqualTo(b); }
  };
#else
  // 順序付けのための演算子オーバーロード。
  bool operator <(const Vector3F& other) const
  {
    // カスタム キーに基づいた順序付けのアルゴリズムはアプリケーションによる。
    // 下記は X を主キー、Y を副キー1、Z を副キー2 として昇順でソートするための実装例。
    if (this->X < other.X)
    {
      return true;
    }
    else if (this->X > other.X)
    {
      return false;
    }
    // X が等しい場合。
    if (this->Y < other.Y)
    {
      return true;
    }
    else if (this->Y > other.Y)
    {
      return false;
    }
    // X と Y が等しい場合。
    if (this->Z < other.Z)
    {
      return true;
    }
    else if (this->Z > other.Z)
    {
      return false;
    }
    // X と Y と Z がすべて等しい場合。
    return false;
  }
#endif
};


#ifdef USE_UNORDERED_CONTAINERS

// std::hash<T> の特殊化を std 名前空間に定義しておくとテンプレート第3引数（hasher）は省略できるが、適用範囲に注意。
// std::equal_to<T> の特殊化を std 名前空間に定義しておくとテンプレート第4引数（key_equal）の代わりにできるが、適用範囲に注意。
#if 1
// テンプレート第4引数を省略すると、bool operator ==(const T&) const が使われる。
typedef std::unordered_map<Vector3F, int, Vector3F::HashFunctor> TVec3ToIndexMap;
#elif 0
typedef std::unordered_map<Vector3F, int, Vector3F::HashFunctor, Vector3F::NearEqualityFunctor> TVec3ToIndexMap;
#else
namespace std
{
  template<> struct hash<Vector3F>
  {
    std::size_t operator()(const Vector3F& key) const
    {
      return key.GetHashCode();
    }
  };
  template<> struct equal_to<Vector3F>
  {
    bool operator ()(const Vector3F& a, const Vector3F& b) const
    {
      return a.IsNearlyEqualTo(b);
    }
  };
}
// これ以降に定義される unordered_set/unordered_map/unordered_multiset/unordered_multimap には
// デフォルトで特殊化されたファンクタが適用される。
typedef std::unordered_map<Vector3F, int> TVec3ToIndexMap;
#endif

#else
typedef std::map<Vector3F, int> TVec3ToIndexMap;
#endif


int main()
{
  TVec3ToIndexMap vecToIndexMap;

  int index = 0;
  vecToIndexMap.insert(std::make_pair(Vector3F(), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(), index++)); // 重複は許可しない。
  vecToIndexMap.insert(std::make_pair(Vector3F(-0.0f, -0.0f, -0.0f), index++)); // +0.0f と -0.0f は同値。
  vecToIndexMap.insert(std::make_pair(Vector3F(FLT_MIN, 0.0f, 0.0f), index++)); // 比較関数の定義によって 0.0f と FLT_MIN が同値か否かが変わる。
  vecToIndexMap.insert(std::make_pair(Vector3F(1.0f, 0.0f, 0.0f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(1.0f + FLT_EPSILON, 0.0f, 0.0f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(+0.1f, +0.2f, +0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(+0.1f, -0.2f, +0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(+0.1f, +0.2f, -0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(+0.1f, -0.2f, -0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(-0.1f, +0.2f, +0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(-0.1f, -0.2f, +0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(-0.1f, +0.2f, -0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F(-0.1f, -0.2f, -0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F( 0.0f, +0.2f, +0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F( 0.0f, -0.2f, +0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F( 0.0f, +0.2f, -0.3f), index++));
  vecToIndexMap.insert(std::make_pair(Vector3F( 0.0f, -0.2f, -0.3f), index++));

  printf("InsertedCount = %d, MapCount = %d\n", index, static_cast<int>(vecToIndexMap.size()));
  // map の場合 Vector3F に基づいてソートされているはず。
  // unordered_map の場合は順序不定。
  for (const auto& pair : vecToIndexMap)
  {
    printf("%2d (%+.3g, %+.3g, %+.3g)\n", pair.second, pair.first.X, pair.first.Y, pair.first.Z);
  }

#ifdef _MSC_VER
  puts("Press any...");
  _getch();
#endif

  return 0;
}

set/mapは要素を追加するたびに項目がソートされるのが特徴です。基本的に挿入／検索操作の計算量はO(log(n))になります。
multiset/multimapはキーの重複を許可します。
unordered_set/unordered_mapは要素の並びが不定ですが、挿入／検索操作の計算量は平均でO(1)すなわち定数時間、最悪でO(n)になります。
unordered_multiset/unordered_multimapはキーの重複を許可します。

従来のset/map系は順序付けがなされるため、カスタム型にoperator <()を定義する必要があります。
unordered系は同値性の定義としてoperator ==()とハッシュ関数（と必要に応じて比較関数）を定義する必要があるのですが、テンプレートをインスタンス化する際に暗黙的に渡すstd::hash（とstd::equal_to）の特殊化を行なうか、ユーザー定義の関数オブジェクト（ファンクタ）を定義して明示的にテンプレート引数として渡します。それぞれメリットとデメリットがありますが、std::hashを特殊化する方法を選んだ場合は以降のデフォルトテンプレート引数に影響を及ぼすため、十分に注意する必要があります。
なお、比較関数の優先順位は、
〔operator ==()〕　＜　〔std::equal_toの特殊化〕　＜　〔テンプレート引数ファンクタ〕
となります。

テーブル系コンテナの一般的な使いどころとしては検索処理の高速化でしょうか。std::vectorをstd::find()などで線形検索する場合O(n)で、データ数が少ない場合はキャッシュ効率的に有利なvectorのほうが高速だったりしますが、例えば二重ループの総当たりでvectorとfind()を使って組み合わせを調べるルート探索系のアルゴリズムを書くとO(n^2)となり、データ数が増加するにつれて急激に計算量（処理時間）が増加していきます。
set/mapは通例二分探索木で実装され、挿入／検索操作の平均計算量は要素数に対数比例するため、データ数の増加に対して平均計算時間の増加が緩やかになります。二重ループにも強くなります。
テーブル系のコンテナはうまく活用できればプログラムを何10倍も何100倍も高速化することができます。

*1:ジェネリクスのパフォーマンスを向上させる目的で、System.IEquatable<T>を併せて実装することもあります。