Что такое хорошая структура данных с быстрой вставкой + удалением и частичным обращением?

Question

Что такое хорошая структура данных с быстрой вставкой + удалением и частичным обращением?

Я пишу алгоритм на C ++, и для этого мне нужна структура данных для хранения последовательности n Точки данных. То есть я хочу хранить элементы v[0],v[1],...,v[n-1], Я забочусь о заказе.

Операции, которые я хотел бы выполнить быстро:

Последовательный доступ (то есть доступ к v[0], затем v[1] и так далее с возможностью редактирования значений);
Перемещение точки, т.е.

{v[0],v[1],...,v[i],v[i+1],...,v[j-1],v[j],v[j+1],...,v[n-1]} -> {v[0],v[1],...,v[i],v[j],v[i+1],...,v[j-1],v[j+1],...,v[n-1]};
Частичная реверсия, т.е.

{v[0],...,v[i],v[i+1],...,v[j-1],v[j],v[j+1],...,v[n-1]} -> {v[0],...,v[i],v[j],v[j-1],...,v[i+1],v[j+1],...,v[n-1]},

Кажется, что я могу реализовать свой алгоритм, используя XOR-связанный список, и это даст наименьшую сложность (операции выше будут O(1), давая O(n^2) для моего алгоритма). Но я знаю, что XOR-связанный список считается «некрасивой структурой данных» ([1], [2]).

Что такое хорошая структура данных для этого, чем? Точнее, существует ли какая-либо другая часто используемая структура данных, реализующая эти операции в O(1) время?

2

bitwise-xor c++c++11 data-structures linked-list

Решение

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

Я бы просто использовал std::vector<T>, тогда ищите потенциально более эффективную структуру данных, только если вы обнаружите, что на практике операции слишком дороги.

Последовательный доступ std::vector<T> чрезвычайно эффективно.
std::rotate алгоритм будет работать на операцию 2.
std::reverse алгоритм будет работать на операцию 3.

Указанные алгоритмы находятся в <algorithm> заголовок.

0

Источник

Accepted Answer

Это зависит от гораздо большего количества факторов, которые вы не упомянули.

Во-первых, это зависит от размера ваших элементов и их кода копирования. Если у вас есть небольшие элементы (около 64 байтов или меньше) и что их копирование (или перемещение) обходится дешево (или даже тривиально (в смысле POD-типа)), тогда используйте std::vector вероятно, будет очень хорошим выбором, даже с «худшими» временными сложностями (кстати, как совет на будущее, не слишком зацикливайтесь на погоне за минимальной временной сложностью, это только одна часть всей истории ).

Это особенно верно, если ваши элементы тривиальный, потому что операция поворота в векторе будет очень быстрой (хотя все еще O (n)), в то время как другие операции одинаковы с точки зрения сложности времени по сравнению со связанным списком.

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

Если ваши элементы настолько малы, что вы планируете использовать XOR-связанный список (чтобы сэкономить один указатель на элемент), то, скорее всего, вам вообще не следует использовать связанный список. И если честно, я не уверен, что XOR-связанный список действительно того стоит (но я не хочу вдаваться в подробности).

В целом, я бы сказал, что вы должны тестовое задание эти три варианта: связанный список (либо std::forward_list или же std::list), std::vectorили вектор указателей (например, std::vector< std::unique_ptr<T> >). Другим выбором может быть развернутый связанный список, но это будет хорошо только в конкретном режиме факторов, которые я упомянул.

И я повторяю, я сказал тестовое задание их, потому что это действительно единственный способ узнать, что лучше. «Анализ» предназначен только для практических правил, не более, согласно одной из моих любимых цитат:

Насколько законы математики относятся к реальности, они не являются определенными; насколько они уверены, они не относятся к реальности. (Альберт Эйнштейн)

1