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 ...