Chapter 6. STL Containers
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 type of reference manual. You can find the minor details of the container interface and the exact signature of the container operations. When useful, crossreferences 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), bitmaps, 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
[1] Historically, container adapters are part of the STL. However, from a conceptional perspective, they are not part of the STL framework; they "only" use the STL.
I l@ve RuBoardI l@ve RuBoard
6.1 Common Container Abilities and Operations
6.1.1 Common Container Abilities
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:
1. All containers provide value rather than reference semantics. Containers copy elements internally when they are inserted rather than managing references to it. 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.
2. 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.
3. 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.
6.1.2 Common Container Operations
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.
Initialization
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:
[2] If a system does not provide member templates, it will typically allow only the same types. In this case, you can use the copy() algorithm instead. See page 188 for an example.
Table6.1. Common Operations of Container Classes
Operation / EffectContType 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 actual 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 c1is 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 c1and 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.clar() / 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]
[3] Thanks to John H. Spicer from EDG for this explanation.
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.
Size Operations
For all container classes, three size operations are provided:
1. size()
Returns the actual number of elements of the container.
2. 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.
3. 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.
Comparisons
The usual comparison operators ==, ! =, <, <=, >, and >= are defined according to the following three rules:
1. Both containers must have the same type.
2. Two containers are equal if their elements are equal and have the same order. To check equality of elements, use operator ==.
3. 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.
Assignments and swap ()
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.
I l@ve RuBoardI l@ve RuBoard
6.2 Vectors
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 use a dynamic array. Rather, it follows from the constraints and specification of the complexity of its operation.
Figure 6.1. Structure of a Vector
To use a vector, you must include the header file <vector>[4] :
[4] In the original STL, the header file for vectors was <vector.h>.
#include <vector>
There, the type is defined as a template class 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]
[5] In systems without support for default template parameters, the second argument is typically missing.
6.2.1 Abilities of Vectors
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.
Size and Capacity
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:
1. Reallocation invalidates all references, pointers, and iterators for elements of the vector.
2. 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 Jots 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 or changed, 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