連想コンテナ(7)

現時点でのコード．連想コンテナ(2)と対して変わらないような．
内部で使うツール類

template
struct TypeTraits { typedef T& ParamType; };
template
struct TypeTraits { typedef T* ParamType; };
template<>
struct TypeTraits { typedef int ParamType; };


// ポインタなら削除．ポインタでなければ削除しない．
template
struct PtrDeletor { inline static void deletor(DataParamType d, KeyParamType k) { }};
template
struct PtrDeletor {
   inline static void deletor(DataParamType* d, KeyParamType* k) { delete d; delete k;}
};
template
struct PtrDeletor {
   inline static void deletor(DataParamType* d, KeyParamType k) { delete d;}
};
template
struct PtrDeletor {
   inline static void deletor(DataParamType d, KeyParamType* k) { delete k;}
};

// 常に何もしない
template
struct NoneDeletor { inline static void deletor(DataParamType d, KeyParamType k) { }};


// 比較関数
// 特殊化する場合，元のkeyが(ポインタ|int)以外の場合は自動的に&がつくことに注意．
template< typename Key>
struct DefaultCompare {
   inline static bool less( const Key k0, const Key k1) { return k0<k1;}
   inline static bool equals( const Key k0, const Key k1) { return k0==k1;}
};

本体

template<
     typename T
   , typename Key = int
   , template class Compare = DefaultCompare
   , template class Deletor = PtrDeletor
>
class AssocVector
{
private:
   typedef T   DataType;
   typedef Key   KeyType;
   typedef typename TypeTraits::ParamType DataParamType;
   typedef typename TypeTraits::ParamType KeyParamType;

   // 使いやすくするための省略形
   typedef std::pair   Item;
   typedef std::vector< Item>   List;
   typedef typename List::iterator   Iterator;
   typedef typename Compare CompImpl;
   typedef typename Deletor DelImpl;

   List   v;

   // 同じkeyに何度もfindImplを掛けないようにキャッシュを持ってみる
   // IsExist()をしてからGet()を呼ぶ場合，二重に探索をすること避ける．
   // keyのコピーコンストラクタが重い場合はキャッシュを使わないほうがいい
   bool      flagCache;
   Iterator   itCache;
   KeyType      keyCache;

   struct Compare {
      inline bool operator()(const Item& i0, const Item& i1) const
          {return CompImpl::less(i0.first,i1.first);} 
      inline bool operator()(const Item& i, const Key k) const
          {return CompImpl::less(i.first,k);} 
      inline bool operator()(const Key k,const Item& i) const
          {return CompImpl::less(k,i.first);} 
   };

   Iterator findImpl( const KeyParamType key) {
      if (!flagCache || !CompImpl::equals( keyCache, key)) {
         itCache = std::lower_bound( v.begin(), v.end(), key, Compare() );
         flagCache = true;
         keyCache = key;
      }
      return itCache;
   }

   inline bool isFound( const KeyParamType key, const Iterator it) {
      return (it!=v.end() && CompImpl::equals( it->first, key));
   }

   DataType   dummyResult;

public:
   AssocVector() : flagCache(false), dummyResult() {}
   ~AssocVector() {}

   void SetDefault( DataType init) {
      dummyResult = init;
   }

   void Insert( KeyParamType key, DataParamType data) {
      Iterator it = findImpl(key);
      if (isFound( key, it)) {
         // 同じkeyが存在するので上書きする
         // 削除処理を呼び出す
         DelImpl::deletor( it->second, it->first);
         it->first = key;   // キーもdeletorに削除される可能性がある．
         it->second = data;
      } else {
         v.insert( it, Item(key, data));
         flagCache = false;
      }
   }

   bool IsEmpty() { return v.empty(); }

   bool IsExist( KeyParamType key) {
      Iterator it = findImpl(key);
      return isFound( key, it);
   }

   DataParamType Get( KeyParamType key) {
      Iterator it = findImpl(key);
      if (isFound( key, it)) {
         return it->second;
      }
      return dummyResult;   // ダミーを返す
   }

   bool Remove( KeyParamType key) {
      Iterator it = findImpl(key);
      if (isFound( key, it)) {
         // 削除処理を呼び出す
         DelImpl::deletor( it->second, it->first);
         v.erase( it);
         flagCache = false;
         return true;
      }
      return false;
   }

   void Clear() {
      // 削除処理を呼び出す
      for( Iterator it = v.begin(); it!=v.end(); ++it) {
         DelImpl::deletor( it->second, it->first);
      }
      v.clear();
      flagCache = false;
   }
};