Tips, Tricks and Gotchas

Polymorphism and Pointers

std::vector<> stores elements by value. This means that storing polymorphic types by value doesn't work like you might expect.

class Object {
  public:
    virtual void hello(void) { std::cout << "Object::hello()" << std::endl; }
    virtual ~Object() {}
};
 
class Dog : public Object {
  public:
    virtual void hello(void) { std::cout << "Dog::hello(). Woof." << std::endl; }
};
 
Dog fido;
std::vector<Object> object_vector;
object_vector.push_back(fido);
object_vector.front().hello(); // outputs "Object::hello()", not "Dog::hello(). Woof."

This only copies the base part of the object into the vector, which is a problem called object slicing. To avoid this problem you can instead store pointers to polymorphic objects. 7)

Dog * fido = new Dog();
std::vector<Object *> object_vector;
object_vector.push_back(fido);
object_vector.front()->hello(); // outputs "Dog::hello(). Woof."

However, if you do this you need to remember to delete the pointer manually; when the vector is destroyed it doesn't call delete on any pointers it contains. One way to make this easier is to instead store smart pointers, like std::tr1::shared_ptr<> if your compiler's standard library implementation has it 8) or boost::shared_ptr<> if it doesn't. But keep in mind that std::auto_ptr<>, introduced in the last article, cannot be stored in a std::vector<>. I'll cover more details about smart pointers in article eight.

boost::shared_ptr<Dog> fido(new Dog());
std::vector<boost::shared_ptr<Object> > object_vector;
object_vector.push_back(fido);
object_vector.front()->hello(); // outputs "Dog::hello(). Woof."

Even if you aren't storing polymorphic objects in a vector, you may wish to use (smart) pointers instead if the objects you wish to store are very expensive to copy.

Your Friend typedef

When using std::vector<>, or really any template code with any degree of complexity, judicious use of typedefs can make your life much easier.

typedef boost::shared_ptr<Object> ObjectPtr;
typedef std::vector<ObjectPtr> LiveObjects;
LiveObjects live_objects;
LiveObjects::iterator begin = live_objects.begin();

In this example, you could change the allocator for LiveObjects with a minimum of fuss, or even the type of container.

Shrinking vectors

std::vector<>::reserve() will not reduce the capacity of a vector. If you want to reduce the capacity, you can use try the copy and swap trick.

std::vector<int> my_vector;
// fill the vector
std::vector<int>(my_vector).swap(my_vector); // creates a temporary vector copy constructed from
                                             // the vector to be shurnk, then immediately swaps
                                             // contents with the original vector

This generally will remove some, but not necessarily all, excess capacity from the original vector. Similarly, sometimes instead of just calling clear() to remove all elements, you may wish to swap with a temporary vector to minimize the memory held by the vector.

std::vector<int> my_vector;
// fill the vector
std::vector<int>().swap(my_vector); // creates an empty temporary vector, then immediately swaps
                                    // contents with the original vector

Interoperating

Some functions expect pointers to buffers. To use std::vector<> with these functions you can pass the address of elements in the vector. For example, if you have a vector v, &v[0] will return a pointer to the first element. std::vector<>'s elements are guaranteed to be stored in contiguous memory 9) so you can use that pointer in the same cases you could use a pointer to a dynamic array of the same size as the vector. (Provided the function doesn't try to delete, realloc() or similarly mess with the actual memory instead of the contents of the memory.)

Unordered Vectors

Sometimes your vector contains a set of elements where the order is unimportant; one example might be a list of particles. In that case instead of using erase() to remove a single element, it's often more efficient to swap the element to be removed with the last element in the vector and call pop_back().

std::vector<int>::iterator itr = /* determine element to be erased */;
// instead of int_vector.erase(itr);
std::swap(*itr, int_vector.back());
int_vector.pop_back();

Alternately, you can assign the last element on top of the current element and call pop_back().

std::vector<int>::iterator itr = /* determine element to be erased */;
// instead of int_vector.erase(itr);
*itr = int_vector.back();
int_vector.pop_back();

Which one is more efficient depends on the type used to instantiate the vector. For integers and other primitive types assignment will generally perform better. For some classes using std::swap<>() will be more efficient.

Avoid std::vector<bool>

The C++ Standard defines std::vector<bool> to be implemented in quite a different manner than other std::vector<> instantiations. Code that works fine with other vector instantiations may explode mysteriously if used with with std::vector<bool>. If you find you need a container to hold bools, consider instead using std::deque<> (covered in part 4).

Reading Error Messages

Reading error messages from code using std::vector<> (or any template code, including the rest of the standard library) can be something of a chore. Let's start with an easy example:

#include <vector>
 
int main(int, char **) {
  std::vector<int> int_vector;
  int_vector.push_back("string");
 
  return 0;
}

Obviously this won't work, because I'm trying to put a string into a vector, but let's pretend that this wasn't so obvious. One compiler, gcc 3.4.4, produces this error message:

temp.cpp: In function 'int main(int, char**)':
temp.cpp:5: error: invalid conversion from 'const char*' to 'int'
temp.cpp:5: error:   initializing argument 1 of 'void std::vector<_Tp, _Alloc>::push_back(const _Tp&)
         [with _Tp = int, _Alloc = std::allocator<int>]'

The "void std::vector<_Tp, _Alloc>::push_back(const _Tp&) [with _Tp = int, _Alloc = std::allocator<int>]" may look a little intimidating, so let's break it down somewhat. It says that we're dealing with a vector where _Tp is int and _Alloc is std::allocator<int>, so let's substitute those back into the vector bits to get:

temp.cpp:5: error: invalid conversion from 'const char*' to 'int'
temp.cpp:5: error:   initializing argument 1 of 'void std::vector<int, std::allocator<int> >::push_back(const int &)'

We know that the default allocator for std::vector<T> is std::allocator<T> so we can take that part out, and this breaks down to:

temp.cpp:5: error: invalid conversion from 'const char*' to 'int'
temp.cpp:5: error:   initializing argument 1 of 'void std::vector<int>::push_back(const int &)'

Now it looks more managable, so it says on line five I tried to stuff a const char * into a std::vector<int>::push_back(), when it expected an int.

Here's another example:

  std::vector<int> int_vector;
  std::vector<float>::iterator itr = int_vector.begin();

When compiled with MSVC .NET 2003, it produces this error message:

temp.cpp(6) : error C2440: 'initializing' : cannot convert
    from 'std::vector<_Ty>::iterator' to 'std::vector<_Ty>::iterator'
        with
        [
            _Ty=int
        ]
        and
        [
            _Ty=float
        ]
        No constructor could take the source type, or constructor overload resolution was ambiguous

In this case you have two different vector types involved, which shows up as two different _Ty='s lines in the error output. Subbing in the _Ty='s in order you get:

temp.cpp(6) : error C2440: 'initializing' : cannot convert
   from 'std::vector<int>::iterator' to 'std::vector<float>::iterator'

So it says I can't assign an iterator to a int vector to an iterator to a float vector.

Some Performance Considerations

In the introduction I claimed that std::vector<> was largely just as efficient as using standard dynamic arrays. This is quite a large claim, and there are some caveats. There are times where std::vector<> is less efficient than standard dynamic arrays, and there are times when dynamic arrays are less efficient. The primary justifying factor for efficiency claims in the standard library is that the standard library is implemented as templates, and as such benefit from inlining. This means that code like:

for (std::vector<Something>::iterator itr = some_vector.begin();
     itr != some_vector.end();
     ++itr) {
  *itr = Something();
}

compiles to equivalent machine code10) as:

for (int i = 0; i < number_of_somethings; ++i) something_array[i] = Something();

Places where std::vector<> differs from normal dynamic arrays come from the fact that std::vector<> holds both initialized and uninitialized memory, and normal dynamic arrays store just initialized memory. Because std::vector<> manages both initialized and uninitialized memory, it needs to store both size and capacity in addition to the memory address of the memory it holds. When you hold a pointer to a dynamic array all you need to do is hold the pointer and usually the size (if you intend to do anything useful with the dynamic array). This means that std::vector<> generally stores an additional word per instance as compared to a dynamic array.

The lack of uninitialized memory makes adding new elements to a dynamic array costly, as you need to first allocate a new array and then copy over the data from the old array every time new elements are added. On the other hand, std::vector<>() can just use the uninitialized memory to add the new elements up to the capacity of the vector. This generally means that the more dynamic the data set, std::vector<>() is more attractive. However, if your data size never changes, (but is still determined at runtime) then a dynamic array may be more attractive from a memory consumption standpoint.

However, some std::vector<> implementations that uses a class type for std::vector<>::iterator, may exhibit some slower behavior for things like using std::sort<>() due to less than perfect inline code generation. This can be addressed by instead of passing begin() and end() to the algorithm, passing pointers to the raw data as arguments. ex: instead of doing std::sort(my_vector.begin(), my_vector.end()) doing std::sort(&my_vector.front(), &my_vector.front() + my_vector.size()).

Closing and References

This article covered most of the more useful member functions and algorithms used with std::vector<>. However, there are still details that I didn't cover. For a reference about std::vector<> and other algorithms to used with std::vector<> you may wish to read The C++ Standard Library by Nicolai Josuttis. Or if you are interested in the language lawyer details, the actual text of the C++ standard: ISO/IEC 14882:2003, which can be found either in hard cover as The C++ Standard: Incorporating Technical Corrigendum No. 1 from Wiley or in electronic or print form from your national standards body. Another good resource of learning how to use standard library containers effectively is Effective STL by Scott Meyers.

In the next article I'll go into more details about iterators and algorithms.

7) Remember that objects with virtual functions should also have a virtual destructor in the base class.

8) As of this writing hardly any do.

9) at least after the 2003 revision of the C++ Standard

10) There may be symbol name differences, and so on. This is in release mode. In debug builds (where performance usually isn't a factor) std::vector<> usually performs much slower. On the other hand it may do some error checking that raw dynamic arrays with pointers does not, so that performance cost isn't pure overhead.