Имеет ли std::vector * * для перемещения объектов при увеличении емкости? Или, могут ли распределители "перераспределять"?

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

Нужно ли std::vector<T> перемещать все элементы при увеличении его емкости?

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

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

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

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

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

Возможно, единственным контейнером, который может воспользоваться этим, является 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 */ }

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

Можно было определить, может ли тип memcpy'd использовать библиотеку свойств форматированного типа (не уверен, что они предоставят ее из коробки, или нужно будет создать дискриминатор составного типа на основе boost).

В любом случае, чтобы воспользоваться realloc(), можно было бы создать новый тип контейнера, который может явно использовать эту оптимизацию. С нынешним стандартным интерфейсом распределителя это не представляется возможным.