Рассмотрим следующий код:
std::vector vec;
vec.reserve(500);
size_t cap = vec.capacity();
std::vector newVec = std::move(vec);
assert(cap == newVec.capacity());
Практически в любой реализации, с которой вы столкнетесь, это будет работать. Меня не волнует, что делают реализации. Я хочу знать, что стандарт требует. Будет ли перенесенный vector иметь ту же емкость, что и исходный? Или сработает утверждение?
Глядя на стандарт, кажется, что от конструктора перемещения ничего не требуется, однако, как говорит @amaurea, это полностью противоречит цели семантики перемещения, если конструктор перемещения пытается выделить или освободить память, поэтому я ожидаю, что емкость оставаться одинаковым во всех реализациях.
23.2.1 Общие требования к контейнеру
Выражение
X u(a);
X u = a;
Утверждение/примечание до/после условия
Требуется: T должен быть CopyInsertable в X (см. ниже).
сообщение: u == a
Стандарт требует только, чтобы newVec == vec. Поскольку емкость std::vector::operator== не учитывается, newVec не обязательно должна иметь ту же емкость, что и vec.
Стандартные требования C++11 к конструктору перемещения для std::vector (Таблица 99 — Требования к контейнеру с поддержкой распределителя):
X(rv)
X u(rv)
rv до этой конструкции; значение get_allocator() должно быть таким же, как значение rv.get_allocator() до этой конструкции.Здесь нет требований/гарантий по емкости. Но мы можем сделать вывод, что постоянная сложность неявно отрицает любые перераспределения. И я не вижу никакой другой логической причины для изменения емкости, кроме перераспределения. Значит будет так же.
С другой точки зрения, если вектор move-from пуст, вполне законно просто игнорировать его и конструировать по умолчанию. Это по-прежнему будет O (1), так как не требует никаких конструкций для каждого элемента. (Спасибо Николу Боласу за эту проблему).
Также реализация, возможно, может уменьшить емкость до размера, используя параметр hint функции std::allocator::allocate:
pointer allocate(size_type, allocator<void>::const_pointer hint = 0);
Использование hint не указано, но предназначено для помощи в определении местоположения, если этого требует реализация. Таким образом, какое-то сложное решение, возможно, может передавать указатель векторного хранилища как hint и использовать для него realloc для уменьшения емкости.
Вывод: похоже, что стандарт не гарантирует сохранения емкости при перемещении std::vector, объем хранилища потенциально может уменьшиться.
realloc, чтобы уменьшить vector так, чтобы size() == capacity(). Постоянная сложность не исключает этого.
- person Peter Alexander; 30.10.2012
std::allocator<> может использовать realloc с его текущим интерфейсом?
- person ildjarn; 30.10.2012
malloc внутри, может просто вызвать realloc для указателя.
- person aschepler; 30.10.2012
std::allocator<> может использовать realloc под прикрытием?
- person Mooing Duck; 30.10.2012
realloc или чего-то подобного: просто меняла векторную емкость без уважительной причины. Память по-прежнему выделена, но никогда не будет использоваться.
- person aschepler; 30.10.2012
std::string Dinkumware/Microsoft делает это.
- person Mooing Duck; 30.10.2012
std::allocator<T> может это сделать? Стандарт требует, чтобы аллокатор по умолчанию для std::vector<T> был std::allocator<T>, без специализаций, без настройки...
- person ildjarn; 30.10.2012
vec пуст, для newVec совершенно законно просто игнорировать пустой перемещенный объект и саму конструкцию по умолчанию. Это по-прежнему будет O (1), так как не требует никаких конструкций для каждого элемента.
- person Nicol Bolas; 30.10.2012
vector, которые содержат типы, отличные от POD. string делает это, потому что требует, чтобы содержащийся тип был POD.
- person Mooing Duck; 30.10.2012
::operator new(std::size_t) требуется распределитель по умолчанию.
- person Rost; 30.10.2012
std::array? Это не постоянное, а линейное время.
- person Rost; 30.10.2012
N. У кортежей та же проблема.
- person Mooing Duck; 30.10.2012
::operator new(size_t) — это не одно и то же наблюдаемое поведение!
- person Rost; 30.10.2012
new заключается в том, что он создает объект. Что касается стандарта, то здесь нет ни стека, ни кучи, ни malloc.
- person Peter Alexander; 30.10.2012
