Как лучше всего определить, перезаписал ли std :: vector свой массив?

Question

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

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

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

size_t old_capacity = v.capacity();

// Do stuff that could change the vector's size
v.push_back(a);
v.push_back(b);
v.push_back(c);

if (old_capacity != v.capacity()) {
    update_references();
}

Мои вопросы:

• Это лучший способ определить, что вектор перераспределил свой массив?
• Нужно ли проверять повторную посадку после выполнения pop_back?

Answer 1

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

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

std::vector<int> v;

void *old_location = (void *) &(v.front());

v.push_back(3);
v.push_back(3);
v.push_back(3);

if (old_location != &(v.front()))
    update_references();

Answer 2

Как вы правильно заметили, каждый раз, когда вы добавляете что-то в вектор, все существующие итераторы (и указатели на элементы) могут стать недействительными.Хотя вы можете попытаться «обнаружить» это, я настоятельно рекомендую устранить проблему другим способом.В зависимости от ваших требований вы можете:

• Использовать индексы вместо прямых указателей.Вместо Obj* ptr, который вы бы разыменовали на *ptr, у вас будет size_t idx, который будет разыменован на vector[idx].Если у вас уже есть много существующего кода с использованием указателей, вы можете попробовать создать умный указатель, который сделает это под капотом.

• Если вы добавляете, но никогда не удаляете элементы из своего вектораи если вас не волнует непрерывность данных, вы можете вообще не использовать std::vector!Я думаю, что-то вроде списка кусков, каждый из которых - например - фиксированный массив из 256 объектов может быть достаточно.У вас будет локальность кэша (потому что порция не меньше строки кэша) и относительно дешевая динамическая расширяемость.Фактически, если ваш массив становится длиннее, он может работать быстрее этого вектора, потому что он никогда не перераспределяет память.

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