Всегда ли перемещаемый вектор всегда пуст?

Я знаю, что в целом стандарт устанавливает несколько требований к значениям, которые были перенесены из:

N3485 17.6.5.15 [lib.types.movedfrom] / 1:

Объекты типов, определенные в стандартной библиотеке C ++, могут быть перемещены из (12.8). Операции перемещения могут быть явно указаны или неявно сгенерированы. Если не указано иное, такие перемещенные объекты помещаются в действительное, но неуказанное состояние.

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

Есть ли какой-то стандарт, который влечет за собой это, что мне не хватает или это похоже на обработку basic_string как непрерывного буфера в C ++ 03 ?

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

Вопрос:

Всегда ли перемещаемый вектор всегда пуст?

Ответ:

Обычно, но нет, не всегда.

Детали gory:

vector не имеет стандартного перемещенного состояния, как некоторые типы (например, unique_ptr указано равным nullptr после перемещения из). Однако требования к vector таковы, что вариантов не так много.

Ответ зависит от того, говорим ли мы о конструкторе перемещения vector или о переходе оператора присваивания. В последнем случае ответ также зависит от распределителя vector .


 vector::vector(vector&& v) 

Эта операция должна иметь постоянную сложность. Это означает, что нет никаких опций, кроме как украсть ресурсы из v чтобы построить *this , оставляя v в пустом состоянии. Это верно независимо от того, что такое распределитель A , и что такое тип T

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


 vector& vector::operator=(vector&& v) 

Это значительно сложнее. Существует 3 основных случая:

Один:

 allocator_traits::propagate_on_container_move_assignment::value == true 

( propagate_on_container_move_assignment оценивается как true_type )

В этом случае оператор присваивания перемещения уничтожит все элементы в *this , освободит емкость с помощью распределителя от *this , переместит назначение распределителей, а затем передаст владение буфером памяти от v до *this . За исключением уничтожения элементов в *this , это операция сложности O (1). И обычно (например, в большинстве, но не во всех алгоритмах std ::), при назначении перемещения в Lhs назначения переноса есть empty() == true .

Примечание. В C ++ 11 параметр propagate_on_container_move_assignment для std::allocatorfalse_type , но это было изменено на true_type для C ++ 1y (y == 4, мы надеемся).

В случае One, перемещенный vector всегда будет пустым.

Два:

 allocator_traits::propagate_on_container_move_assignment::value == false && get_allocator() == v.get_allocator() 

( propagate_on_container_move_assignment оценивает значение false_type , а два распределителя сравниваются одинаково)

В этом случае оператор присваивания перемещений ведет себя точно так же, как и случай 1, со следующими исключениями:

  1. Распределители не перемещаются.
  2. Решение между этим случаем и случаем Три происходит во время выполнения, а в случае Три требует больше T , и, следовательно, так же, как и случай Два, хотя случай 2 фактически не выполняет эти дополнительные требования к T

В случае Two перемещенный vector всегда будет пустым.

Три:

 allocator_traits::propagate_on_container_move_assignment::value == false && get_allocator() != v.get_allocator() 

( propagate_on_container_move_assignment оценивает значение false_type , а два распределителя не сравниваются)

В этом случае реализация не может перемещать назначение распределителей, а также не может передавать любые ресурсы из v в *this (ресурсы являются буфером памяти). В этом случае единственным способом реализации оператора присваивания переходов является эффективное:

 typedef move_iterator Ip; assign(Ip(v.begin()), Ip(v.end())); 

То есть, переместите каждый отдельный T из v в *this . Назначение может повторно использовать как capacity и size в *this если доступно. Например, если *this имеет тот же size что и v реализация может перемещать назначение каждого T из v в *this . Для этого требуется, чтобы T был MoveAssignable . Обратите внимание, что MoveAssignable не требует, чтобы T имел оператор присваивания перемещения. Оператору присваивания копии также будет достаточно. MoveAssignable просто означает, что T должен быть назначен из r значения T

Если size *this недостаточно, то новый T должен быть построен в *this . Для этого требуется, чтобы T был MoveInsertable . Для любого разумного распределителя, о котором я могу думать, MoveInsertable сводится к тому же, что и MoveConstructible , что означает конструктивное из rvalue T (не подразумевает существования конструктора перемещения для T ).

В случае Три, перемещенный vector будет вообще не пустым. Он может быть переполнен элементами. Если элементы не имеют конструктора перемещения, это может быть эквивалентно присваиванию копии. Тем не менее, ничего не предусмотрено. Разработчик может выполнить некоторую дополнительную работу и выполнить v.clear() если он этого v.clear() , оставив v пустым. Мне не известно о какой-либо реализации, и я не знаю о какой-либо мотивации для реализации. Но я не вижу ничего, что бы запрещало это.

Дэвид Родригес сообщает, что GCC 4.8.1 называет v.clear() в этом случае, оставляя v пустым. libc ++ не делает, оставляя v непустым. Обе реализации соответствуют.

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

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

Во многих ситуациях перемещение-построение и назначение переноса могут быть реализованы путем делегирования swap особенно если не задействованы распределители. Для этого есть несколько причин:

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

Ниже приведен пример переноса. В этом случае вектор перемещения не будет пустым, если перемещенный вектор не был пустым.

 auto operator=(vector&& rhs) -> vector& { if (/* allocator is neither move- nor swap-aware */) { swap(rhs); } else { ... } return *this; } 

Я оставил комментарии по этому поводу на других ответах, но перед тем, как полностью объяснить, пришлось сбежать. Результат перемещенного вектора всегда должен быть пустым или в случае назначения перемещения должен быть либо пустым, либо состоянием предыдущего объекта (т. Е. Свопом), поскольку в противном случае правила аннулирования iteratorа не могут быть выполнены, а именно, что перемещение не делает их недействительными. Рассматривать:

 std::vector move; std::vector::iterator it; { std::vector x(some_size); it = x.begin(); move = std::move(x); } std::cout << *it; 

Здесь вы можете увидеть, что недействительность iteratorа действительно раскрывает реализацию перемещения. Требование о том, чтобы этот код был законным, в частности, что iterator остается в силе, предотвращает выполнение от выполнения копии или хранения небольших объектов или любой другой подобной вещи. Если копия была сделана, тогда it будет признана недействительной, когда опционально будет опустошена, и то же самое верно, если vector использует какое-то хранилище на основе SSO. По сути, единственно разумная возможная реализация заключается в том, чтобы поменять указатели или просто переместить их.

Просьба ознакомиться со стандартными котировками по требованиям ко всем контейнерам:

 X u(rv) X u = rv 

post: u будет равна значению, которое было у rv до этой конструкции

 a = rv 

a должно быть равно значению, которое было у rv до этого присвоения

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

begin () возвращает iterator, ссылаясь на первый элемент в контейнере. end () возвращает iterator, который является последним значением для контейнера. Если контейнер пуст, тогда begin () == end ();

Любая реализация, которая действительно перемещалась из элементов источника вместо замены памяти, была бы дефектной, поэтому я предлагаю, чтобы любые стандартные формулировки, говорящие иначе, были дефектом, не в последнюю очередь из-за того, что стандарт на самом деле не очень ясен по этому вопросу , Эти цитаты из N3691.

Interesting Posts
Давайте будем гением компьютера.