This chapter discusses STL containers in detail. It continues the discussion that was begun in Chapter 5. The chapter starts with a general overview of the general abilities and operations of all container classes, with each container class explained in detail. The explanation includes a description of their internal data structures, their operations, and their performance. It also shows how to use the different operations and gives examples if the usage is not trivial. Each section about the containers ends with examples of the typical use of the container. The chapter then discusses the interesting question of when to use which container. By comparing the general abilities, advantages, and disadvantages of all container types, it shows you how to find the best container to meet your needs. Lastly, the chapter covers all members of all container classes in detail. This part is intended as a kind of a reference manual. You can find the minor details of the container interface and the exact signature of the container operations. When useful, cross-references to similar or supplementary algorithms are included.
The C++ standard library provides some special container classes, the so-called container adapters (stack, queue, priority queue), bitsets, and valarrays. All of these have special interfaces that don't meet the general requirements of STL containers, so they are covered in separate sections.[1]Container adapters and bitsets are covered in Chapter 10. Valarrays are described in Section 12.2
This section covers the common abilities of STL container classes. Most of them are requirements that, in general, every STL container should meet. The three core abilities are as follows:
All containers provide value rather than reference semantics. Containers copy elements internally when they are inserted rather than managing references to them. Thus, each element of an STL container must be able to be copied. If objects you want to store don't have a public copy constructor, or copying is not useful (for example, because it takes time or elements must be part of multiple containers), the container elements must be pointers or pointer objects that refer to these objects. Section 5.10.2, covers this problem in detail.
In general, all elements have an order. Thus, you can iterate one or many times over all elements in the same order. Each container type provides operations that return iterators to iterate over the elements. This is the key interface of the STL algorithms.
In general, operations are not safe. The caller must ensure that the parameters of the operations meet the requirements. Violating these requirements (such as using an invalid index) results in undefined behavior. Usually the STL does not throw exceptions by itself. If user-defined operations called by the STL containers do throw, the behavior is different. See Section 5.11.2, for details.
The operations common to all containers meet the core abilities that were mentioned in the previous subsection. Table 6.1 lists these operations. The following subsections explore some of these common operations.
Every container class provides a default constructor, a copy constructor, and a destructor. You can also initialize a container with elements of a given range. This constructor is provided to initialize the container with elements of another container, with an array, or from standard input. These constructors are member templates (see page 11), so not only the container but also the type of the elements may differ, provided there is an automatic conversion from the source element type to the destination element type.[2] The following examples expand on this:
Table 6.1. Common Operations of Container Classes
Operation | Effect |
---|---|
ContType
c
| Creates an empty container without any element |
ContType
c1(c2)
| Copies a container of the same type |
ContType
c(beg,end)
| Creates a container and initializes it with copies of all elements of [beg,end)
|
c. ~ContType()
| Deletes all elements and frees the memory |
c.size()
| Returns the current number of elements |
c.empty()
| Returns whether the container is empty (equivalent to size() ==0, but might be faster)
|
c.max_size()
| Returns the maximum number of elements possible |
c1 == 2
| Returns whether c1 is equal to c2
|
c1 != c2
| Returns whether c1 is not equal to c2 (equivalent to !(c1==c2) )
|
c1 < c2
| Returns whether c1 is less than c2
|
c1 > c2
| Returns whether c1 is greater than c2 (equivalent to c2<c1 )
|
c1 <= c2
| Returns whether c1 is less than or equal to c2 (equivalent to ! (c2<c1) )
|
c1 >= c2
| Returns whether c1 is greater than or equal to c2 (equivalent to ! (c1<c2) )
|
c1 = c2
| Assigns all elements of c1 to c2
|
c1.swap(c2)
| Swaps the data of c1 and c2
|
swap(c1,c2)
| Same (as global function) |
c.begin()
| Returns an iterator for the first element |
c.end()
| Returns an iterator for the position after the last element |
c.rbegin()
| Returns a reverse iterator for the first element of a reverse iteration |
c.rend()
| Returns a reverse iterator for the position after the last element of a reverse iteration |
c.insert(pos,elem)
| Inserts a copy of elem (return value and the meaning of pos differ)
|
c.erase(beg,end)
| Removes all elements of the range [beg,end) (some containers return next element not removed)
|
c.clear()
| Removes all elements (makes the container empty) |
c.get_allocator()
| Returns the memory model of the container |
Initialize with the elements of another container:
std::list<int> l; //l is a linked list of ints ... //copy all elements of the list as floats into a vector std::vector<float> c(l.begin(),l.end());
Initialize with the elements of an array:
int array[] = { 2, 3, 17, 33, 45, 77 };
...
//copy all elements of the array into a set
std::set<int> c(array,array+sizeof(array)/sizeof(array[0]));
Initialize by using standard input:
//read all integer elements of the deque from standard input
std::deque<int> c((std::istream_iterator<int>(std::cin)),
(std::istream_iterator<int>()));
Don't forget the extra parentheses around the initializer arguments here. Otherwise, this expression does something very different and you probably will get some strange warnings or errors in following statements. Consider writing the statement without extra parentheses:
std::deque<int> c(std::istream_iterator<int>(std::cin), std::istream_iterator<int>());
In this case, c
declares a function with a return type that is deque<int>.
Its first parameter is of type istream_iterator<int>
with the name cin,
and its second unnamed parameter is of type "function taking no arguments returning istream_iterator<int>.
" This construct is valid syntactically as either a declaration or an expression. So, according to language rules, it is treated as a declaration. The extra parentheses force the initializer not to match the syntax of a declaration.[3]
In principle, these techniques are also provided to assign or to insert elements from another range. However, for those operations the exact interfaces either differ due to additional arguments or are not provided for all container classes.
For all container classes, three size operations are provided:
size()
Returns the current number of elements of the container.
empty()
Is a shortcut for checking whether the number of elements is zero (size()==0
). However, empty()
might be implemented more efficiently, so you should use it if possible.
max_size()
Returns the maximum number of elements a container might contain. This value is implementation defined. For example, a vector typically contains all elements in a single block of memory, so there might be relevant restrictions on PCs. Otherwise, max_size()
is usually the maximum value of the type of the index.
The usual comparison operators ==, ! =, <, <=, >,
and >=
are defined according to the following three rules:
Both containers must have the same type.
Two containers are equal if their elements are equal and have the same order. To check equality of elements, use operator ==.
To check whether a container is less than another container, a lexicographical comparison is done (see page 360).
To compare containers with different types, you must use the comparing algorithms of Section 9.5.4.
If you assign containers, you copy all elements of the source container and remove all old elements in the destination container. Thus, assignment of containers is relatively expensive.
If the containers have the same type and the source is no longer used, there is an easy optimization: Use swap(). swap()
offers much better efficiency because it swaps only the internal data of the containers. In fact, it swaps only some internal pointers that refer to the data (elements, allocator, sorting criterion, if any). So, swap()
is guaranteed to have only constant complexity, instead of the linear complexity of an assignment.
A vector models a dynamic array. Thus, it is an abstraction that manages its elements with a dynamic array (Figure 6.1). However, note that the standard does not specify that the implementation uses a dynamic array. Rather, it follows from the constraints and specification of the complexity of its operation.
To use a vector, you must include the header file <vector>
[4]:
#include <vector>
There, the types are defined as class template inside namespace std:
namespace std { template <class T, class Allocator = allocator<T> > class vector; }
The elements of a vector may have any type T
that is assignable and copyable. The optional second template parameter defines the memory model (see Chapter 15). The default memory model is the model allocator,
which is provided by the C++ standard library.[5]
Vectors copy their elements into their internal dynamic array. The elements always have a certain order. Thus, vectors are a kind of ordered collection. Vectors provide random access. Thus, you can access every element directly in constant time, provided you know its position. The iterators are random access iterators, so you can use any algorithm of the STL.
Vectors provide good performance if you append or delete elements at the end. If you insert or delete in the middle or at the beginning, performance gets worse. This is because every element behind has to be moved to another position. In fact, the assignment operator would be called for every following element.
Part of the way in which vectors give good performance is by allocating more memory than they need to contain all their elements. To use vectors effectively and correctly you should understand how size and capacity cooperate in a vector.
Vectors provide the usual size operations size(), empty(),
and max_size()
(see Section 6.1.2). An additional "size" operation is the capacity()
function. capacity()
returns the number of characters a vector could contain in its actual memory. If you exceed the capacity(),
the vector has to reallocate its internal memory.
The capacity of a vector is important for two reasons:
Reallocation invalidates all references, pointers, and iterators for elements of the vector.
Reallocation takes time.
Thus, if a program manages pointers, references, or iterators into a vector, or if speed is a goal, it is important to take the capacity into account.
To avoid reallocation, you can use reserve()
to ensure a certain capacity before you really need it. In this way, you can ensure that references remain valid as long as the capacity is not exceeded:
std::vector<int> v; // create an empty vector v.reserve (80); // reserve memory for 80 elements
Another way to avoid reallocation is to initialize a vector with enough elements by passing additional arguments to the constructor. For example, if you pass a numeric value as parameter, it is taken as the starting size of the vector:
std::vector<T> v(5); // creates a vector and initializes it with five values // (calls five times the default constructor of type T)
Of course, the type of the elements must provide a default constructor for this ability. But note that for complex types, even if a default constructor is provided, the initialization takes time. If the only reason for initialization is to reserve memory, you should use reserve().
The concept of capacity for vectors is similar to that for strings (see Section 11.2.5), with one big difference: Unlike strings, it is not possible to call reserve()
for vectors to shrink the capacity. Calling reserve()
with an argument that is less than the current capacity is a no-op. Furthermore, how to reach an optimal performance regarding speed and memory usage is implementation defined. Thus, implementations might increase capacity in larger steps. In fact, to avoid internal fragmentation, many implementations allocate a whole block of memory (such as 2K) the first time you insert anything if you don't call reserve()
first yourself. This can waste lots of memory if you have many vectors with only a few small elements.
Because the capacity of vectors never shrinks, it is guaranteed that references, pointers, and iterators remain valid even when elements are deleted, provided they refer to a position before the manipulated elements. However, insertions may invalidate references, pointers, and iterators.
There is a way to shrink the capacity indirectly: Swapping the contents with another vector swaps the capacity. The following function shrinks the capacity while preserving the elements:
template <class T> void shrinkCapacity(std::vector<T>& v) { std::vector<T> tmp(v); // copy elements into a new vector v.swap(tmp); // swap internal vector data }
You can even shrink the capacity without calling this function by calling the following statement[6]:
//shrink capacity of vector v for type T std::vector<T>(v).swap(v);
However, note that after swap(),
all references, pointers, and iterators swap their containers. They still refer to the elements to which they referred on entry. Thus, shrinkCapacity()
invalidates all references, pointers, and iterators.
Table 6.2 lists the constructors and destructors for vectors. You can create vectors with and without elements for initialization. If you pass only the size, the elements are created with their default constructor. Note that an explicit call of the default constructor also initializes fundamental types such as int
with zero (this language feature is covered on page 14). See Section 6.1.2, for some remarks about possible initialization sources.
Table 6.2. Constructors and Destructors of Vectors
Operation | Effect |
---|---|
vector<Elem> c
| Creates an empty vector without any elements |
vector<Elem> c1(c2)
| Creates a copy of another vector of the same type (all elements are copied) |
vector<Elem> c(n)
| Creates a vector with n elements that are created by the default constructor
|
vector<Elem> c(n,elem)
| Creates a vector initialized with n copies of element elem
|
vector<Elem> c(beg,end)
| Creates a vector initialized with the elements of the range [beg,end )
|
c.~vector<Elem>()
| Destroys all elements and frees the memory |
Table 6.3 lists all nonmodifying operations of vectors.[7] See additional remarks in Section 6.1.2, and Section 6.2.1.
Table 6.3. Nonmodifying Operations of Vectors
Operation | Effect |
---|---|
c.size()
| Returns the current number of elements |
c.empty()
| Returns whether the container is empty (equivalent to size()==0, but might be faster)
|
c.max_size()
| Returns the maximum number of elements possible |
capacity()
| Returns the maximum possible number of elements without reallocation |
reserve()
| Enlarges capacity, if not enough yet[7] |
c1 == c2
| Returns whether c1 is equal to c2
|
c1 != c2
| Returns whether c1 is not equal to c2 (equivalent to !
( c1==c2) )
|
c1 < c2
| Returns whether c1 is less than c2
|
c1 > c2
| Returns whether c1 is greater than c2 (equivalent to c2<c1 )
|
c1 <= c2
| Returns whether c1 is less than or equal to c2 (equivalent to !
( c2<c1) )
|
c1 >= c2
| Returns whether c1 is greater than or equal to c2 (equivalent to ! ( c1<c2) )
|
Table 6.4. Assignment Operations of Vectors
Operation | Effect |
---|---|
c1 = c2
| Assigns all elements of c2 to c1
|
c.assign(n,elem)
| Assigns n copies of element elem
|
c.assign(beg,end)
| Assigns the elements of the range [beg,end)
|
c1.swap(c2)
| Swaps the data of c1 and c2
|
swap(c1,c2)
| Same (as global function) |
Table 6.4 lists the ways to assign new elements while removing all ordinary elements. The set of assign()
functions matches the set of constructors. You can use different sources for assignments (containers, arrays, standard input) similar to those described for constructors on page 144. All assignment operations call the default constructor, copy constructor, assignment operator, and/or destructor of the element type, depending on how the number of elements changes. For example:
std::list<Elem> l; std::vector<Elem> coll; ... //make coll be a copy of the contents of l coll.assign(l.begin(),l.end());
Table 6.5 shows all vector operations for direct element access. As usual in C and C++, the first element has index 0
and the last element has index size()−1.
Thus, the nth element has index n−1. For nonconstant vectors, these operations return a reference to the element. Thus you could modify an element by using one of these operations (provided it is not forbidden for other reasons).
Table 6.5. Direct Element Access of Vectors
Operation | Effect |
---|---|
c.at(idx)
| Returns the element with index idx (throws range error exception if idx is out of range)
|
c[idx]
| Returns the element with index idx (no range checking)
|
c.front()
| Returns the first element (no check whether a first element exists) |
c.back()
| Returns the last element (no check whether a last element exists) |
The most important issue for the caller is whether these operations perform range checking. Only at()
performs range checking. If the index is out of range, it throws an out_of_range
exception (see Section 3.3). All other functions do not check. A range error results in undefined behavior. Calling operator [],
front(),
and back()
for an empty container always results in undefined behavior:
std::vector<Elem> coll; // empty! coll [5] = elem; // RUNTIME ERROR $$$undefined behavior std::cout << coll.front (); // RUNTIME ERROR $$$undefined behavior
So, you must ensure that the index for operator []
is valid and the container is not empty when either front()
or back()
is called:
std::vector<Elem> coll; // empty! if (coll.size() > 5) { coll [5] = elem; // OK } if (!coll.empty()) { cout << coll.front(); // OK } coll.at(5) = elem; // throws out_of_range exception
Vectors provide the usual operators to get iterators (Table 6.6). Vector iterators are random access iterators (see Section 7.2, for a discussion of iterator categories). Thus, in principle you could use all algorithms of the STL.
Table 6.6. Iterator Operations of Vectors
Operation | Effect |
---|---|
c.begin()
| Returns a random access iterator for the first element |
c.end()
| Returns a random access iterator for the position after the last element |
c.rbegin()
| Returns a reverse iterator for the first element of a reverse iteration |
c.rend()
| Returns a reverse iterator for the position after the last element of a reverse iteration |
The exact type of these iterators is implementation defined. However, for vectors they are often ordinary pointers. An ordinary pointer is a random access iterator, and because the internal structure of a vector is usually an array, it has the correct behavior. However, you can't count on it. For example, if a safe version of the STL that checks range errors and other potential problems is used, the iterator type is usually an auxiliary class. See Section 7.2.6, for a look at the nasty difference between iterators implemented as pointers and iterators implemented as classes.
Iterators remain valid until an element with a smaller index gets inserted or removed, or reallocation occurs and capacity changes (see Section 6.2.1).
Table 6.7 shows the operations provided for vectors to insert or to remove elements. As usual by using the STL, you must ensure that the arguments are valid. Iterators must refer to valid positions, the beginning of a range must have a position that is not behind the end, and you must not try to remove an element from an empty container.
Regarding performance, you should consider that inserting and removing happens faster when
Elements are inserted or removed at the end
The capacity is large enough on entry
Multiple elements are inserted by a single call rather than by multiple calls
Inserting or removing elements invalidates references, pointers, and iterators that refer to the following elements. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.
Table 6.7. Insert and Remove Operations of Vectors
Operation | Effect |
---|---|
c.insert(pos,elem)
| Inserts at iterator position pos a copy of elem and returns the position of the new element
|
c.insert(pos,n,elem)
| Inserts at iterator position pos
n copies of elem (returns nothing)
|
c.insert(pos,beg,end)
| Inserts at iterator position pos a copy of all elements of the range [beg,end ) (returns nothing)
|
c.push_back(elem)
| Appends a copy of elem at the end
|
c.pop_back()
| Removes the last element (does not return it) |
c.erase(pos)
| Removes the element at iterator position pos and returns the position of the next element
|
c.erase(beg,end)
| Removes all elements of the range [beg,end ) and returns the position of the next element
|
c.resize(num)
| Changes the number of elements to num (if size() grows, new elements are created by their default constructor)
|
c.resize(num,elem)
| Changes the number of elements to num (if size() grows, new elements are copies of elem )
|
c.clear()
| Removes all elements (makes the container empty) |
Vectors provide no operation to remove elements directly that have a certain value. You must use an algorithm to do this. For example, the following statement removes all elements that have the value val:
std::vector<Elem> coll;
...
//remove all elements with value val
coll.erase(remove(coll.begin(), coll.end(),
val),
coll.end());
This statement is explained in Section 5.6.1.
To remove only the first element that has a certain value, you must use the following statements:
std::vector<Elem> coll;
...
//remove first element with value val
std::vector<Elem>::iterator pos;
pos = find(coll.begin(),coll.end(),
val);
if (pos != coll.end()) {
coll.erase(pos);
}
The C++ standard library does not state clearly whether the elements of a vector are required to be in contiguous memory. However, it is the intention that this is guaranteed and it will be fixed due to a defect report. Thus, you can expect that for any valid index i
in vector v,
the following yields true:
&v[i] == &v[0] + i
This guarantee has some important consequences. It simply means that you can use a vector in all cases in which you could use a dynamic array. For example, you can use a vector to hold data of ordinary C-strings of type char*
or const char*:
std::vector<char> v; // create vector as dynamic array of chars v.resize(41); // make room for 41 characters (including '