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

Question

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

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

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

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

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

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

6

arrays c++data-structures list random-access

Решение

Другие решения

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

1

Источник

Accepted Answer

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

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

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

Если действительно вы можете установить разумное максимальное количество записей, то я бы посоветовал вам предварительно выделить массив (например, используя std::array если максимум известен во время компиляции, или std::vector в противном случае с этим количеством записей установите количество элементов (для подсчета количества элементов, хранящихся в данный момент) и действуйте следующим образом:

Первоначально вы установите счетчик на 0
Когда вы вставляете элемент, вы добавляете его в конец и увеличиваете количество
Когда вы удаляете элемент, вы поменяйте местами с последним элементом и уменьшить счет
Для произвольного доступа (в том смысле, в котором вы его описали, т. Е. Буквально выбираете элемент случайным образом), вы определяете случайное число от 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;
}

6