動的ダブル配列

memo

動的にキーの追加ができるTrieを探していたが、動的ダブル配列でできるということでメモ。

大雑把に他のデータ構造との性能比較すると、次のような感じ。

  • ハッシュ(C++で言う std::map, std::tr1::unordered_map)よりも検索が速い
  • 静的ダブル配列よりもデータサイズは少しorかなり大きいが、検索速度はあまり変わらない
  • 簡潔データ構造よりもかなり検索が速いが、データサイズはかなり大きい

reference