どのデータ構造が効率的な削除とランダムアクセスをサポートしていますか？

Question

私はアイテムを効率的に削除し、ランダムアクセスをサポートできるデータ構造を探しています。

また、効率的な挿入が必要ですが、要素の順序は重要ではないため、格納する必要のある最大数の要素に対してメモリを事前に割り当ててから、新しい要素を最後に配置して、他の要素の移動が必要です。

私の知る限りでは、リンクされたリストは削除には最適ですが、要素にアクセスするとO（n）時間かかることがあります。反対に、単純な配列（例えば、C++のvector）はランダムアクセスプロパティを有するが、このような構造から要素を削除することはO（n）の複雑さを有する。

実際、ランダムアクセスの要件は、実際に必要なものよりも強いものです。構造の要素を無作為に一様に選ぶことができればいいだけです。明らかに効率的なアクセスプロパティは、私が必要とする操作の効率性を意味しますが、その2つが同等かどうかはわかりません。

ありがとうございます！

Answer 1

私はあなたの質問であなたが知っている解決策は、実際にはあなたが必要とするものだと信じています。

あなたが示唆した：

を私はそれを保存するために持っており、他の要素のない再配分や移動が必要でないように、常に最後に新しい要素を置いてもよい要素の最大数のためにメモリを事前に割り当てることができます思いました。あなたがエントリの合理的な最大数を確立できる確かならば

、その数と、私はあなたが、配列を事前に割り当てることをお勧め（最大は、コンパイル時にわかっている場合などは、std::arrayを使用して、またはその他std::vector）エントリは、（現在保存されている要素の数をカウントする）の要素数を確立し、次のように進む：あなたは要素を挿入すると

1. が最初あなたは0
2. にカウント数を設定し、あなたが最後にそれを追加しますカウントをインクリメントします。
3. 要素を削除すると、は最後の要素で置き換えられますとカウントを減らします
4. ランダムアクセス（つまり、文字通りランダムに要素を選択するという意味で）ランダムアクセスの場合は、0からcountまでの乱数を決定します、と私は変更のみ、詳細は、私はあなたが最後の要素とスイッチの位置として実装示唆要素の削除、あるその要素

を選びます。

可能な実装：

#include <vector> 
#include <utility> 
#include <iostream> 

template <typename Elem> 
class randomaccesstable 
{ 
public: 
    randomaccesstable(std::size_t initial_size) 
    : data_(initial_size) , count_(0) 
    { } 

    randomaccesstable &push_back(const Elem &elem) 
    { 
    if (count_ < data_.size()) 
     data_[count_++] = elem; 
    else { 
     data_.push_back(elem); 
     ++count_; 
    } 
    return *this; 
    } 

    randomaccesstable &remove(const std::size_t index) 
    { 
    if (index < count_) 
    { 
     std::swap(data_[index],data_[count_-1]); 
     --count_; 
    } 
    return *this; 
    } 

    const Elem &operator[](const std::size_t index) const 
    { return data_[index]; } 

    Elem &operator[](const std::size_t index) 
    { return data_[index]; } 

    std::size_t size() const 
    { return count_; } 

private: 
    std::vector<Elem> data_; 
    std::size_t  count_; 
}; 

int main() 
{ 
    randomaccesstable<int> table(10); 
    table.push_back(3); 
    table.push_back(12); 
    table.push_back(2); 

    for (std::size_t i = 0 ; i < table.size() ; ++i) 
    std::cout << table[i] << ' '; 
    std::cout << '\n'; 

    table.remove(1); // this removes the entry for 12, swapping it for 2 

    for (std::size_t i = 0 ; i < table.size() ; ++i) 
    std::cout << table[i] << ' '; 
    std::cout << '\n'; 

    return 0; 
} 

Answer 2

hash tableを使用することをお勧めします。そこでは、一定の複雑さで要素を削除したり検索したりすることができます。 C++では、std::unordered_map（C++ 11）またはboost::unordered_map（pre-C++ 11）とjava-HashMapを使用できます。