Какая структура данных поддерживает эффективное удаление и произвольный доступ?

Я ищу структуру данных, в которой я могу эффективно удалять элементы, а также поддерживает произвольный доступ.

Мне также нужна эффективная вставка, но поскольку порядок элементов не важен, я подумал, что могу предварительно выделить память для максимального количества элементов, которые она может хранить, а затем всегда помещать новый элемент в конце, чтобы не было необходимости в перераспределении или перемещении других элементов.

Насколько мне известно, связанный список идеально подходит для удаления, но доступ к его элементам может занять O (n) времени. С другой стороны, простой массив (например, vector в C++) обладает свойством произвольного доступа, но удаление элемента из такой структуры имеет сложность O(n).

На самом деле, требование произвольного доступа-это нечто более сильное, чем то, что мне действительно нужно. Я только должен быть в состоянии выбрать элемент структуры равномерно случайным образом. Очевидно, что свойство эффективного доступа подразумевает эффективность операции, в которой я нуждаюсь, но я не уверен, что эти два аналог.

Заранее спасибо!

2 6
arrays c++ list data-structures random-access

2 ответа:

Я считаю, что решение, на которое вы намекаете в своем вопросе, на самом деле то, что вам нужно, за исключением небольшой детали.

Вы предложили:

Я подумал, что могу предварительно выделить память для максимального количества элементов, которые она может хранить, а затем всегда помещать новый элемент в конец, чтобы не было необходимости в перераспределении или перемещении других элементов.

Если вы действительно можете установить разумное максимальное число записей, то я бы предложил вам предварительно выделить массив (например, используя 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;
}
5

Я бы предложил использовать хэш-таблицу . Там вы можете как удалять, так и искать элемент с постоянной сложностью. В C++ вы можете использовать std::unordered_map (C++11) или boost::unordered_map(pre-C++11), а в java - HashMap.

1