Делает станд.:: вектор вызывает функцию подкачки при росте? Всегда или только для некоторых типов?

Я не думаю, что в векторе разрешено использовать своп (обнаружено ADL). Я могу найти это явно не запрещено, но требования к типу значения вектора - это CopyConstructible и Assignable. Ни один из них не имеет swap в качестве допустимой операции (даже необязательной) или каких-либо стандартных средств для определения того, перегружен ли swap или нет. Возможно, он мог бы использовать std :: swap (или специализацию, если таковая существует), где это необходимо, потому что у нее такие же требования к своим параметрам: CopyConstructible и Assignable (и специализации для UDT функций в пространстве имен std должны реализовать определенное поведение универсального шаблона). Однако это не помогает с перераспределением, потому что вам нужно будет создать несколько «пустых» объектов для обмена, а вектор не может просто самостоятельно решить, что его тип значения должен быть конструктивным по умолчанию, когда стандарт этого не делает. это не требуется.

Думаю, разумно предположить, что если операция не требуется для вашего типа T, она не будет выполнена, даже если компилятор каким-то образом психически определит, что она существует. В C ++ тот факт, что что-то имеет правильные функции, определенные для реализации интерфейса, не означает, что он утверждает, что реализует семантику этого интерфейса. Только когда вы передадите его в контексте, который требует семантики, вы заявляете, что поведение функций соответствует ожидаемому для интерфейса.Стандарт не требует корректного свопа для типа значения вектора, поэтому реализация вектора не может предполагать, что только потому, что своп определен, он лучше, чем оператор = .

Это всего лишь моя интерпретация цели спецификации, хотя я не могу найти ничего окончательного в любом случае.

23.2.4.3/4 дает подсказку. Когда говорят о erase , он говорит: «оператор присваивания T вызывается количество раз, равное количеству элементов в векторе после стертых элементов». Таким образом, вектору явно запрещается использовать swap для смещения конца вектора вперед после стирания: он должен использовать operator = . Я считаю это сильным намеком на то, что авторы ожидают использовать operator = для всего, иначе они не были бы настолько беспечны, чтобы запретить своп в одном случае, когда на самом деле его можно использовать без конструктора по умолчанию.

Я также понимаю точку зрения Microsoft, описанную вами и jdv, что для контейнеров контейнеров можно получить большую выгоду от подкачки. Пока «магия шаблона» такова, что она не мешает правильно сформированным программам C ++, нет ничего плохого в реализации, предоставляющей средства для типов, сообщающих вектору для замены.

Например, возможно, у них есть шаблон характеристик типа с двойным подчеркиванием в имени. Эффект от использования этого имени определяется реализацией, поэтому все ставки отключены.Стандарт C ++ ничего не говорит о том, как std :: vector ведет себя в программах, специализирующихся на этом шаблоне. После того, как вы использовали зарезервированное имя в своей программе, реализация может определить вектор для использования operator = , swap или aubergine для всех стандартных забот.

std :: vector традиционно копирует элементы в новую память при росте, а затем старые значения уничтожаются. Однако в грядущем C ++ 0x со ссылками на rvalue и семантикой перемещения std :: vector может перемещать-конструировать элементы в новую память. Это намного эффективнее. Если у вас есть вектор строк или некоторые другие дорогостоящие для копирования данные, то их построение с перемещением по существу просто копирует указатели на хранимые данные и отмечает исходный объект как пустой. Это очень дешево по сравнению с копированием и уничтожением и эффективно решает дорогостоящую проблему перераспределения векторов для типов, конструируемых перемещением. Это в значительной степени оптимизация подкачки, которую вы описали, встроенная в язык.

Что говорит стандарт, я точно не знаю. По умолчанию в stl используется копирование, что неинтересно, если вы много редактируете векторы векторов.

Однако желаемое поведение реализовано в Visual C ++ в их реализации TR1, доступной как обновление для VS2008 (TR1 является своего рода прелюдией к стандарту C ++ 0x). Они покупают свою реализацию stl у Dinkumware, как и многие другие поставщики компиляторов, поэтому вы можете ожидать, что она появится в других компиляторах. См. http://msdn.microsoft.com/en-us/library/bb982198.aspx .

Если вы используете GCC, это бесполезно для вас, но, вероятно, здесь есть другие, которые могут вам сказать.

[Edit] Прочитав после редактирования, я обнаружил, что Microsoft утверждает, что оптимизация swap () - это их функция, а не dinkimware. По крайней мере, так я прочитал это сообщение в блоге: http://blogs.msdn.com/vcblog/archive/2008/01/08/qa-on-our-tr1-implementation.aspx

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

По сути, вы спрашиваете, что происходит, когда вы делаете следующее:

vector<int> v;
v.reserve(100);

Мы можем посмотреть, что делает libstdc ++ в этом случае, на примере .

template<typename _Tp, typename _Alloc> void vector<_Tp, _Alloc>::reserve(size_type __n) {
    if (__n > this->max_size())
        __throw_length_error(__N("vector::reserve"));
    if (this->capacity() >= __n)
        return;

    const size_type __old_size = size();
    pointer __tmp = _M_allocate_and_copy(__n,
        _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start),
        _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish));
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
    _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
    this->_M_impl._M_start = __tmp;
    this->_M_impl._M_finish = __tmp + __old_size;
    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
}

Важным вызовом здесь является _M_allocate_and_copy

template<typename _ForwardIterator> pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last) {
    pointer __result = this->_M_allocate(__n);
    std::__uninitialized_copy_a(__first, __last, __result, _M_get_Tp_allocator());
    return __result;
}

Важным вызовом здесь является std :: __ uninitialized_copy_a

template<typename _InputIterator, typename _ForwardIterator, typename _Allocator> _ForwardIterator __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _Allocator& __alloc) {
    _ForwardIterator __cur = __result;
    for (; __first != __last; ++__first, ++__cur)
        __alloc.construct(&*__cur, *__first);
    return __cur;
}

Это вызывает конструкцию . Как видите, он использует конструктор копирования.

void construct ( pointer p, const_reference val ) {
    new ((void*)p) T (val);
}

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

К сожалению, при обсуждении стандарта C ++ 0x не уделялось внимания использованию функции подкачки.

На мой взгляд, своп должен быть базовой функцией, известной на уровне языка. Он решает многие проблемы, связанные с добавлением в язык ссылок rvalue.

Возврат std :: vector из функции или назначение из временного может использовать swap вместо копирования. Контейнеры могут использовать это для оптимизации перераспределения.

Увы. : (