Does std::vector call the swap function when growing? Always or only for some types?

Question

As far as I know I can use a vector of vectors (std::vector< std::vector >) and this will be quite efficient, because internally the elements will not be copied, but swapped, which is much faster, because does not include coping of the memory buffers. Am I right?

When does std::vector exactly make use of the swap function? I can't find anything about it in the C++ standard (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf). Does it happen during buffer reallocation?

I did some tests to find it out, but I failed. The swap function for my custom data type isn't called at all.

EDIT: Here is my test program: http://www.future-processing.com/~mczardybon/swaptest.cpp

Answer 1

What the standard says, I don't know exactly. The default in stl is copying, which is no fun if you edit vectors of vectors a lot.

However, the behavior you want is implemented in Visual C++ in their TR1 implementation, available as an update for VS2008 (TR1 is kind of a prelude to the C++ 0x standard). They buy their stl implementation from Dinkumware, like many other compiler vendors, so you can expect to see this appear on other compilers. See http://msdn.microsoft.com/en-us/library/bb982198.aspx.

If you use GCC this is of no use to you, but there's probably others around here that can tell you.

[Edit] Reading on after editing, I found out that microsoft claims that the swap() optimization is their feature, not dinkimware's. At least that's how I read this blog post: http://blogs.msdn.com/vcblog/archive/2008/01/08/q-a-on-our-tr1-implementation.aspx

Answer 2

std::vector traditionally copy-constructs elements in to the new memory when growing, then the old values are destroyed. However, in the upcoming C++0x with rvalue references and move semantics, std::vector can move-construct elements in to the new memory. This is far more efficient. If you have a vector of strings or some other expensive-to-copy data, then move-constructing them essentially just copies the pointers to the held data and marks the source object as empty. This is very cheap compared to copying and destroying, and effectively solves the costly vector reallocation problem for move-constructable types. It's pretty much the swap optimisation you described, built in to the language.

Answer 3

I don't think vector is permitted to use swap (found by ADL). It's not explicitly forbidden that I can find, but the requirements on the value type of vector are CopyConstructible and Assignable. Neither of those has swap as a valid operation (even an optional one), or any standard means to determine whether swap is overloaded or not. Possibly it could use std::swap (or a specialization, if one exists) where appropriate, because that has the same requirements on its parameters: CopyConstructible and Assignable (and specializations for UDTs of functions in namespace std must implement the defined behaviour of the generic template). That doesn't help with reallocation, though, because you'd have to construct some "empty" objects to swap with, and vector can't just decide of its own authority that its value type should be default constructible, when the standard doesn't require that.

I think it's reasonable to assume that if an operation isn't required for your type T, then it won't be performed, even if the compiler somehow psychically determines that it exists. In C++, just because something has the right functions defined to implement an interface doesn't mean it claims to implement the semantics of that interface. It's not until you pass it in a context which demands the semantics that you're claiming the behaviour of the functions is as expected for the interface. The standard doesn't demand a well-behaved swap for the value type of vector, so the implementation of vector can't assume that just because swap is defined, it's better than operator=.

That's just my interpretation of the intention of the spec, though, I can't find anything definitive either way.

23.2.4.3/4 gives a clue. When talking about erase, it says: "the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements". So vector is explicitly forbidden from using swap to shift forward the end of the vector after an erase: it must use operator=. I take that as a strong hint that the expectation of the authors is to use operator= for everything, otherwise they would not have been so careless as to forbid swap in the one case where it actually can be used without any need for a default constructor.

I also see Microsoft's point, described by you and jdv, that for containers of containers, there's a big gain to be had from swapping. As long as the "template magic" is such that it doesn't interfere with well-formed C++ programs, there's nothing wrong with an implementation providing a means for types to tell vector to swap.

For instance, possibly they have a type traits template with a double-underscore in the name. The effects of using that name are implementation-defined, so all bets are off. The C++ standard says nothing about how std::vector behaves in programs which specialise that template. Once you've used a reserved name in your program, the implementation can define vector to use operator=, swap, or aubergine for all the standard cares.

Answer 4

I have no links to back up this claims, but as far as I know, the STL implementation distributed with Microsoft C++ uses some internal non-standard magic annotations to mark vector (and other STL collections) as having-performant-swap so vector<vector<>> won't copy the inner vectors but swap them. Up to VC9 that is, in VC10 they'll switch to rvalue-references. I think you are not supposed to be able to mark your own classes the same way as there's no cross-compiler way to do it and your code will work only on the specific compiler version.

Edit: I had a quick look at the <vector> header in VC9 and found this:

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

Just for experiment, you could try to specialize this class for you own type, but as I said, this is STL version specific and it's going away in VC10

Answer 5

when you have a quite large vector and you want to release it, you can use swap function to swap it with an empty vector. This is a very efficient way to free memory space when using STL container.

Answer 6

Basically, you are asking what happens when you do the following:

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

We can look at what libstdc++ does in this case as an example.

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

The important call here is _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;
}

The important call here is 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;
}

This is calling construct. As you can see, it is using the copy constructor.

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

Therefore, when a reallocate happens, every element in the vector has the copy constructor called on it.

Answer 7

Unfortunately, using swap function was overlooked when discussing C++ 0x standard.

In my opinion swap should be basic function known to the language level. It solves many rationals for adding rvalue references to the language.

Returning std::vector from function or assigning from temporary could use swap instead of copy. Containers could use it to optimize reallocation.

Alas. :(