私はC++でアドレス帳を実装しようと考えていました。モバイルアプリケーション用に開発されているので、アドレス帳はできるだけメモリを少なくし、ユーザーは名前で連絡先を検索または並べ替えることができるはずです（私が知っているパラドックス）。アドレス帳の効率的な実装
私はちょっと調べたところで、ほとんどの人がTrieが私のニーズに合った最高のデータ構造になることを示唆しています。より正確にはradix tree（Patricia Trie）。このデータ構造を使用すると、オートコンプリートも実装することができます。
他の実行可能なソリューションがありますか、このアイデアを使用してコーディングを開始すると問題ありませんか？
小規模なコレクションを試してください。彼らは良い漸近的な行動を提供するが、時間と空間の両方で隠れた定数が大きすぎるかもしれない。
特に、小さなコレクションの主な関心事であるキャッシュのパフォーマンスが悪い傾向があります。
データが比較的小さいと仮定すると（< 10,000エントリ）、std::vectorは良好なキャッシュパフォーマンスを提供することができます。これはおそらくサイズ係数よりはるかに影響します。だから、それの検索時間でさえも、漸近的に高くなっています。実際には、良いキャッシングのおかげで、両方の方が良いかもしれません。
を使用してvectorをソートしても維持できる場合は、ログ検索の時間とキャッシュの両方の効果が得られます。
（*）この回答は、アプリケーションを展開するハードウェアがCPU-Cacheであることを前提としています。
ベクトル上のバイナリ検索は、トライをナビゲートするよりもキャッシュヒットの方が悪いだろうか？ –
@OliCharlesworth：コレクションが小さいと仮定すると、実際にはキャッシュに収まるかもしれません。多くのオーバーヘッドが発生する傾向があり、キャッシュを「オーバーフロー」させる可能性が非常に高くなります。小さなコレクションの場合、この差は漸近的な動作よりもはるかに重要なものかもしれません – amit
これは私が恐れていたものです.Trieの余分なオーバーヘッドです。今、あなたはキャッシュが大きな違いを持つことができると指摘しました（なぜ私はそれについて考えなかったのかわかりません）。私はこの問題で全く違って見ています。 –
試行は、クイック検索、挿入、削除を提供するなどの目的に最適です。
ここでどのくらいのエントリを話していますか？モバイルデバイスはどれくらい速いのですか？それは本当に複雑なデータ構造を実装する価値がありますか？ – Michael
通常のアドレス帳のサイズ。私は5000人の連絡先（トップ）を言うというだけの人はいないだろうと思う。 –