элемент pop-push из std::vector и повторное использование элементов

у меня есть проект на С++ 03, у которого есть проблема со структурой данных: я использую вектор вместо списка, даже если мне приходится постоянно делать push_front-push_back. но пока все в порядке, потому что мне нужно переписать слишком много кода.

мой подход заключается в том, чтобы буфер последней точки frame_size всегда обновлялся. поэтому в каждом кадре я должен выдвигаться вперед и отталкиваться назад. (может быть, есть название для этого подхода?)

поэтому я использую этот код:

Point apoint;  // allocate new point
apoint.x = xx;
apoint.y = yy;

int size = points.size()
if (size > frame_size) {
    this->points.erase( points.begin() );  // pop_front
}
this->points.push_back(apoint);

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

хорошо, это не так полезно и, вероятно, не имеет смысла, но я спрашиваю только из образовательного любопытства: как я могу это сделать?

как я могу сохранить память стертого элемента вектора для его повторного использования? этот вопрос имеет смысл? если нет, то почему?

.. поскольку стирание не возвращает стертый вектор, оно возвращает:

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


c++ std vector object-pooling erase
person nkint    schedule 27.02.2012    source источник
comment
Если вы постоянно pop_front и не хотите использовать list, то почему бы и std::deque?   -  person Sebastian Mach    schedule 27.02.2012
comment
проблема в том, что у меня есть много утилит, которые используют std::vector, поэтому мне нужно открыть репозиторий утилиты, разветвить его и шаблонировать (или переписать) все, что берет вектор, чтобы сделать его пригодным для использования для списка или deque   -  person nkint    schedule 27.02.2012
comment
Является ли создание Point тяжеловесным? Вы храните объекты, а не указатели на объекты в векторе. Если вы хотите сохранить объекты в пуле, рекомендуется хранить их как указатели, а не как объекты.   -  person Jagannath    schedule 27.02.2012
comment
Если вы push_back() сразу после erase(), то для нового объекта уже выделена память. Вектор не уменьшает емкость, когда вы стираете ее. Однако объект не будет построен в одном и том же месте, но, вероятно, это не главное, верно?   -  person jrok    schedule 27.02.2012
comment
@Jagannath: я думаю, точка, это не так уж тяжело, но для пула объектов это хорошо, если подумать, что он тяжелый, не так ли? Спасибо за совет.   -  person nkint    schedule 27.02.2012
comment
@jrok: я думаю, что тяжелая часть, в которой должен помочь пул объектов, - это создание нового объекта, а не только памяти, может быть, я плохо объяснил себя ..   -  person nkint    schedule 27.02.2012

Ответы (2)


arrow_upward
2
arrow_downward

у меня есть готовый код для пула объектов... как мне это сделать?

Используя вектор, вы не можете. Вектор хранит свои элементы в непрерывном массиве, поэтому их нельзя размещать по одному, а только блоками произвольного размера. Поэтому вы не можете использовать пул объектов в качестве распределителя для std::vector.

как я могу сохранить память стертого элемента вектора для его повторного использования? этот вопрос имеет смысл? если нет, то почему?

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

Пока вы используете вектор, вы не можете избежать перемещения всех элементов при стирании первого; если это слишком неэффективно, используйте вместо этого deque (или, возможно, list).

person Mike Seymour    schedule 27.02.2012

arrow_upward
1
arrow_downward

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

// don't do this on an empty vector
assert (points.size() > 0);

// rotate elements in the vector, erasing the first element
// and duplicating the last one
copy (points.begin()+1, points.end(), points.begin());

// overwrite the last element with your new data
points.back().x = xx;
points.back().y = yy;

EDIT: Как отметил Майк Сеймур в комментариях, ни это решение, ни подход, предложенный в вопросе, не вызывают нового выделения памяти.

person François Févotte    schedule 27.02.2012
comment
Последние 2 утверждения должны быть внутри условия if? - person Jagannath; 27.02.2012
comment
Просто удалите условие if и должно быть хочу, чтобы @nkint хотел. - person Jagannath; 27.02.2012
comment
@Jagannath оба способа должны быть эквивалентны, но вы правы: ваш более элегантный и компактный. - person François Févotte; 27.02.2012
comment
таким образом, мне не нужно использовать пул. но в общем случае, если я хочу использовать бассейн? как мне это сделать? - person nkint; 27.02.2012
comment
Обратите внимание, что код в вопросе также не выделяет новую память - vector будет выделять только тогда, когда ей нужно расти. Использование copy может быть менее эффективным, так как оно явно копирует объекты, тогда как erase может их перемещать. - person Mike Seymour; 27.02.2012
comment
@MikeSeymour, возможно ли, что вызов erase() приведет к тому, что вектор освободит некоторое пространство, поскольку его размер уменьшится? В противном случае вы правы: erase может перемещать объекты, а не копировать их (но поскольку Point выглядит как обычный struct, я сомневаюсь, что в этом случае перемещение будет более эффективным, чем копирование). - person François Févotte; 27.02.2012
comment
@Francesco: стирание любого элемента, кроме первого, не может привести к перераспределению, поскольку ссылки на элементы перед стертым должны быть сохраненыc. Теоретически сумасшедший разработчик может проверить особый случай стирания первого элемента и перераспределить его в этом случае; Я сомневаюсь, что какой-либо реальный разработчик подумает, что сохранение памяти одного элемента в одной конкретной ситуации стоит затрат на производительность и связанную с этим фрагментацию памяти. - person Mike Seymour; 27.02.2012
comment
Класс Point — это структура координат и множество методов векторной алгебры. это важно для перераспределения? - person nkint; 27.02.2012