15.2 Introduction to Containers2

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.

Fig. 15.1 Standard Library container classes 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.

Containers Overview

The sequence containers represent linear data structures (i.e., all of their elements are conceptually “lined up in a row”), such as arrays, vectors 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.

Near Containers

There are other container types that are considered near containers—built-in arrays, bitsets for maintaining sets of flag values and valarrays 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.

Common Container Functions

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

Fig. 15.2 Common member functions for most Standard Library containers.

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.

First-Class Container Common Nested Types

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.

Fig. 15.3 Nested types found in first-class containers.

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

Requirements for Container Elements

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.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset