Предотвращение аннулирования итераторов с помощью индексов, поддержание чистого интерфейса

Question

Предотвращение аннулирования итераторов с помощью индексов, поддержание чистого интерфейса

Я создал MemoryManager<T> класс, который в основном является оберткой вокруг двух векторов указателей, управляющих временем жизни объектов, выделенных кучей.

Один вектор хранит «живые» объекты, другой хранит объект, который будет добавлен в следующий MemoryManager<T>::refresh,

Этот дизайн был выбран, чтобы избежать аннулирования итератора при циклическом MemoryManager<T>как добавление нового объекта непосредственно в MemoryManager<T>::alive вектор может сделать недействительными существующие итераторы (если он увеличится в размере).

template<typename T> struct MemoryManager {
std::vector<std::unique_ptr<T>> alive;
std::vector<T*> toAdd;

T& create() {
auto r(new T);
toAdd.push_back(r);
return *r;
}

T& refresh() {
// Use erase-remove idiom on dead objects
eraseRemoveIf(alive, [](const std::unique_ptr<T>& p){ return p->alive; });

// Add all "toAdd" objects and clear the "toAdd" vector
for(auto i : toAdd) alive.emplace_back(i);
toAdd.clear();
}

void kill(T& mItem)  { mItem.alive = false; }

IteratorType begin() { return alive.begin(); }
IteratorType end()   { return alive.end(); }
}

Я использую его в своем игровом движке для хранения сущностей и обновляю каждую «живую» сущность каждый кадр:

void game() {
MemoryManager<Entity> mm;

while(gameLoop) {
mm.refresh();
for(auto e : mm) processEntity(e);
auto& newEntity = mm.create();
// do something with newEntity
}
}

Это позволило мне постоянно создавать / убивать сущности, не беспокоясь об их жизни.

Тем не менее, я недавно пришел к выводу, что с использованием двух std::vector не нужно Я мог бы просто использовать один вектор и сохранить итератор в «последнем живом объекте», добавляя вновь созданные объекты сразу после вышеупомянутого итератора:

Диаграмма предполагаемого одно-векторного поведения

Идея, на мой взгляд, работает нормально … но я не могу использовать тип итератора для end (как показано на диаграмме), так как он может стать недействительным после добавления некоторых новых элементов в вектор. Я проверял это, и это часто случается, вызывая сбой.

Другое решение, которое я могу придумать, — использовать индекс вместо итератора. Это решило бы сбой, но я не смог бы использовать крутой C ++ 11 for(x : y) цикл foreach, потому что MemoryManager<T>::begin а также MemoryManager<T>::end нужно вернуть итератор.

Есть ли способ добиться текущего поведения с помощью одного вектора и при этом поддерживать понятный интерфейс, который можно использовать с циклами C ++ 11 for-each?

9

c++c++11 invalidation iterator vector

Решение

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

Одним из самых простых способов получить стабильные итераторы (и ссылки) является использование std::list<T>, И если вам не нужно T чтобы быть указателем на полиморфный базовый класс, лучше использовать std::list<T>в отличие от std::list<std::unique_ptr<T>>,

Если с другой стороны, ваш Entity является полиморфным основанием, тогда рассмотрите возможность использования std::vector<std::unique_ptr<T>>, Хотя вы не можете зависеть от того, что итераторы остаются действительными, вы Можно зависит от указателей и ссылок на Entity остается в силе с std::vector<std::unique_ptr<T>>,

В вашем game() Например, вы никогда не пользуетесь стабильными итераторами или указателями. Вы могли бы так же легко (и более просто) сделать:

void game() {
std::vector<Entity> mm;

while(gameLoop) {
mm.erase(std::remove_if(mm.begin(), mm.end(), [](const Entity& e)
{ return e.alive; }),
mm.end());
for(auto e : mm) processEntity(e);
mm.push_back(create());
auto& newEntity = mm.back();
// do something with newEntity
}
}

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

Но если вам действительно нужны стабильные итераторы / ссылки, подставив в std::list<Entity> было бы очень легко. Я бы поменял erase/remove использовать listчлен remove_if вместо. Это будет более эффективным.

Если вы сделаете это, а также тестирование производительности (не догадываясь) показывает, что вы потеряли производительность по сравнению с существующим MemoryManagerможно оптимизировать list используя «распределитель стека», такой как продемонстрированный здесь:

http://howardhinnant.github.io/stack_alloc.html

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

В итоге:

Узнайте / сообщите нам, если unique_ptr<Entity> на самом деле необходимо, потому что Entity это базовый класс. предпочитать container<Entity> над container<unique_ptr<Entity>>,
Вы действительно нуждаетесь в стабильности итератора / указателя / ссылки? Ваш пример кода нет. Если вам это на самом деле не нужно, не платите за это. использование vector<Entity> (или же vector<unique_ptr<Entity>> если вы должны).
Если вам действительно нужно container<unique_ptr<Entity>>Можете ли вы избежать стабильности указателя / ссылки, жертвуя стабильностью итератора? Если да, vector<unique_ptr<Entity>> это путь.
Если вам действительно нужна стабильность итератора, настоятельно рекомендуем использовать std::list,
Если вы используете std::list и обнаружив при тестировании проблемы с производительностью, оптимизируйте его с помощью распределителя, настроенного на ваши потребности.
Если все вышеперечисленное не помогает, затем начать разработку собственной структуры данных. Если вы зашли так далеко, знайте, что это самый сложный маршрут, и все должно быть подтверждено тестами на правильность и производительность.

9

Вы можете избежать перемещения элементов контейнера, поддерживая свободный список (см. http://www.memorymanagement.org/glossary/f.html#free.list).

Чтобы избежать аннулирования ссылок на элементы, вы можете использовать std :: deque, если вы не вставляете или не стираете в середине.
Чтобы избежать аннулирования итераторов, вы можете использовать std :: list.

(Спасибо, Говард Хиннант)

2

Вы можете реализовать свой собственный класс итератора, который обрабатывает вещи так, как вы предпочитаете. Тогда ваши begin () и end () могут возвращать экземпляры этого класса. Например, ваш пользовательский итератор может хранить целочисленный индекс и указатель на сам вектор, тем самым делая итератор действительным даже при перераспределении.

0

Источник

Accepted Answer

Вы можете реализовать свой собственный класс итератора.

Может помочь что-то вроде следующего.

template <typename T, typename... Ts>
class IndexIterator : public std::iterator<std::random_access_iterator_tag, T>
{
public:
IndexIterator(std::vector<T, Ts...>& v, std::size_t index) : v(&v), index(index) {}

// if needed.
typename std::vector<T, Ts...>::iterator getRegularIterator() const { return v->begin() + index; }

T& operator *() const { return v->at(index); }
T* operator ->() const { return &v->at(index); }

IndexIterator& operator ++() { ++index; return *this;}
IndexIterator& operator ++(int) { IndexIterator old(*this); ++*this; return old;}
IndexIterator& operator +=(std::ptrdiff_t offset) { index += offset; return *this;}
IndexIterator operator +(std::ptrdiff_t offset) const { IndexIterator res (*this); res += offset; return res;}

IndexIterator& operator --() { --index; return *this;}
IndexIterator& operator --(int) { IndexIterator old(*this); --*this; return old;}
IndexIterator& operator -=(std::ptrdiff_t offset) { index -= offset; return *this;}
IndexIterator operator -(std::ptrdiff_t offset) const { IndexIterator res (*this); res -= offset; return res;}

std::ptrdiff_t operator -(const IndexIterator& rhs) const { assert(v == rhs.v); return index - rhs.index; }

bool operator == (const IndexIterator& rhs) const { assert(v == rhs.v); return index == rhs.index; }
bool operator != (const IndexIterator& rhs) const { return !(*this == rhs); }

private:
std::vector<T, Ts...>* v;
std::size_t index;
};

template <typename T, typename... Ts>
IndexIterator<T, Ts...> IndexIteratorBegin(std::vector<T, Ts...>& v)
{
return IndexIterator<T, Ts...>(v, 0);
}

template <typename T, typename... Ts>
IndexIterator<T, Ts...> IndexIteratorEnd(std::vector<T, Ts...>& v)
{
return IndexIterator<T, Ts...>(v, v.size());
}

5