Как сохранить 2 списка объекта

Question

Моя программа на С ++ должна поддерживать 2 списка объектов.

list<A*> inuse;
list<A*> free;

Таким образом, объекты A могут находиться даже в списке «inuse» или в списке «free», но не в обоих.
http://www.cplusplus.com/reference/stl/list/

Я думаю об использовании «списка» в качестве структуры данных для моих списков. Мои вопросы

1. почему я не могу получить случайный доступ к elmenet в списке, я смотрю на API выше, я не вижу способа получить inuse[2];
2. Как удалить элемент из списка? Существует erase (), но как я могу использовать его для удаления элемента # 2? И после того, как я удалю элемент 2? будет ли список STL заполнять стертое место автоматически? например № 3 станет № 2, № 4 станет № 3 и так далее?

Спасибо.

Answer 1

Используйте std :: vector . Имеет произвольный доступ к элементам ([] или at()).

//does NOT check for out of range
myvector[i];

//does check for out of range
myvactor.at(i);

Вы можете удалить элемент из вектора с помощью erase () , и он автоматически обработает отверстия (# 3 становится # 2 и т. Д.)

//erase the 6th element
myvector.erase (myvector.begin()+5);

// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);

Но если вам нужно удалить много объектов 1 на 1, и в списке не может быть двух одинаковых объектов, вы можете попробовать использовать std :: map . Используйте какое-то уникальное свойство объекта в качестве ключа и объект itselt в качестве значения (или самого объекта в качестве ключа и true в качестве значения). Он также имеет аналогичные операторы произвольного доступа [] и erase().

Answer 2

Если вам нужен как быстрый доступ, так и быстрое удаление, рассмотрите std :: set, который должен иметь как поиск в журнале, так и вход / удаление из журнала, при этом все еще сортируемый

Answer 3

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

Либо используйте std::list с линейным временем std::advance для произвольного доступа, либо std::deque (моя рекомендация) или std::vector и принимайте удаление с линейным временем.

Если вы всегда удаляете второй предмет в серии, deque имеет большой шанс сохранить постоянное время удаления. deque похож на vector, но разбит на небольшие куски, связанные с оглавлением.

Или, если ваши данные отсортированы, используйте std::set для удаления в постоянном времени и доступа к журналу (N).

Удаление элемента из середины любого контейнера выполняется с помощью my_container.erase( my_iterator ). Список, вектор, deque, карта, что угодно.

Answer 4

Я бы реализовал списки «inuse» и «free» в виде списков с двойной связью, а затем создал бы массивы «inuse_pointers» и «free_pointers» для хранения указателей на элементы списков. Таким образом, вы можете индексировать в связанный список, используя массив указателей (и избегать необходимости обходить список), и будете поддерживать быстрые операции вставки / удаления в двусвязном списке. Это не типичный подход STL (он был взят из некоторого кода управления кешем на языке C, над которым я сейчас работаю), но я знаю, что он работает и довольно эффективен.

Answer 5

Я много размышляю здесь ... Но ...

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

«Свободный список», как я ожидаю, просто должен позволять вам нажимать и выдвигаться вперед;это стек fifo, который можно использовать для хранения объектов, которые в данный момент не используются, но которые можно использовать, когда требуется выделение, а «свободный список» в настоящее время не пуст.

«Активный список»список всех выделенных в данный момент объектов.Распределителю может потребоваться иметь возможность сообщать об этом, или делать что-то с ними, или что-то еще.«Активный список» требует, чтобы вы могли удалить объект из любого места, когда объект становится освобожденным.Я предполагаю, что затем он помещается в свободный список для повторного использования.

Теперь структуры данных, которые можно использовать для каждого «списка», могут отличаться.Все зависит от точных требований.Я бы сказал, что вы должны иметь возможность использовать std::list<A *> для своего «свободного списка», если я прав в требуемой семантике использования.Если вас не волнует возможность пройти «активный список» в порядке распределения, тогда вы можете использовать std::set<A *> для своего «активного списка».Чтобы избежать необходимости выполнять поиск в наборе для удаления объекта из «активного списка», вы можете сохранить итератор в местоположении объекта в наборе в объекте (этот итератор не станет недействительным, если сам объект не будет удален иззадавать - или так сказать этот ответ , и я не проверял это, но я уверен, что кто-то исправит меня, если я ошибаюсь).Если вам НЕОБХОДИМО иметь возможность обходить «активный список» в порядке распределения, тогда вы можете использовать std::map<size_t, A *> и сохранить в качестве ключа карты увеличивающийся индекс распределения;снова трюк «объект содержит итератор для быстрого стирания» должен работать.

Answer 6

list<> - довольно плохое имя; это на самом деле связанный список. Вы хотите vector<> (шкафчик .Net List<> и Java ArrayList.)

Answer 7

Std :: list - это двусвязный список. Это означает, что у вас есть ряд узлов, содержащих элементы, например,

a <-> b <-> c <-> d.

Когда вы удаляете 'b', происходит то, что указатели корректируются так, что узел a указывает на узел c, а b удаляется, т.е.

а <-> с <->. Д

Причина отсутствия оператора [] состоит в том, что если вы хотите найти 5-й элемент, вам нужно перейти по ссылкам на пятый элемент. Структура данных просто не поддерживает быстрый доступ к определенному местоположению. В массиве или векторе все элементы расположены рядом друг с другом, так что это тривиально. Вы просто добавляете 5 * sizeof (data) к указателю на вершину.

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

Я подозреваю, что на самом деле вам нужен std :: set или std :: map, чтобы вы могли найти элемент и быстро переместить его в другой набор.

Answer 8

A std :: list моделируется после структуры данных с именем двусвязный список .

1. Вы не можете использовать произвольный доступ, поскольку объекты расположены в куче, а указатели на их местоположение сохраняются в предыдущем и следующем элементах. В std :: vector память является непрерывной, и вы можете получить доступ к n-му элементу по смещению * size объекта.

2. Вы удаляете элемент, получая итератор для этого объекта и вызывая std :: list :: erase с этим итератором (или диапазоном). erase возвращает итератор для элемента, на который указывает следующий указатель только что удаленного элемента.

3. Да, место будет заполнено автоматически.

Все сказано, используйте std :: vector, если сомневаетесь.