Part II c++ library

Sequential Containers (Chapter 9)

A container holds a collection of objects of a specified type. Sequential containers are standard-library containers whose order of elements corresponds to positions in which the elements are added. This is opposed to ordered/unordered associative containers which store elements based on the value of a key.

STL Sequential containers

The STL offers 6 sequential container types, all of which provide _fast sequential access _to their elements. However, they offer different performance trade-offs when considering:

• Cost to add/delete
• Cost to perform non-sequentail access

Generally, vectors are said to be the most performant and should be preferred. Extending should be avoided especially in loops, prefer reserve() on initialisation.

Memory

With the exception of array which offers a fixed-size container, the rest allow flexible memory management.

The performance impact of _add/remove _and search operations are dependent on the memory layout of the container. string and vector hold elements in a contiguous memory block, and as such inserting in the adding/removing elements from the middle involves moving all elements to ensure continuity (which in turn can require allocating new memory).

The list and forward_list containers are designed for fast addition/removal from elements located anywhere in container. As such, these containers do not offer random access to elements. To access an element we must traverse the whole container.

A deque supports fast random access, but like vector and string it is expensive to insert in the middle, but fast for front/back additions & removals.

The forwared_list and array types are since c++11. array offers a safer alternative to build-in arrays. forward_list is the a zero-overhead linked list implementation. Due to speed considerations, the size() function is not offered as it would require element counting which would have costs.

The addition of move in c++11 has improved the performance of the STL containers significantly.

Usage

Generally, it is best to use vector unless there is a good reason not to. Vectors allow for data to be stored in contiguous blocks of memory, and as most applications these days are memory access bound this will be the best choice.

Exceptions:

• very frequent insert/deletion of elements in middle (consider list or forward_list)
• very frequent insert/delete at front/back but not middle (consider deque)

Iterators

Iterators provide a consistent way of accessing data members from containers, irrespective of the container type. Prefer iterators to _subscripts (integer accessors) _because it allows the underlying container type to change without effecting dependent code.

Iterators allow us to access an element from a container using a dereference operator. Iterators allow traversal of a container from one element to the next through the increment operator.

Iterator Ranges

Denoted by a pair of iterators, an iterator range refers to two elements - or one past the last element - end() - in the same container. Concept of iterator ranges is fundamental to the standard library. The second element in the range never refers to the last element but rather to 1 point past the last element.

The elements in the range include the element denoted by first to (but not including) last

mathematically represented : [begin, end)

Requirements: To iterators _begin and end _form an iterator range if:

• refer to same container
• possible to reach end by continuously incrementing begin (end cannot be precede begin)

Programming Implications [begin, end)

Library using left-inclusive ranges due to three convenient properties:

• begin == end, range is empty
• begin != end, at least one element exists in range
• _begin++, _eventually reaches end

while (begin != end) {
    *begin = val;
    ++begin;
}

Container Type Members

In addition to begin and end, reverse iterators are offered through rbegin() _and _rend().

Reverse iterators allow traversing through a container backwards, with ++ moving the iterator to the element before the current. This allows generic containers to always increment but callers to control the order by which a container is traversed.

The begin() and end() functions are overloaded, the cbegin() and cend() were introduced purely to assist with the use of auto. In other contexts, cbegin() and cend() will be used automatically when begin()/end() is called on a const object.

Container Initialisation

.. by construction

With the exception of array, every container defines a default constructor. Additionally, these containers offer a constructor with the following signature:

vector<int> v(10,-1); // size 10, default value set to -1

.. by copy

Containers can be created as a copy of another. Both container types and element types must match. Iterators are used as the parameters to define the range in which the new object should be created from.

.. by list

The new standard offers list initialisation.

list<string> numbers = {"one", "two", "three"};

NB: For all containers other than array, this method implicitly sets the size of the container.

Arrays

Similar to a build-in array, the std::array has size as part of its type. In defining an array we specify the container size.

Due to the fixed-size nature of arrays, the default-constructed array is not empty - it contains as many elements as its size. These elements are default-initialised.

array<int, 10> a1; // 10 default-initialised ints
array<int, 10> a2 = {0,1,2,3,4,5,6,7,8,9}; 
array<int, 10> a3 = {42};

NB: We cannot copy or assign objects of built-in array types, these restrictions do not apply to std::array.

Assignment & swap

Assignment operators replace the entire range of elements in the left-hand operator. In the instance that the sizes do not match, the left hand container size == right hand container size after the assignment (with relevant allocations taking place).

assign

The assignment operator requires the LHS & RHS operands are of the same type. Sequential containers also define a member named assign which replaces all the elements in the LHS with copies of the elements specified by its arguments..

vector<const char*> names = {"antoine", "waugh"};
names.size(); // 2
names.assign(names.begin(), names.begin()); // remove waugh
names.size(); // 1

swap

The _swap _operation exchanges the contents of two containers of the same type. After the cal to swap, the containers have interchanged.

vector<int> v1 = {1,2,3};
vector<int> v2 = {3,2,1};
swap(v1,v2);

NB: With the exception of array, swap does not copy, delete or insert any elements and is guaranteed to run in constant time. This fact (with the exception of string), means that iterators, references and pointers into the containers are not invalidated. As the pointers themselves have not changed, variables looking at v1[0] prior to the swap will now point to v2[0] and so forth.

**NB: Swapping of array does exchange the elements, and therefore required time is proportional to the size of the array.