私は xlsx ビルダーを構築しており、スプレッドシート (xml ファイル) に保存する一連の文字列があります。重複する可能性があるため、文字列をマップに格納してカウントを増やしたいと考えています。次に、文字列を保存する代わりに、マップ内のインデックスを保存し、別の xml ファイルに文字列を保存します。しかし、与えられた文字列のインデックスを取得することは、std::map で O(n) です。これをより速く達成できるデータ構造はありますか?
2 に答える
2
「別のファイル」を辞書順に並べる必要がない限り、マップでインデックスを使用せず、インデックスを明示的に保存します。
したがって、たとえば a map<string, gubbins>, with struct gubbins { size_t count; size_t index; }.
マップに新しいキーを挿入するたびに、そのインデックスにインクリメント カウンターの「次の」値を指定します。
使用されるインデックス値の範囲は、後で来てrefcountをデクリメントし、ゼロに達したときにマップからエントリを削除しない限り、連続しています。その場合、インデックスを「最適化」できますが、インデックスを使用して別の場所で文字列を識別している場合はもちろんできません。
文字列ファイルを書き込む操作では、最初にインデックスでソートする必要があります。線形時間でそれを行うことができます-十分な大きさの配列を作成してから、マップを実行し、各文字列を正しいインデックスに格納します。または、文字列ファイルを作成しながら、マップに追加するときに各文字列を追加することもできます。
すべてを右で行うことはおそらく可能ですboost:multi_index。
于 2013-01-17T17:03:07.677 に答える
0
文字列を並べ替えた順序で格納する必要がある場合は、順序統計ツリーのデータ構造を調べることをお勧めします。これは、ツリー内の n 番目の要素を効率的に決定できるようにする追加情報が追加されたバランスのとれた二分探索ツリーです ( O(log n) 時間)。これにより、 の元の機能のすべてにstd::map加えて、ランダム アクセスが提供されます。
C++ 標準ライブラリには順序統計ツリーの標準実装はありませんが、Google で簡単に検索するといくつか出てくるはずです。
お役に立てれば！
于 2013-01-17T17:04:06.583 に答える