哪种数据结构支持有效删除和随机访问？

Question

我正在寻找一种数据结构,我可以在其中有效地删除项目,并支持随机访问.

我还需要有效的插入,但由于元素的排序并不重要,我认为我可以预先分配内存以获得它可能必须存储的最大数量的元素,然后始终将新元素放在最后,以便不重新分配或移动其他元素有必要的.

据我所知,链表很适合删除,但访问其元素可能需要O(n)时间.另一方面,简单数组(例如,vector在C++中)具有随机访问属性,但是从这种结构中删除元素具有O(n)的复杂性.

实际上,随机访问要求比我真正需要的要强.我只需要能够随机均匀地选择结构的元素.显而易见的高效访问属性意味着我需要的操作效率,但我不确定这两者是否相同.

提前致谢!

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;
}