14

空の配列が与えられた場合、2種類のクエリを実行する必要があります

  1. 配列に要素を挿入する

  2. いくつかの要素kのインデックスを見つける（明らかに配列はソートされたままでなければなりません）

これは、setコンテナを使用して行うことができます

set<int> st;
set.insert(t);

これにより、私の要素がに挿入されO(log(n))ます。

そして2番目のクエリの場合

set<int>::iterator it;
it = st.find(k);
idx = distance(st.begin(), it);

これにはO(n)時間がかかります。（O(n)[for distance()[+ O(log(n)[for set::find()]）。

O(log(n))C ++の事前定義されたコンテナを使用して両方のクエリを実行する方法はありますか？

http://www.cplusplus.com/reference/stl/

4

3 に答える 3

5

インデックスによるアクセスをサポートするには実装を変更する必要があるため（各ノードにカウンターを追加する）、標準ライブラリのコンテナーではこれが可能ではないと思います。これにより、各ノードのサイズが大きくなります。そして C++ の哲学は、「使わないものにはお金を払わない」です。

これが本当に必要な場合は、要件を満たすブースト用に提案されたカウンターツリー実装があります (そして、少なくとも C++11 機能の一部をサポートしています)。

于 2013-02-04T18:13:58.323 に答える
4

いいえ。できません（事前定義されたコンテナを使用）。C++標準ライブラリのシーケンスコンテナには次のいずれかがあります。

  • O（1）ランダムアクセスおよびO（N）挿入/削除または
  • O（N）ランダムアクセスおよびO（1）挿入/削除

これは例外であることに注意してくださいdeque。ただし、挿入/削除がアレイの最後で行われる場合に限ります。一般的なケースはまだO（N）です。

さらに、イテレータの分類には、この場合のカテゴリは含まれていません。ランダムな位置にジャンプするのにO（N）時間がかかる双方向イテレータ（、、、、および）があり、次のカテゴリはランダムlistアクセスイテレータ（set、、、および）用です。中間カテゴリはありません。multisetmapmultimapvectordequestring

新しいカテゴリを追加することは、まったく簡単なことではありません。for_eachライブラリは、コンテナで機能する多くのアルゴリズム（など）も実装しています。すべてのイテレータカテゴリに実装があります。

注文統計ツリーは、 Boostで数回提案されています。私の知る限りでは：

  1. 2004年：最初の提案（実装されたかどうかはわかりません）
  2. 2006年：「階層データ構造」
  3. 2006：AVLアレイ（Boostで「ランクリスト」に名前が変更されました）
  4. 2012：カウンターツリー

それらが受け入れられることの主な困難は、それらが利益ではなく危険であるという一般的な意見でした。今日のプログラマーは、典型的なコンテナーで知っているすべての問題を解決するために使用されています。経験豊富なプログラマーは、初心者が慎重に選択するのではなく、提案されたコンテナーをすべてに盲目的に使用する可能性があることを恐れています。

于 2013-02-05T16:04:57.093 に答える