The Standard Library container types are shown in Fig. 15.1. The containers are divided into four major categories—sequence containers, ordered associative containers, unordered associative containers and container adapters.
Container class | Description |
---|---|
Sequence containers | |
array |
Fixed size. Direct access to any element. |
deque |
Rapid insertions and deletions at front or back. Direct access to any element. |
forward_list |
Singly linked list, rapid insertion and deletion anywhere. Added in C++11. |
list |
Doubly linked list, rapid insertion and deletion anywhere. |
vector |
Rapid insertions and deletions at back. Direct access to any element. |
Ordered associative containers—keys are maintained in sorted order | |
set |
Rapid lookup, no duplicates allowed. |
multiset |
Rapid lookup, duplicates allowed. |
map |
One-to-one mapping, no duplicates allowed, rapid key-based lookup. |
multimap |
One-to-many mapping, duplicates allowed, rapid key-based lookup. |
Unordered associative containers | |
unordered_set |
Rapid lookup, no duplicates allowed. |
unordered_multiset |
Rapid lookup, duplicates allowed. |
unordered_map |
One-to-one mapping, no duplicates allowed, rapid key-based lookup. |
unordered_multimap |
One-to-many mapping, duplicates allowed, rapid key-based lookup. |
Container adapters | |
stack |
Last-in, first-out (LIFO). |
queue |
First-in, first-out (FIFO). |
priority_queue |
Highest-priority element is always the first element out. |
The sequence containers represent linear data structures (i.e., all of their elements are conceptually “lined up in a row”), such as array
s, vector
s and linked lists. We’ll study linked data structures in Chapter 19, Custom Templatized Data Structures. Associative containers are nonlinear data structures that typically can locate elements stored in the containers quickly. Such containers can store sets of values or key–value pairs in which each key has an associated value—for example, a program might associate employee IDs with Employee
objects. As you’ll see, some associative containers allow multiple values for each key. The keys in associative containers are immutable (they cannot be modified) as of C++11. The sequence containers and associative containers are collectively referred to as the first-class containers. Stacks and queues are typically constrained versions of sequence containers. For this reason, the Standard Library implements class templates stack
, queue
and priority_queue
as container adapters that enable a program to view a sequence container in a constrained manner. Class string
supports the same functionality as a sequence container, but stores only character data.
There are other container types that are considered near containers—built-in arrays, bitset
s for maintaining sets of flag values and valarray
s for performing high-speed mathematical vector operations (not to be confused with the vector
container). These types are considered near containers because they exhibit some, but not all, capabilities of the first-class containers.
Most containers provide similar functionality. Many operations apply to all containers, and other operations apply to subsets of similar containers. Figure 15.2 describes the many functions that are commonly available in most Standard Library containers. Overloaded operators <
, <=
, >
, >=
, ==
and !=
perform element-by-element comparisons. Overloaded operators <
, <=
, >
, >=
, ==
and !=
are not provided for priority_queue
s. Overloaded operators <
, <=
, >
and >=
are not provided for the unordered associative containers. Member functions rbegin
, rend
, crbegin
and crend
are not available in a forward_list
. Before using any container, you should study its capabilities.
Member function | Description |
---|---|
default constructor | A constructor that initializes an empty container. Normally, each container has several constructors that provide different ways to initialize the container. |
copy constructor | A constructor that initializes the container to be a copy of an existing container of the same type. |
move constructor | A move constructor (added in C++11 and discussed in Chapter 24) moves the contents of an existing container into a new container of the same type—the old container no longer contains the data. This avoids the overhead of copying each element of the argument container. |
destructor | Destructor function for cleanup after a container is no longer needed. |
empty |
Returns true if there are no elements in the container; otherwise, returns false . |
insert |
Inserts an item in the container. |
size |
Returns the number of elements currently in the container. |
copy operator= |
Copies the elements of one container into another. |
move operator= |
The move assignment operator (added in C++11 and discussed in Chapter 24) moves the elements of one container into another container of the same type—the old container no longer contains the data. This avoids the overhead of copying each element of the argument container. |
operator< |
Returns true if the contents of the first container are less than the second otherwise, returns false . |
operator<= |
Returns true if the contents of the first container are less than or equal to the second; otherwise, returns false . |
operator> |
Returns true if the contents of the first container are greater than the second; otherwise, returns false . |
operator>= |
Returns true if the contents of the first container are greater than or equal to the second; otherwise, returns false . |
operator== |
Returns true if the contents of the first container are equal to the contents of the second; otherwise, returns false . |
operator!= |
Returns true if the contents of the first container are not equal to the contents of the second; otherwise, returns false . |
swap |
Swaps the elements of two containers. As of C++11, there is a non-member-function version of swap that swaps the contents of its two arguments (which must be of the same container type) using move operations rather than copy operations. |
max_size |
Returns the maximum number of elements for a container. |
begin |
Overloaded to return either an iterator or a const_iterator that refers to the first element of the container. |
end |
Overloaded to return either an iterator or a const_iterator that refers to the next position after the end of the container. |
cbegin (C++11) |
Returns a const_iterator that refers to the container’s first element. |
cend (C++11) |
Returns a const_iterator that refers to the next position after the end of the container. |
rbegin |
The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the last element of the container. |
rend |
The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the position before the first element of the container. |
crbegin (C++11) |
Returns a const_reverse_iterator that refers to the last element of the container. |
crend (C++11) |
Returns a const_reverse_iterator that refers to the position before the first element of the container. |
erase |
Removes one or more elements from the container. |
clear |
Removes all elements from the container. |
Figure 15.3 shows the common first-class container nested types (types defined inside each container class definition). These are used in template-based declarations of variables, parameters to functions and return values from functions (as you’ll see in this chapter and Chapter 16). For example, value_type
in each container always represents the type of elements stored in the container. The types reverse_iterator
and const_reverse_iterator
are not provided by class forward_list
.
typedef |
Description |
---|---|
allocator_type |
The type of the object used to allocate the container’s memory—not included in class template array . |
value_type |
The type of element stored in the container. |
reference |
A reference for the container’s element type. |
const_reference |
A reference for the container’s element type that can be used only to read elements in the container and to perform const operations. |
pointer |
A pointer for the container’s element type. |
const_pointer |
A pointer for the container’s element type that can be used only to read elements and to perform const operations. |
iterator |
An iterator that points to an element of the container’s element type. |
const_iterator |
An iterator that points to an element of the container’s element type. Used only to read elements and to perform const operations. |
reverse_iterator |
A reverse iterator that points to an element of the container’s element type. Iterates through a container back-to-front. |
const_reverse_iterator |
A reverse iterator that points to an element of the container’s element type and can be used only to read elements and to perform const operations. Used to iterate through a container in reverse. |
difference_type |
The type of the result of subtracting two iterators that refer to the same container (the overloaded - operator is not defined for iterators of list s and associative containers). |
size_type |
The type used to count items in a container and index through a sequence container (cannot index through a list ). |
Before using a Standard Library container, it’s important to ensure that the type of objects being stored in the container supports a minimum set of functionality. When an object is inserted into a container, a copy of the object is made. For this reason, the object type should provide a copy constructor and copy assignment operator (custom or default versions, depending on whether the class uses dynamic memory). Also, the ordered associative containers and many algorithms require elements to be compared—for this reason, the object type should provide less-than (<
) and equality (==
) operators. As of C++11, objects can also be moved into container elements, in which case the object type needs a move constructor and move assignment operator—Chapter 24 discusses move semantics.