Previous Table of Contents Next


The first column of the matrix has elements 0, 10, 20, ..., 90; we can refer to that column as v[slice(0, 10, 10)]. More generally, we can use v[slice(n, 10, 1)] to refer to the nth row and v[slice(n, 10, 10)] to refer to the nth column. We can even refer to the two main diagonals as v[slice(0, 10, 11)] and v[slice(9, 10, 9)].

If you are a numerical analyst, this description has probably whetted your appetite; in which case you are invited to refer to a more detailed description of the library.

7.6.4. Containers

There is no single best way to store a collection of related data, so the C++ library offers several choices. All of these choices are made available as templates that define types that hold values. So, for example, we can define an object of type vector<int>. If we do so, that object will contain a vector of integer values. We emphasize the notion of value here because putting something into a container copies it, and taking it out copies it again. In order to put objects into a container while preserving their identities, you should store pointers to the objects instead.

There are two kinds of containers in the standard library: sequential containers and associative containers. Although these containers are not related by inheritance, the containers of each kind have several operations in common with each other. We do not have room to enumerate all the container operations, but we can give an idea of the most important properties of the containers.

7.6.4.1. Sequential Containers

The sequential containers are vector, list, and deque (which stands for double-ended queue). All of them support the ability to append elements at the end of the sequence and remove them again efficiently. However, their capabilities vary beyond that.

For example, as its name suggests, a vector will typically store its elements in contiguous memory. This makes it possible to access the elements in random order, if necessary, but makes it somewhat more difficult to append elements efficiently.

The list class is intended to be an idealization of a doubly linked list. Accordingly, it is possible to insert elements efficiently into a list, not only at the end, but also at the beginning and between any pair of adjacent elements.

The deque class is more like a vector than like a list. The main difference between a vector and a deque is that the deque supports efficient insertion at either end, not just at one end.

As a simple example, we can create a vector that contains the squares of the integers from 0 through 99 as follows:

   vector<int> squares(100);

   for (int i = 0; i < 100; ++i)
       squares[i] = i * i;

This example, however, does not take advantage of the sequential nature of vectors. Instead, it preallocates memory and uses random-access indexing for something that could be done more directly. If we wanted to use vectors sequentially, we might write:

   vector<int> squares;

   for (int i = 0; i < 100; ++i)
       squares.push_back(i * i);

This version has the advantage that we now do not need to precompute how many elements the vector will have. However, it is somewhat slower than the first version because the library will have to reallocate the memory that the vector occupies several times.

We can avoid reallocation by giving the vector a hint about how much memory to occupy:

   vector<int> squares;

   squares.reserve(100);
   for (int i = 0; i < 100; ++i)
       squares.push_back(i * i);

The call to reserve tells the library to allocate at least enough memory for 100 elements.

One advantage of using vectors sequentially is that the same code will work for lists:

   list<int> squares;

   for (int i = 0; i < 100; ++i)
       squares.push_back(i * i);

Now, however, there is no reason to reserve space in advance. Moreover, if we wanted, we could have used push_front to push the squares onto the beginning of the list (which would have reversed their order). We could have used a deque the same way.


Previous Table of Contents Next