3/9

3. STL Data structure

The C++ standard library called STL (Standard Template Library) propose a set of generic containers and algorithms modeling standard data structure.

Note that at the beginning of C++ language, STL was more limited and not always available. Therefore multiple user defined libraries have been defined (ex. ad-hoc dynamic vectors, etc) leading to, sometimes, incoherent design and lack of robustness. Today, STL is widely available, efficiently implemented and optimized, and covers basic data structures (arrays, linked lists, dictionaries, hash table, etc). It is highly suggested that you consider in priority using containers of the standard library, instead of defining from scratch basic containers.

General principle of containers

All containers of STL are defined on the principle to be generic, coherent, and efficient. To this end

  • Elements within containers are template types. It means, that STL containers can contain any object as long as the type is known at compile time. Templates are generic types known at compile time. Template allows to write generic functions independently of the variable type, but contrary to dynamic typing, doesn’t involve any indirection that would lead to extra computational cost.

  • All container elements can be accessed using iterators in a similar way.

  • Methods proposed by default on a given container are limited to efficient operations on them.

Iterators

Iterators are STL-defined objects able to designate an element within a container, and to be able to iterate to other elements.

All iterators it have, at least, the following property. * *it access to the current designated element (*it returns a reference to the pointed variable) * ++it iterate over the current designated element to the next one.

Note that iterators have been designed to be compatible with pointers notations, and can be seen as a safer, and more general (next element is not necessarily contiguous in memory like with pointers), pointer object.

Depending on containers, more iterating possibility can be offered, ex. --it to go to previous element, it += k moving forward k times, etc.

Let suppose a container of type C. * C::iterator is the type of the iterator * C.begin() returns the iterator pointing on the first element of the container. * C.end() returns the iterator pointing after the last element of the container (you should not try to access the element of this iterator).

Example of iterating over a container

Example of iterator use to travel through all elements of a container C

// iterator on the first element of C
C::iterator it     = C.begin();
// iterator following the last element of C
C::iterator it_end = C.end();


// loop over all elements
while( it != it_end )
{
   ... // get value using *it
   ++it; // iterate over the next element
}

Or, more concisely using a for loop

for( C::iterator it=C.begin(), it_end=C.end(); it != it_end; ++it )
{
  ... // use *it within the loop
}

Note that, in modern C++, the same result can be obtained using for-range loop syntax that uses iterator implicitly

for( type& element : C )
{
  ... // use directly element
}

const_iterator

Default iterator have by default the property to modify the pointed value (*it returns a non const reference). This is to be avoided in the case where values of the container should only be accessed, and not modified.

const_iterator are similar to iterator, but ensure that designated elements cannot be modified.

Similarily to iterators, we have

  • C::const_iterator is the type of the const_iterator

  • C.cbegin() returns the const iterator pointing on the first element of the container.

  • C.cend() returns the const iterator pointing after the last element of the container.

// const_iterator on the first element of C
C::const_iterator it     = C.cbegin();
// const_iterator following the last element of C
C::const_iterator it_end = C.cend();


// loop over all elements
while( it != it_end )
{
   ... // get value using *it (can read, but not write on *it)
   ++it; // iterate over the next element
}

for( C::const_iterator it=C.cbegin(), it_end=C.cend(); it != it_cend; ++it )
{
  ... // use *it within the loop
}

for( const type& element : C )
{
  ... // use directly element
}

The following rules applies

  • Iterators retrieved by C.begin() and C.end() are automatically

    • non const iterator, if C is non const qualified.

    • const iterator, if C is const qualified.

  • const iterators can be retrieved from both const and non const qualified containers.

  • non const iterators can be only be retrieved non const qualified containers.

As good practice, you should always prefer by default the use of const iterators. Use only non const iterators when you explicitly want to modify the value of elements.

Vector

std::vector are generic container for sequence of elements with dynamic size. It will be the most used container when dealing with large buffer of data.

STL vectors have the following properties

  • Elements are stored on heap memory [1]

    • Allocation and desallocation is automatically handled by the container.

    • Large amount of data (up to your memory RAM) can be stored in std::vector.

  • All elements are contiguous in memory.

    • Fully compatible with C pointers.

    • Fast random access to any element (O(1)).

  • Elements can be added efficiently at the end of the vector

    • Usually in O(1), and at worst O(N) exceptionnaly.

std::vector replace C dynamic vectors allocated using malloc (or new in C++ ). They have the same efficiency as no supplementary indirection has to be performed. But the data allocation is fully transparent to the user.

Array

array are generic container for sequence of elements with static size. It can be used to safely replace C-style array (T[N]) to store limited number of elements.

STL arrays have the following properties

  • Elements are stored on stack memory.

    • Fastest creation and access to elements, but should be restrained to a few number of elements (up to some MB) within the limit of allowed stack by the system.

  • All elements are contiguous in memory.

  • Size is known at compile time.

Dictionaries

map are dictionary storing key-value pair of elements. Each key must be unique [2]. Maps are generic data structure allowing to generically and efficiently set an association between a key and a value.

STL maps have the following properties

  • Elements are sorted in order, using the \(<\) operator.

  • Element lookup, addition, and deletion (from key) in complexity O(log N). [3]

tuples

tuples are static size collection of, potentially, heterogeneous values. Tuples can be used for instance to pass multiple values as argument, or to be returned by functions, without having to declared a named object.

STL tuples have the following properties

  • Types and number of tuple elements must be known at compile time.

  • Access to k-th tuple must be known at compile time (zero run time cost).

std::tuple <int, float, double> t {1, 2.3f, 5.4};


std::get<0>(t) += 2;


std::cout << std::get<0>(t) << std::endl;
std::cout << std::get<1>(t) << std::endl;
std::cout << std::get<2>(t) << std::endl;

In template programming, tuples can be used to iterate safely over arbitrary number of elements at compile time.

Other containers

STL defines other standard containers that you may use for your algorithms such as linked list (std::list), stack (std::stack), queue (std::queue), priority queue (std::priority_queue), unique set (std::set), hash table (unordered_map, and unordered_multimap), etc.

Exercise

  • Create a function computing the cartesian norm of a std::array of 3 floats.

  • Create a function taking as argument a std::vector of string, and concatenates all strings into a single one. Modify this function such that you add a comma between all strings.

  • Create a map associating to a year (given by an integer) a list of events (as std::vector<std::string>). Fill this map and create a function displaying on the console all year and associated events.

1. Heap memory, at the opposite of Stack memory, is not limited in size. However its management must be handled manually (allocation and desallocation)
2. See multimap for instance when dealing with multiple keys
3. maps can be implemented as red-black tree (self balancing binary search tree)