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

Question

Насколько я знаю, я могу использовать вектор векторов (std::vector< std::vector<int> >), и это будет довольно эффективно, потому что внутренне элементы будут не копироваться, а заменяться, что намного быстрее, поскольку не включает копирование буферы памяти. Я прав?

Когда std::vector точно использует функцию подкачки? Я ничего не могу найти в стандарте C ++ . Это происходит во время перераспределения буфера?

Я провел несколько тестов, чтобы выяснить это, но потерпел неудачу. Функция подкачки для моего пользовательского типа данных вообще не вызывается.

РЕДАКТИРОВАТЬ : Вот моя программа испытаний .

Answer 1

У меня нет ссылок для поддержки этих утверждений, но, насколько мне известно, реализация STL, распространяемая с помощью Microsoft C ++, использует некоторые внутренние нестандартные магические аннотации, чтобы пометить vector (и другие коллекции STL) как имеющие производительность -swap, чтобы vector<vector<>> не копировал внутренние векторы, а менял их местами. До VC9, то есть, в VC10 они переключаются на rvalue-ссылки. Я думаю, что вы не должны иметь возможность отмечать свои собственные классы так же, как не существует кросс-компиляторного способа сделать это, и ваш код будет работать только на конкретной версии компилятора.

Редактировать: я быстро взглянул на заголовок <vector> в VC9 и нашел:

    // vector implements a performant swap
template <class _Ty, class _Ax>
    class _Move_operation_category<vector<_Ty, _Ax> >
    {
    public:
        typedef _Swap_move_tag _Move_cat;
    };

Просто для эксперимента, вы можете попытаться специализировать этот класс для вашего собственного типа, но, как я уже сказал, это зависит от версии STL и исчезнет в VC10

Answer 2

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

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

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

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

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

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

Answer 3

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

Answer 4

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

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);
}

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Увы. (

Answer 7

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