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

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?

Answer 1

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

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

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());
}

Answer 2

Один из самых простых способов получить стабильные итераторы (и ссылки) - это использовать 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

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

В итоге:

1. Узнайте / сообщите нам, если unique_ptr<Entity> на самом деле необходимо, потому что Entity это базовый класс. предпочитать container<Entity> над container<unique_ptr<Entity>>,

2. Вы действительно нуждаетесь в стабильности итератора / указателя / ссылки? Ваш пример кода нет. Если вам это на самом деле не нужно, не платите за это. использование vector<Entity> (или же vector<unique_ptr<Entity>> если вы должны).

3. Если вам действительно нужно container<unique_ptr<Entity>> Можете ли вы избежать стабильности указателя / ссылки, жертвуя стабильностью итератора? Если да, vector<unique_ptr<Entity>> это путь

4. Если вам действительно нужна стабильность итератора, настоятельно рекомендуем использовать std::list,

5. Если вы используете std::list и обнаружив при тестировании проблемы с производительностью, оптимизируйте его с помощью распределителя, настроенного на ваши потребности.

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

Answer 3

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

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

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

Answer 4

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