Chapter 9. Sequential Containers

A container holds a collection fo objects of a specified type. The sequential containers let the programmer control the order in which the elements are stored and accessed.

9.1 Overview of the Sequential Containers

Sequential Container Types	Description
vector	Flexible-size array.
deque	Double-ended queue.
list	Doubly lined list.
forward_list	Singly linked list.
array	Fixed-size array.
string	A specialised container, similar to vector, that contains characters

There are few rules of thumb that apply to selecting which container to use:

• Unless you have a reason to use another container, use a vector.

• If your program has lots of small elements and space overhead matters, don't use list or forward_list.

• If the program requires random access to elements, use a vector or a deque.

• If the program needs to insert or delete elements in the middle of the container, use a list or forward_list.

• If the program needs to insert or delete elements at the front and the back, but not in the middle, use a deque.

9.2 Container Library Overview

9.2.1 Iterators

As with the containers, iterators have a common interface: If an iterator provides an operation, then the operation is supported in the same way for each iterator that supplies that operation.

An iterator range is denoted by a pair of iterators each of which refers to an element, or to one past the last element, in the same container. These two iterators, often referred to as begin and end, or as first end last, mark a range of elements from the container.

This element range is called a left-inclusive interval. The standard mathematical notion for such a range is [begin, end).

9.2.2 Container Type Members

Each container defines several types, three of these container-defined types: size_type, iterator, and const_iterator.

list<string>::iterator iter;

9.2.3 begin and end Members

The begin and end operations yield iterators that refer to the first and one past the last element in the container.

9.2.4 Defining and Initialising a Container

Operation	Description
C c;	Default constructor.
C c1(c2);	c1 is copy from c2.
C c1 = c2;	c1 is copy from c2.
C c{a, b, c};	c is a copy of the elements in the initialiser list.
C c = {a, b, c};	c is a copy of the elements in the initialiser list.
C c = (b, e);	c is a copy of the elements in the range denoted by iterators b end e.
C seq(n);	seq has n value-initialised element; this constructor is explicit.
C seq(n, t);	seq has n elements with value t.

When we initialise a container as a copy of another container, the container type and element type of both containers must be identical.

Under the new standard, we can list initialise a container:

list<string> authors = {"Milton", "Shakespeare", "Austen"};

We can also initialise the sequential containers from a size and an element initialiser:

vector<int> ivec(10, -1);

The constructors that take a size are valid only for sequential containers; they are not supported for the associative containers.

When we define an array, in addition to specifying the element type, we also specify the container size:

array<int, 42>

9.2.5 Assignment and swap

The assignment operator replace the entire range of elements int eh left-hand container with copies of the elements from the right-hand operand.

Container Assignment Operations	Description
c1 = c2;	Replace the elements in c1 with copies of the elements in c2.
c = {a, b, c};	Replace the elements in c1 with copies of the elements in the initialiser list.
swap(c1, c2);	Exchanges element in c1 with those in c2.
c1.swap(c2);
seq.assign(b, e);	Replaces elements in seq with those in the range denoted by iterators be and e.
seq.assign(il);	Replaces the elements in seq with those in the initialiser list il.
seq.assign(n, t);	Replaces the elements in seq with n elements with value t.

The assignment operator requires that the left-hand and right-hand operands have the same type. It copies all the elements from the right-hand operand into left-hand operand.

The swap operation exchanges the contents of two containers of the same type.

In the new library, the containers offer both a member and nonmember version of swap. Earlier versions of the library defined only the member version of swap. The nonmember swap is of most importance in generic programs.

9.2.6 Container Size Operations

The size member returns the number of elements in the container; empty returns a bool that is true if size is zero and false otherwise; and max_size returns a number that is greater than or equal to the number of elements a container of that type can contain.

9.2.7 Relation Operators

Comparing two containers performs a pairwise comparison of the elements:

• If both containers are the same size and all the elements are equal, then the two containers are equal; otherwise, they are unequal.

• If the containers have different sizes but every element of the smaller one is equal to the corresponding element of the larger one, then the smaller one is less than the other.

• If neither container is an initial subsequence of the other, then the comparison depend s on comparing the first unequal elements.

We can use a relational operator to compare two containers only if the appropriate comparison operator is defined for the element type.

9.3 Sequential Container Operations

9.3.1 Adding Elements to a Sequential Container

Operations That Add Elements to a Sequential Container	Description
c.push_back(t);	Creates an element with value t or constructed from args at the end of c.
c.emplace_back(args);
c.push_front(t);	Creates an element with value t or constructed from args on the front of c.
c.emplace_front(args);
c.insert(p, t);	Create an element with value t or constructed from args before the element denoted by iterator p.
c.emplace(p, args);
c.insert(p, n, t);	Inserts n elements with value t before the element denoted by iterator p.
c.insert(p, b, e);	Inserts the elements from the range denoted by iterators b and e before the element denoted by iterator p.
c.insert(p, il);	il is a braced list of element values.

In the call to emplace_back, that object is crated directly in space managed by the container The call to push_back creates a local temporary object that is pushed onto the container.

9.3.2 Accessing Elements

Operations to Access Elements in a Sequential Container	Description
c.back();	Returns a reference to the last element in c.
c.front();	Returns a reference to the first element in c.
c[n];	Returns a reference to the element indexed by the unsigned integral value n.
c.at(n);	Returns a reference to the element indexed by n.

The members that access elements in a container return references. If the container is a const object, the return is a reference to const. If the container is not const, the return is an ordinary reference that we can use to change the value of the fetched element.

9.3.3 Erasing Elements

erase Operations on Sequential Containers	Description
c.pop_back();	Removes last element in c.
c.pop_front();	Removes first element in c.
c.erase(p);	Removes the element denoted by the iterator p.
c.erase(b, e);	Removes the range of elements denoted by the iterators b and e.
c.clear();	Removes all the elements in c.

9.3.4 Specialised forward_list Operations

Operations to Insert or Remove Elements in a forward_list	Description
lst.before_begin();	Iterator denoting the nonexistent element just before the beginning of the list
lst.cbefore_begin();
lst.insert_after(p, t);	Inserts element after the one denoted by iterator p. t is an object.
lst.insert_after(p, n, t);	n is a count.
lst.insert_after(p, b, e);	b and e are iterators denoting a range.
lst.insert_after(p, il);	il is a braced list.
emplace_after(p, args);	Uses args to construct an element after the one denoted by iterator p.
lst.erase_after(p);	Removes the element after the one denoted by iterator p or the range of elements from the one after the iterator b up to but not including the one denoted by e.
lst.erase_after(b, e);

9.3.5 Resizing a Container

Sequential Size Operations	Description
c.resize(n);	Resize c so that it has n elements.
c.resize(n, t);	Resize c to have n elements.

9.3.6 Container Operations May Invalidate Iterators

Operations that add or remove elements from a container can invalidate pointers, references, or iterators to container elements. An invalidated pointer, reference, or iterator is one that no longer denotes an element.

After an operation that adds elements to a container:

• Iterators, pointers, and references to a vector or string are invalid if the container was reallocated.

• Iterators, pointers, and references to a deque are invalid if we add elements anywhere but at the front or back.

• Iterators, pointers, and references to a list or forward_list remain valid.

After we remove an element:

• All other iterators, references, or pointers to a list or forward_list remain valid.

• All other iterators, references, or pointers to a deque are invalidated if the removed elements are anywhere but the front or back.

• All other iterators, references, or pointers to a vector or string remain valid for elements before the removal point.

9.4 How a vector Grows

To support fast random access, vector elements are stored contiguously, each element is adjacent to the previous element.

When they have to get new memory, vector and string implementations typically allocate capacity beyond what is immediately needed. The container holds this storage in reserve and uses it to allocate new elements as they are added. reserve does not change the number of elements in the container; it affects only how much memory the vector preallocates.

A call to reserve changes the capacity of the vector only if the requested space exceeds the current capacity. A call to reserve will never reduce the amount of space that the container uses.

Container Size Management	Description
c.shrink_to_fit();	Request to reduce capacity() to equal size().
c.capacity();	Number of elements c can have before reallocation is necessary.
c.reserve(n);	Allocate space for at least n elements.

it is important to understand the difference between capacity and size. The size of a container is the number of elements it already holds; its capacity is how many elements it can hold before more space must be allocated.

9.5 Additional string Operations

9.5.1 Other Ways to Construct strings

Additional Operation of strings	Description
string s(cp, n);	s is a copy of the first n characters in the array to which cp points.
string s(s2, pos2);	s is a copy of the characters in the string s2 starting at the index pos2.
string s(s2, pos2, len2);	s is a copy of len2 characters from s2 starting at the index pos2.
s.substr(pos, n);	Return a string containing n characters from s starting at pos.

9.5.2 Other Ways to Change a string

Operations to Modify strings	Description
s.insert(pos, args);	Insert characters specified by args before pos.
s.erase(pos, len);	Remove len characters starting at position pos.
s.assign(args);	Replace characters in s according to args.
s.append(args);	Append args to s.
s.replace(range, args);	Remove range of characters from s and replace them with the characters formed by args.

The assign and append functions have no need to specify what part of the string is changed: assign is always replaces the entire contents of the string and append always adds to the end of the string.

9.5.3 string Search Operations

string Search Operations	Description
s.find(args);	Find the first occurrence of args in s.
s.rfind(args);	Find the last occurrence of args in s.
s.find_first_of(args);	Find the first occurrence of any character from args in s.
s.find_last_of(args);	Find the last occurrence of any character from args in s.
s.find_first_not_of(args);	Find the first character in s that is not in args.
s.find_last_not_of(args);	Find the last character in s that is not in args.

9.5.4 The compare Functions

s.compare returns zero or a positive or negative value depending on whether s is equal to, greater than, or less than the string formed from the given arguments.

Possible Arguments to s.compare	Description
s2	Compare s to s2.
pos1, n1, s2	Compares n1 characters starting at pos1 from s to s2.
pos1, n1, s2, pos2, n2	Compares n1 characters starting at pos1 from s the n2.
cp	Compares s to the null-terminated array pointed to by cp.
pos1, n1, cp	Compares n1 characters starting at pos1 from s to cp.
pos1, n1, cp, n2	Compares n1 characters starting at pos1 from s to n2 characters starting from the pointer cp.

9.5.5 Numeric Conversions

Conversions between strings and Numbers	Description
to_string(val);	Overloaded functions returning the string representation of val.
stoi(s, p, b);	Return the initial substring of s that has numeric content as an int, long, unsigned long, long long, unsigned long long.
stol(s, p, b);
stoul(s, p, b);
stoll(s, p, b);
stoull(s, p, b);
stof(s, p);	Return the initial numeric substring in s as a float, double, or long double.
stod(s, p);
stold(s, p);

If the string can't be converted to a number, these functions throw an invalid_argument exception. If the conversion generates a value that can't be represented, they throw out_of_range.

9.6 Container Adaptors

In addition to the sequential containers, the library defines three sequential container adaptors: stack, queue, and priority_queue.

Operations and Types Common to the Container Adaptors	Description
size_type	Type large enough to hold the size of the largest object of this type.
value_type	Element type.
container_type	Type of the underlying container on which the adaptor is implemented.
A a;	Create a new empty adaptor named a.
A a(c);	Create a new adaptor named a with a copy of the container c.
relation operators	Each adaptor supports all the relational operators: ==, !=, <, <=, >, >=.
a.empty();	false if a has any elements, true otherwise.
a.size();	Number of elements in a.
swap(a, b);	Swaps the contents of a and b.
a.swap(b);

Each adaptor defines two constructor: the default constructor that creates an empty object, and a constructor that takes a container and initialises the adaptor by copying the given container.

By default both stack and queue are implemented in terms of deque, and a priority_queue is implemented on a vector.

The stack type is defined in the stack header.

Stack Operations	Description
s.pop();	Removes, but does not return, the top element from the stack.
s.pus(item);	Creates a new top element on the stack by copying or removing item, or by constructing the element from args.
s.emplace(args);
s.top()	Returns, but does not remove, the top element on the stack.

The queue and priority_queue adaptors are defined in the queue header.

queue, priority_queue Operations	Description
q.pop();	Removes, but does not return, the front element or highest-priority element from the queue or priority_queue, respectively.
q.front();	Returns, but does not remove, the front or back element of q.
q.back();	Valid only for queue.
q.top();	Returns, but does not remove, the highest-priority element, valid only for priority_queue.
q.push(item);	Create an element with value item or constructed from args at the end of the queue or inits appropriate position in priority_queue.
q.emplace(args);

A priority_queue lets us establish a priority among the elements held in the queue.