C++ Cookbook

6.2. Using vectors Efficiently

Problem

You are using vectors and you have tight space or time requirements and need to reduce or eliminate overhead.

Solution

Understand how a vector is implemented, know the complexity of insertion and deletion member functions, and minimize unnecessary memory churn with the reserve member function. Example 6-2 shows a few of these techniques in action.

Example 6-2. Using a vector efficiently

#include <iostream>
#include <vector>
#include <string>

using std::vector;
using std::string;

void f(vector<string>& vec) { // Pass vec by reference (or
                              // pointer, if you have to)
   // ...
}

int main() {

   vector<string> vec(500); // Tell the vector that you plan on
                            // putting a certain number of objects
                            // in it at construction
   vector<string> vec2;

   // Fill up vec...
   f(vec);

   vec2.reserve(500);       // Or, after the fact, tell the vector
                            // that you want the buffer to be big
                            // enough to hold this many objects

   // Fill up vec2...
}

Discussion

The key to using vectors efficiently lies in knowing how they work. Once you have a good idea of how a vector is usually implemented, the performance hot spots become obvious.

How vectors work

A vector is, essentially, a managed array. More specifically, a vector<T> is a chunk of contiguous memory (i.e., an array) that is large enough to hold n objects of type T, where n is greater than or equal to zero and is less or equal to an implementation-defined maximum size. n usually increases during the lifetime of the container as you add or ...