Требуется ли сохранить емкость при перемещении std :: vector?

Рассмотрим следующий код:

std::vector vec;
vec.reserve(500);
size_t cap = vec.capacity();

std::vector newVec = std::move(vec);
assert(cap == newVec.capacity());

Практически в любой реализации, с которой вы столкнетесь, это будет работать. Я нене заботиться о том, что делают реализации. Я хочу знать, что стандарттребует, Будет ли переездvector имеют ту же емкость, что и оригинал? Или актив будет срабатывать?

 amaurea29 окт. 2012 г., 21:44
Если бы емкость могла измениться, это полностью сломало бы мотивацию для семантики перемещения, во-первых, чтобы избежать ненужного копирования и перераспределения. Я неу меня нет стандарта, поэтому я могудать вам правильный ответ.

Ответы на вопрос(2)

Решение Вопроса

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

23.2.1 Общие требования к контейнерам

выражение

X u(a);
X u = a;

Утверждение / примечание до / после условия

Требуется:T CopyInsertable в X (см. ниже).

сообщение:u == a

Стандарт требует только, чтобыnewVec == vec, Поскольку мощность не принимается во внимание,std::vector::operator==newVec не обязательно должны иметь такую же емкость, как.vec

 seh11 янв. 2013 г., 21:12
Первый абзац вашего ответа противоречит вашему предупреждению в последнем абзаце, поэтомутрудно сказать, какое утверждение выДелаем сильнее.

Стандартные требования C ++ 11 к конструктору перемещения дляstd::vector есть (Таблица 99 - Требования к контейнерам, учитываемые распределителем):

X(rv)
X u(rv)
Перемещение конструкции распределителя не должно выходить через исключениеpost: у вас должны быть те же элементы, что иrv имел до этой конструкции; значениеget_allocator() должно быть таким же, как значениеrv.get_allocator() до этой конструкции.сложность: постоянная

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

С другой стороны, если вектор с удаленным пустым, совершенно законно просто игнорировать его и конструировать по умолчанию. Это все равно будет O (1), так как это нене требует каких-либо конструкций для каждого элемента. (БлагодаряНиколь Болас для этого вопроса).

Также реализация может уменьшить емкость до размера, используяhint параметрstd::allocator::allocate функция:

pointer allocate(size_type, allocator<void>::const_pointer hint = 0);
</void>

Использованиеhint не определено, но предназначено как помощь населению, если реализация того пожелает. Таким образом, какое-то изощренное решение может передать указатель на векторное хранилище какhint и использоватьrealloc на это уменьшить емкость.

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

 Peter Alexander29 окт. 2012 г., 22:17
@ildjarn: это не такдолжен. Там'Это стандартное правило высокого уровня, которое позволяет реализации выполнять любую оптимизацию, которую сочтет нужной, при условии, что наблюдаемое поведение остается тем же. Кроме того, что сказал Ашеплер :-P
 ildjarn29 окт. 2012 г., 22:28
@PeterAlexander: Выповторяешь чтоstd::allocator может сделать это? Стандарт требует, чтобы распределитель по умолчанию дляstd::vector являетсяstd::allocator, без специализаций, без настройки ...
 ildjarn29 окт. 2012 г., 22:15
@PeterAlexander: Как могstd::allocator использоватьrealloc с его текущим интерфейсом?
 Nicol Bolas29 окт. 2012 г., 22:31
@Rost: проблема здесь в том, что, так какvec пусто, это совершенно законно дляnewVec просто игнорировать пустой перемещенный объект и саму конструкцию по умолчанию. Это все равно будет O (1), так как это нене требует каких-либо конструкций для каждого элемента.
 Rost29 окт. 2012 г., 22:59
@PeterAlexander Stack и другие грязные трюкиЭто применимо, требуется использовать распределитель по умолчанию::operator new(std::size_t)
 Mooing Duck29 окт. 2012 г., 23:07
@Rost: Тыя не правРассмотренные типы, размер стека которых зависит отN, Кортежи имеют ту же проблему.
 Mooing Duck29 окт. 2012 г., 22:27
@PeterAlexander: Этоизвестные как Small Buffer Optimization и Dinkumware / Microsoft'sstd::string Является ли.
 Mooing Duck29 окт. 2012 г., 22:57
@Rost: перемещение автоматического хранилищавсегда постоянное время, поскольку оно имеет небольшой фиксированный верхний предел. Илджарн прав, что это нет относится кvectors, которые содержат не POD типы.string делает это, потому что требует, чтобы содержащийся тип был POD.
 aschepler29 окт. 2012 г., 22:19
Но изначально я думал о странной реализации, которая нет даже делать какие-либоrealloc или аналогичный: просто измените емкость вектора без уважительной причины. Память все еще распределена, но она выиграланикогда не будет использован.
 Peter Alexander29 окт. 2012 г., 23:52
@Rost: наблюдаемое поведениеnew просто он создает объект. Что касается стандарта, то нет ни стека, ни кучи, ни.malloc
 aschepler29 окт. 2012 г., 22:17
@ildjarn: Теоретически, специализация шаблона, которая знает, что использовался его распределитель.malloc внутренне мог просто позвонитьrealloc на указатель.
 ildjarn29 окт. 2012 г., 22:12
Но мы можем сделать вывод, что постоянная сложность неявно отрицает любые перераспределения ". +1
 Rost29 окт. 2012 г., 23:04
@ Действительно, Утка? Как насчет перемещения / обменаstd::array? Это'не постоянное, а линейное время.
 Rost29 окт. 2012 г., 23:21
@ Питер Александр Ооо, наконец-то я это вижу. Но ждать! Распределение по стеку и через::operator new(size_t) не то же самое наблюдаемое поведение!
 Rost29 окт. 2012 г., 22:32
@MooingDuck Don 'Не думаю, что такой прием применим здесь, как вы можете перемещать объект автоматического хранения в постоянное время? Вы должны перемещать его по элементам, которые являются линейными или, по крайней мере, амортизируются по сложности.
 Rost29 окт. 2012 г., 22:36
@ Николас Болас Хороший вопрос, похоже,по стандарту не отрицается.
 Peter Alexander29 окт. 2012 г., 22:34
@ildjarn: яЯ повторяюсь здесь, но реализация может сделатьвсе, что хочет до тех пор, пока наблюдаемое поведение одинаково.
 Peter Alexander29 окт. 2012 г., 22:14
Я мог видеть разумную реализацию, делающуюrealloc чтобы уменьшитьvector вниз, чтобыsize() == capacity(), Постоянная сложность не исключает этого.
 Mooing Duck29 окт. 2012 г., 22:18
@aschepler: Но какая частьstd::allocator интерфейс может использоватьrealloc под одеялом?
 aschepler29 окт. 2012 г., 22:14
Похоже, что реализация могла бы просто уменьшить емкость до размера и при этом удовлетворить все юридические требования, хотя это было бы бессмысленной тратой.
 Peter Alexander29 окт. 2012 г., 23:10
@Rost: яповторю в третий раз: реализацию можно сделатьвсе, что хочет до тех пор, пока наблюдаемое поведение одинаково.
 ildjarn29 окт. 2012 г., 22:42
@PeterAlexander: размещение в стекене имеют такое же наблюдаемое поведение.
 Peter Alexander29 окт. 2012 г., 22:21
Очень умная реализация может даже оптимизировать весь вектор и распределить все в стеке (если позволяет ситуация). Я нене думаю, что тамЧто-нибудь, что запрещает это в определенных ситуациях.

Ваш ответ на вопрос