Имеет ли std :: vector * возможность * перемещать объекты при увеличении емкости?Или, может ли распределители «перераспределить»?

Question

A другой вопрос вдохновил на следующую мысль:

Имеет ли std::vector<T> для перемещения всех элементов, когда он увеличивает свою емкость?

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

Такое поведение представляется единственно возможным правильным решением с учетом стандартного интерфейса распределителя.Но мне было интересно, имеет ли смысл изменить распределитель, чтобы он предлагал функцию reallocate(std::size_t), которая возвращала бы pair<pointer, bool> и могла бы отображаться на базовый realloc()?Преимущество этого состоит в том, что в случае, если операционная система может просто расширить выделенную память, тогда никакого перемещения вообще не должно произойти.Логическое значение будет указывать, была ли перемещена память.

(std::realloc(), возможно, не лучший выбор, потому что нам не нужно копировать данные, если мы не можем расширять. Поэтому на самом деле мы бы предпочли что-токак extend_or_malloc_new(). Редактировать: Возможно, специализация на основе is_pod позволит нам использовать фактический realloc, включая его побитовую копию. Только не в общем.)

Это похоже на упущенную возможность.В худшем случае, вы всегда можете реализовать reallocate(size_t n) как return make_pair(allocate(n), true);, чтобы не было никаких штрафов.

Есть ли проблема, которая делает эту функцию неприемлемой или нежелательной для C ++?

Возможно, единственным контейнером, который может воспользоваться этим, является std::vector, но опять же, это довольно полезный контейнер.

---

Обновление: небольшой пример для пояснения.Текущая resize():

pointer p = alloc.allocate(new_size);

for (size_t i = 0; i != old_size; ++i)
{
  alloc.construct(p + i, T(std::move(buf[i])))
  alloc.destroy(buf[i]);
}
for (size_t i = old_size; i < new_size; ++i)
{
  alloc.construct(p + i, T());
}

alloc.deallocate(buf);
buf = p;

Новая реализация:

pair<pointer, bool> pp = alloc.reallocate(buf, new_size);

if (pp.second) { /* as before */ }
else           { /* only construct new elements */ }

Answer 1

Когда std::vector<T> заканчивается, имеет для выделения нового блока.Вы правильно объяснили причины.

IMO это имеет смысл расширить интерфейс распределителя.Двое из нас пытались для C ++ 11, и мы не смогли получить поддержку для него: [1] [2]

Я убедился, что длядля этого потребуется дополнительный API уровня C.Мне также не удалось получить поддержку: [3]

Answer 2

В большинстве случаев realloc не будет расширять память, а скорее выделять отдельный блок и перемещать содержимое.Это было учтено при определении C ++ в первую очередь, и было решено, что текущий интерфейс проще и не менее эффективен в общем случае.

В реальной жизни на самом деле мало случаев, когда realloc способен расти .В любой реализации, где malloc имеет разные размеры пула, есть вероятность, что новый размер (помните, что размеры vector должны расти геометрически) попадет в другой пул.Даже в случае больших чанков, которые не выделены из какого-либо пула памяти, он сможет расти, только если виртуальные адреса большего размера свободны.

Обратите внимание, что в то время как realloc может иногда Вырастите память без перемещения , но к моменту завершения realloc она может уже переместить (побитовое перемещение) памяти и этот двоичный файл переместить вызовет неопределенное поведение для всех не POD-типов.Я не знаю ни одной реализации распределителя (POSIX, * NIX, Windows), где вы могли бы спросить систему, сможет ли она расти , но это не удастся, если потребуется перемещение .

Answer 3

Да, вы правы, что стандартный интерфейс распределителя не обеспечивает оптимизации для типов memcpy'able.

Можно было определить, может ли тип быть memcpy, используя библиотеку признаков типа boost (не уверен, предоставят ли они его «из коробки», или нужно было бы создать составной дискриминатор типов, основанный на форсированных)которые могут явно воспользоваться этой оптимизацией.С текущим стандартным интерфейсом распределителя это кажется невозможным.