Каков наилучший способ узнать, переместил ли 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 объектов. У вас будет локализация кеша (потому что кусок не меньше строки кэша) и относительно дешевая динамическая расширяемость. Фактически, если ваш массив становится длинным, он может быстрее выполнять этот вектор, поскольку он никогда не перераспределяет память.

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