7

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

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

私の知る限り、リンクされたリストは削除に最適ですが、その要素へのアクセスには O(n) 時間がかかる場合があります。一方、単純な配列 ( vectorC++ など) にはランダム アクセス プロパティがありますが、そのような構造から要素を削除すると O(n) の複雑さが生じます。

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

前もって感謝します！

4

2 に答える 2

6

あなたの質問で示唆している解決策は、細部を除いて、実際に必要なものだと思います。

あなたは提案しました：

格納する必要がある要素の最大数にメモリを事前に割り当ててから、常に新しい要素を最後に配置して、他の要素の再割り当てや移動が不要になるようにすることができると思いました。

実際にエントリの妥当な最大数を確立できる場合は、そのエントリ数で配列を事前に割り当て (たとえばstd::array、コンパイル時に最大値がわかっている場合などに使用std::vector)、要素数を確立することをお勧めします (現在保存されている要素の数を数えます)、次のように進みます。

  1. 最初にカウントを0に設定します
  2. 要素を挿入するときは、最後に追加してカウントを増やします
  3. 要素を削除すると、それを最後の要素と交換し、カウントを減らします
  4. ランダムアクセス（説明した意味で、つまり文字通り要素をランダムに選択する）の場合、0とカウントの間の乱数を決定し、その要素を選択します

私が変更した唯一の詳細は要素の削除です。これは、最後の要素でスイッチ位置として実装することをお勧めします。

可能な実装:

#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;
}
于 2013-03-07T14:49:59.147 に答える
1

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

于 2013-03-07T13:34:02.420 に答える