タグ

関連タグで絞り込む (0)

  • 関連タグはありません

タグの絞り込みを解除

ProgrammingとC++とHashに関するagwのブックマーク (2)

  • std::unordered_map のキーに独自の型を使用する - Qiita

    C++11 で追加された std::unordered_map は、連想配列を扱うことができる。 以前からある std::map では、キーとして扱えることができるのは 順序関係が定義されたオブジェクトのみである。一方、 std::unordered_map では順序関係が定義されていキーを使うことができ、純粋な連想配列(ハッシュテーブル)として使うことができる。 ただし、 std::unordered_map のキーはハッシュ値へ変換できる必要がある。多くの標準型のように std::hash() でハッシュ値への変換が定義されている型はそのままキーに使うことができるが、自分で定義した型など変換が定義されていない型をキーとして使用する場合はハッシュ計算を行う関数を自分で用意する必要がある。 このハッシュ関数を定義するには、 std::hash() を特殊化する方法と、関数オブジェクトを作成

    std::unordered_map のキーに独自の型を使用する - Qiita
  • mapとunordered_mapの違いについてまとめておく - yasuhisa's blog

    NLPだとstd::mapとtr1::unordered_mapなら後者を使うことになることが多いと思うけど、あれこれ混乱してきたのでメモる。NLPerなら押さえておくべき常識のはず。。。 それぞれの特徴 データ構造 std::map tr1::unordered_map 実装 赤黒木 ハッシュテーブル find log n Average case: O(1), Worset case: O(n) insert log n Average case: O(1), Worset case: O(n) delete log n Average case: O(1), Worset case: O(n) メリット キーでソート済みなことが保障されているので、ある範囲でiterationさせたいとき、deleteするなどの操作を効率的に行うことができる バケット数を最初にきちんと設定しておけば大

    mapとunordered_mapの違いについてまとめておく - yasuhisa's blog
  • 1