挿入のための効率的なデータ構造

Question

私は構造に値を任意に挿入する高速（O（N）より速い）を可能にするデータ構造（配列のようなもの）を探しています。データ構造は、要素を挿入された形で印刷することができなければなりません。これは、List.Insert（）のようなものです（ランダムにアクセスまたは削除する必要がないことを除いて、すべての要素を移動するには遅すぎます）。挿入は常に '配列'のサイズ内になります。すべての値は一意です。他の操作は必要ありません。

たとえば、Insert（x、i）が値xをインデックスi（0インデックス）に挿入するとします。その後：

• インサート（1、0）{1}
• 挿入与える（3、1）{1,3}
• 挿入与える（2、1）{1,2,3}を与えます
• インサート（5、0）{5,1,2,3}

を与え、それが最後に{5,1,2,3}をプリントアウトできるようにする必要があります。

私はC++を使用しています。

Answer 1

skip listを使用してください。別のオプションはtiered vectorである必要があります。スキップリストはconst O（log（n））に挿入を行い、順番に番号を保持します。階層化されたベクトルはO（sqrt（n））に挿入をサポートし、要素を順に印刷することができます。

EDIT：アミットのコメントごとに、私はあなたがスキップリストにk番目の要素を見つけるのです方法を説明します：

各要素についてあなたが次の要素に、あなたが知っている各リンクのリンク上のタワーを持っていますいくつの要素が飛び越えますか？だから、k番目の要素を探して、リストの先頭から始め、k要素以上にジャンプしないリンクを見つけるまで、塔の下に行く。このノードが指すノードに行き、ジャンプした要素の数でkを減らします。やって続けているユーザーは、k = 0あなただけそうのように、ベクトルのマップを使用することができ、C++で

Answer 2

std::mapまたはstd::vectorをお使いですか？

std::mapをキーとして挿入ランクで使用できます。 vectorにはメンバー関数reserveがあります。

Answer 3

持つまで：

int main() { 
    map<int, vector<int> > data; 
    data[0].push_back(1); 
    data[1].push_back(3); 
    data[1].push_back(2); 
    data[0].push_back(5); 
    map<int, vector<int> >::iterator it; 
    for (it = data.begin(); it != data.end(); it++) { 
    vector<int> v = it->second; 
    for (int i = v.size() - 1; i >= 0; i--) { 
     cout << v[i] << ' '; 
    } 
    } 
    cout << '\n'; 
} 

この版画：ちょうどあなたが望むような

5 1 2 3 

を、挿入はO（log n）です。

Answer 4

マッピング時間（インデックス、挿入時間）のペアを値に使用することができます。ここで、挿入時間は「自動インクリメント」整数（SQLの場合）です。ペアの順序は、コードで

i < i* or t > t* 

IFF

(i, t) < (i*, t*) 

次のようになります。

struct lt { 
    bool operator()(std::pair<size_t, size_t> const &x, 
        std::pair<size_t, size_t> const &y) 
    { 
     return x.first < y.first || x.second > y.second; 
    } 
}; 

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like; 

void insert(array_like &a, int value, size_t i) 
{ 
    a[std::make_pair(i, a.size())] = value; 
} 

Answer 5

あなたのコメントについて：ある

List.Insert（）（すべての要素をシフトしなければならないほど遅い）

リストは値をシフトしないで、挿入する位置を見つけるために繰り返します。あなたの言うことに注意してください。これは私のような初心者に混乱することがあります。

Answer 6

デフォルトでGCCに含まれている解決策は、ロープデータ構造です。ここにはdocumentationがあります。通常、長い文字列で作業する場合、ロープが気になります。ここでは文字の代わりにintがありますが、それは同じように動作します。ちょうどintをテンプレートパラメータとして使用してください。 （pairなど）

ここにはdescription of rope on Wikipediaがあります。

基本的には、左右のサブツリーに含まれる要素の数（または注文統計と呼ばれるもの）を維持するバイナリツリーです。これらのカウントは、要素が挿入され、削除されます。これにより、O（lg n）の操作が可能になります。