Ответ 1
std::vector<T,A>( std::vector<T,A>&& )
это гарантировано как постоянное время (N3797 Таблица 99 X u(rv)).
Мне неизвестно, как переносить вектор произвольного размера в постоянное время, просто не перемещая указатели в буфер. Если это (нет способа) истинно, то построенный вектор должен иметь буфер, по меньшей мере, такой же, как исходный буфер. В стандарте нет формулировки, согласно которой vector должно быть эффективным: правая сторона vector может иметь свою емкость, уменьшенную до любого значения, большего или равного его size: постусловие состоит только в том, что элементы одинаковы. Теоретически это может быть даже большая емкость, если правая сторона vector имела "скрытую емкость", которую компилятор выбрал по какой-либо причине (например, фаза луны).
Ни в какой точке в стандарте N3797 нет верхней границы на capacity, размещенной на любом контейнере. Соответствующая реализация может иметь все std::vector с минимальной емкостью в 2 миллиона элементов (запрет allocator), который может быть использован для принудительной емкости 0), без операции, способной уменьшить это значение ниже 2 миллионов. (shrink_to_fit - всего лишь предложение, а std::vector<T,A>().swap(x) может создать vector из 2 миллионов возможностей и поменять его.
Так как большая часть из приведенного выше относится к отрицательной форме, все, что я могу сказать, это поиск стандарта для каждого упоминания vector, allocator, allocate и capacity. capacity никогда не описывается верхней границей в любой точке. Никаких ограничений (кроме исключения-безопасности) не производится против дополнительных вызовов allocator в пустом конструкторе std::vector (если allocator не удалось, вам может потребоваться размер 0 и емкость 0, но извлечение этого состояния в все, что не использует то же самое allocator, является сложным).
Что касается назначения копий и назначения переноса, то в присваивании копий не устанавливаются гарантии на пропускную способность, превышающую основные (это capacity() >= size()).
Для перемещения-назначения это зависит от того, как это применимо:
23.2.1 [container.requirements.general]/10
Если не указано иное (явно или путем определения функции в терминах других функций), ссылаясь на функция-член контейнера или передача контейнера в качестве аргумента функции библиотеки не должны аннулировать итераторам или изменению значений объектов в этом контейнере.
a = rv (aka std::vector<T,A>& operator=(std::vector<T,A>&&)) случай из таблицы 96 и таблицы 99 относятся к нам. Также не упоминается, что значения, содержащиеся в rv, уничтожаются, и что итераторы к ним недействительны. Таким образом, в соответствии с 23.2.1/10 итераторы не являются недействительными.
Это, однако, не требует перемещения буфера. Либо буфер перемещается из rhs в lhs, либо он остается неповрежденным в rhs vector. В таблице 99 упоминается этот случай неявно, когда он говорит, что элементы lhs могут быть привязаны к переходу (что является единственным способом работы std::array).
Поскольку std::array не имеет выбора, кроме как перемещать элементы, а std::vector не дает никаких дополнительных гарантий относительно перемещения буфера, буфер не нужно перемещать. Похоже, что перемещение буфера является юридической реализацией.
На практике std::vector<T,A>( std::vector<T,A> const& ) выполнит копию содержимого правой стороны в левую сторону, и в каждой проверке, которую я проверил, левая сторона capacity равна значению size в результате vector. Аналогично, std::vector<T,A>( ForwardIterator, ForwardIterator ) создаст vector, который просто подходит для ввода.
Обратите внимание, что std::vector<T,A>::operator=(std::vector<T,A>&&) остается линейным по сложности.