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

Ответ 1

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

Вопрос:

Является ли переносимый вектор всегда пустым?

Ответ:

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

Детали gory:

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

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

vector<T, A>::vector(vector&& v)

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

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

vector<T, A>&
vector<T, A>::operator=(vector&& v)

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

Один:

allocator_traits<A>::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 до назначения перемещения.

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

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

Два:

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

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

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

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

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

Три

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

Просматривайте стандартные кавычки по требованиям для всех контейнеров:

X u(rv)    
X u = rv    

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

a = rv

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

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

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

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