[Алгоритмы] Структура данных для пула объектов

[shmaser]

Доброго времени суток, прошу помочь разобраться по следующий вопросам:

1. Видел много реализаций пула объектов через массив, есть ли какие-либо преимущества/недостатки реализации в виде самописного односвязного списка? Кто-то вообще так делает? Как минимум, список позволит избежать реаллокации памяти на первых порах, пока пул расширяется и, наверное, доступ по ссылке будет быстрее чем по индексу.
2. Когда необходимо удалять элементы в неупорядоченном массиве, встречал реализацию когда последний элемент ставят вместо удаляемого и хранят реальную длину массива в отдельной переменной. Является ли данный подход альтернативой спискам? Т.е. получается что можно легко изменять элементы в коллекции и при этом иметь доступ к любому элементу по индексу. Т.е. имеем преимущества как списков так и массивов (рассматриваются только неупорядоченные данные).

В общем, интересуют любые размышления по этим вопросам.

[Babylon]

В обоих случаях вы будете иметь дело со ссылками. Выбор способа представления данных зависит от цели и способа их обработки.

[shmaser]

Выбор способа представления данных зависит от цели и способа их обработки.

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

[Babylon]

Если вы используете Dictionary доступ осуществляется по ссылке. Какой смысл в односвязном списке?

[Akopalipsis]

Еще ни одной реализации не видел пула в виде списка

Вы меня извините за глупый вопрос - что такое список?
я понимаю тему настолько, что могу обьяснить пользу от удаления последнего элемента пула,
по тому что менее используемый. Так же могу сказать, что использовать Dictionary удобно в случаи получения по ключу. Тут наверное подход зависит от того, для чего он нужен.
Но я это сказал всё для того, чтобы больше шансов было на получения ответа на мой вопрос

[Frost47rus]

Список в ас3 - это Vector<>.
Хотя, в контексте, сам не могу понять какое именно значение вкладывает автор в это слово.
Я не совсем понял, что автор хочет. Хранить в обычном массиве объекты разных типов?
Если да, то сразу же первый вопрос - зачем?
Если нет, то вопрос второй - в чем суть поста?

[alexcon314]

1. Связный список не имеет нативной реализации в AS 3. Потому и примеров нету. Самописный? Попробовать можно, почему нет? Но вряд ли это будет быстрее вектора.
2. Зачем что-то удалять из пула? (глобальная зачистка не в счет).
Может быть стоит сделать что-то простое? Не стоит заниматься преждевременной оптимизацией.
Akopalipsis, http://ru.wikipedia.org/wiki/Связный_список же

[Akopalipsis]

Akopalipsis, http://ru.wikipedia.org/wiki/Связный_список же

Это композиция же?)

[shmaser]

1. Связный список не имеет нативной реализации в AS 3. Потому и примеров нету. Самописный? Попробовать можно, почему нет? Но вряд ли это будет быстрее вектора.

Да, все верно самописный. У меня существует уже реализация связного списка, которую я использую для других действий, вот задумался над вопросом стОит ли использовать такую структуру данных в качестве пула. Оператор квадратной скобки для доступа к Vector/Array достаточно медленный, а с использованием связного списка доставать элементы можно будет по ссылкам.

Зачем что-то удалять из пула? (глобальная зачистка не в счет).

Второй вопрос никак не связан с пулом, он чисто абстрактный. Раньше я списки не использовал вообще, в массивах где требовалось удалять/добавлять элементы городились костыли, во избежание методов splice(), push(), pop() и т.п. С одной стороны, используя списки можно экологично-чисто изменять длину коллекции, с другой, способом, описанным выше:

…последний элемент ставят вместо удаляемого и хранят реальную длину массива в отдельной переменной.

можно делать тоже самое. Вопрос в том, что не могу четко определить для себя что лучше

Может быть стоит сделать что-то простое? Не стоит заниматься преждевременной оптимизацией.

Дело в том, что на данном этапе у меня грядет лютый рефакторинг практически во всем и пул объектов - одна из его частей

[Anton Riot]

Сообщение от shmaser

…последний элемент ставят вместо удаляемого и хранят реальную длину массива в отдельной переменной.

зачем отдельной, длину можно устанавливать, изменяя поле length.