Есть ли эквивалент vector:: reserve() для std:: list?

У меня есть класс, который выглядит так:

typedef std::list<char*> PtrList;
class Foo
{
public:
   void DoStuff();
private:
   PtrList m_list;
   PtrList::iterator m_it;
};

Функция DoStuff() в основном добавляет элементы в m_list или стирает из нее элементы, находит итератор в каком-то специальном элементе в нем и сохраняет его в m_it. Важно отметить, что каждое значение m_it используется при каждом следующем вызове DoStuff().

Итак, в чем проблема? Все работает, за исключением того, что профилирование показывает, что оператор new вызван слишком сильно из-за list::push_back(), вызванного из DoStuff().

Чтобы увеличить производительность, я хочу предварительно выделить память для m_list в инициализации Foo, как я бы сделал, если бы это был std::vector. Проблема в том, что это приведет к появлению новых проблем, таких как:

  • Менее эффективные элементы insert и erase.
  • m_it становится недействительным, как только вектор изменяется с одного вызова на DoStuff() на следующий. EDIT: Алан Стокс предложил использовать индекс вместо итератора, решая эту проблему.

Мое решение: Самое простое решение, о котором я подумал, - это реализовать пул объектов, который также имеет функциональность связанного списка. Таким образом, я получаю связанный список и могу выделить память для него.

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

Любые мысли, обходные пути или просветляющие комментарии будут оценены!

Ответы

Ответ 1

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

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

Лучшим контейнером является std:: deque. Дека - это в основном массив массивов. Он выделяет блок памяти и занимает его, когда вы нажимаете назад, когда он заканчивается, он выделяет другой блок. Это означает, что он распределяется очень редко, и вам не нужно заранее знать размер контейнера для эффективности, например std::vector и reserver.

Ответ 2

Вы можете использовать функцию splice в std::list для реализации пула. Добавьте новую переменную участника PtrList m_Pool. Если вы хотите добавить новый объект и пул не пуст, назначьте значение первому элементу в пуле и затем соедините его в списке. Чтобы стереть элемент, соедините его из списка с пулом.

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

Ответ 3

Мой совет такой же, как 111111, попробуйте переключиться на deque, прежде чем писать какой-либо значительный код.

Однако для прямого ответа на ваш вопрос: вы можете использовать std::list с помощью специального распределителя. Это немного странно, и я не собираюсь описывать все подробности здесь, но суть в том, что вы пишете класс, представляющий стратегию распределения памяти для узлов списка. Узлы, выделенные list, будут представлять собой небольшую размерную реализацию, превышающую char*, но все они будут одинакового размера, что означает, что вы можете написать оптимизированный распределитель только для этого размера (пул блоков памяти, а не пул объектов), и вы можете добавить к нему функции, которые позволят вам зарезервировать любое пространство, которое вы хотите в распределителе, в то время, когда захотите. Затем список может выделяться/освобождаться быстро. Это избавит вас от необходимости повторно использовать любую из фактических функциональных возможностей list.

Если бы вы (по какой-то причине) собирались реализовать пул объектов с функциональностью списка, то вы могли бы начать с boost::intrusive. Это также может быть полезно при написании собственного распределителя, чтобы отслеживать список свободных блоков.

Ответ 4

Может потенциально использовать list::get_allocator().allocate(). Afaik, поведение по умолчанию заключалось бы в том, чтобы получить память как и из-за несмежного характера list - следовательно, отсутствие reserve() - но никаких серьезных недостатков с использованием метода allocator не возникает сразу. Если у вас есть некритический раздел в вашей программе, в начале или в любом случае, вы можете по крайней мере выбрать, чтобы получить урон в этой точке.

Ответ 5

Список и вектор полностью различаются в способе управления объектами.

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

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

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