7

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

我也需要有效的插入，但由于元素的顺序并不重要，我想我可以为它可能必须存储的最大元素数量预先分配内存，然后总是将新元素放在最后，这样就不会重新分配或移动其他元素是必要的。

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

实际上，随机访问要求比我真正需要的要强。我只需要能够随机均匀地选择结构的一个元素。显然有效的访问属性意味着我需要的操作的效率，但我不确定这两者是否等效。

提前致谢！

4

2 回答 2

6

我相信您在问题中暗示的解决方案实际上就是您所需要的，除了一个小细节。

你建议：

我想我可以为它可能必须存储的最大元素数量预先分配内存，然后总是将新元素放在最后，这样就不需要重新分配或移动其他元素。

如果您确实可以建立一个合理的最大条目数，那么我建议您使用该条目数预先分配一个数组（例如，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;
}
于 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 回答