Chapter #11 - Standard Template Libraries (STL)

containers, iterators, algorithms and example code

11.0 Prologue

The C++ language comes with a great collection of standard libraries. There are scores of very well designed facilities and more just arrived with the new standardization C++20. In this part we will be discussing the Standard Template Libraries (STL).

11.1 STL Libraries

Fig 1. STL Iterators

The STL consists of a fairly large collection of containers, scores of algorithms, and iterators. Iterators are the glue that binds algorithms to containers.

Iterators are a special form of smart pointer. Each container defines a set of iterators that know how to traverse its structure. That may be a simple process for contiguous memory containers like std::vector, but significantly more detailed for containers like std::unordered_map. For the map, an iterator must be able to traverse a hash table, stepping over empty slots, and walk up bucket lists.

Containers each have a set of iterators, e.g., C::iterator, C::const_iterator, C::reverse_iterator, etc. They also define traits like C::value_type. value_types are aliases for the type of value defined for an application's instantiation of a container. So, for std::vector<std::pair<int, double>> the value type would be std::pair<int, double>.

11.2 Containers

There are three groups of STL containers: sequential, associative, and adaptors. The sequential containers arrange their elements in a linear sequence. All of the sets and maps are associative containers based on binary trees or hash tables. The std::stack, std::queue, and std::priority_queue are adapters, built on top of another container. All the other containers are sequential.

Table 1. List of STL Containers

- Simple code demos for each container

Container	Description
std::array<T,N>	Fixed size array residing entirely in the local stackframe. This is the only container, other than native arrays, that manages its data in the stack. All others place their data in the native heap.
std::deque<T>	Indexable container with FIFO semantics constructed from three blocks of contiguous memory for fast access to the front and back.
std::list<T>	doubly-linked list, iterable but not indexable, can be traversed in either direction.
std::map<K,V>	Balanced binary tree with associative lookup: myMap[key] returns value. Duplicate keys are not allowed.
std::multi_map<K,V>	Same as std::map but duplicate keys are allowed.
T t[N]	Native array is indexable and iterable with native T* pointer. The functions std::begin and std::end allow native arrays to be iterated with range-based for loops.
std::priority_queue<T>	Heap structure that returns the largest of its elements.
std::queue<T>	An adapter, by default based on std::deque, has FIFO semantics. It is not iterable or indexable.
std::set<T>	Based on balanced binary tree, does not allow duplicate keys.
std::multi_set<T>	Same as std::set except that it does allow duplicate keys.
std::singlelist<T>	Singly linked list, is iterable with forward iterator but not indexable.
std::stack<T>	An adapter, by default implemented using std::deque, has LIFO semantics, is not iterable or indexable.
std::string<Char>	Has all of the attributes of the other containers, is iterable and indexable.
std::unordered_map<K,V>	Hashed associative container with unique keys. Has a set of hash functions supplied by default for the primative types and strings.
std::unordered_multimap<K,V>	Same as std::unordered_map except that duplicate keys are allowed.
std::unordered_set<K>	Hashed set with unique keys.
std::unordered_multiset<K>	Same as std::set except that keys do not have to be unique.
std::vector<T>	Expandable array that is iterable and indexable.

All of the containers have value semantics: they can be copied, assigned, and moved. That means that classes that have only numeric type and/or STL container members will have value semantics, using compiler generated methods. So they tend to be small and simple because the STL containers do most of the heavy lifting.

11.3 Algorithms

The algorithms in the STL are not engineering or scientific algorithms, e.g., optimization or fast Fourier transforms. They are relatively simple processes on collections of data held in an STL container.

Table 2. - Partial List of Algorithnms

- complete list

Algorithms	Description
for_each	applies operation to each element
all_of, any_of, non_of	checks if a predicate is true for all, any, or none of the elements
count, count_if	returns numver of elements satisfying predicate
find, find_if, find_if_not	finds first element satisfying a predicate
find_first_of	searches for any one of a set of elements
search	searches for a range of elements
copy, copy_if	copies a range of elements to a new location
move	moves a range of elements to a new location
fill	copies value to every element in a range
transform	applies operation to a range of elements, storing results in a destination range
generate	applies results of operation to every element of a range
remove, remove_if	remove elements satisfying predicate
replace, replace_if	replaces all values satisfying predicate with new value
swap_ranges	swaps two ranges of elements
reverse	reverses order of elements in range
rotate	rotates order of elements in range
shift_left, shift_right	shifts elements in a range
unique	removes consecutive duplicates in range
partition	divides elements of a range into two groups
sort	sorts a range into ascending order
stable_sort	sorts a range of elements while preserving order of equal elements
merge	merges two sorted ranges
max_element, min_element	returns largest or smallest element in range
equal	determines if two ranges are equal
lexicographical_compare	returns true if one range is alphabetically less than another
accumulate	finds sum of a range of elements

As provided in C++17, the code using standard algorithms tends to be fairly complicated, littered with iterators and can't easily be composed. That gets better in C++20 with the new STL range technology. In the mean-time, there are some things we can do to beautify our algorithm codes as illustrated in the examples below.

11.4 Examples

The first example shows standard usage for the std::for_each, std::find, and std::copy algorithms. With std::copy we use a std::ostream_iterator, std::inserter, and std::back_inserter which does push_backs on a destination container.

Example: Standard Uses

Definitions: Op, show, and Vec, Lst, iterator

#include <string> #include <vector> #include <list> #include <set> #include <unordered_map> #include <iostream> #include <functional> #include <algorithm> #include "../Chapter7-Display/Chap7Display.h" template<typename V> class Op { public: void operator()(V v) { if (first) { std::cout << "\n " << v; first = false; } else { std::cout << ", " << v; } } private: bool first = true; }; template<typename C> bool contains(C c, typename C::value_type v) { typename C::iterator iter = std::find(c.begin(), c.end(), v); return iter != c.end(); } template<typename C> void show(C& c) { std::cout << " "; for_each( c.begin(), c.end(), Op<typename C::value_type>() ); } template<typename T> using Vec = std::vector<T>; template<typename T> using Lst = std::list<T>; template<typename T> using iterator = typename std::vector<T>::iterator;

Using Code:

int main() { displayDemo("-- traditional algo use --"); Vec<int> vecInt{ 1, 2, 3, 4, 5 }; std::for_each( vecInt.begin(), vecInt.end(), Op<int>() ); int val = 3; std::cout << std::boolalpha; std::cout << "\n vecInt contains " << val << ": " << contains(vecInt, val); iterator<int> iter = std::find( vecInt.begin(), vecInt.end(), val ); std::cout << "\n found " << val << " at location " << iter - vecInt.begin(); val = 0; std::cout << "\n vecInt contains " << val << ": " << contains(vecInt, val); displayDemo( "\n -- copy with ostream_inserter --" ); auto outIter = std::ostream_iterator<int>( std::cout, " " ); putline(1, " "); std::copy( vecInt.begin(), vecInt.end(), outIter ); displayDemo( "\n -- copy with back_inserter --" ); Vec<int> dstVec; auto binserter = std::back_inserter(dstVec); auto begin = [&vecInt]() { return vecInt.begin(); }; auto end = [&vecInt]() { return vecInt.end(); }; std::copy(begin(), --end(), binserter); show(dstVec); displayDemo("\n -- copy with inserter --"); auto inserter = std::inserter(dstVec, ++++dstVec.begin()); std::copy(begin(), end(), inserter); show(dstVec); putline(2); }

Output

-- traditional algo use -- 1, 2, 3, 4, 5 vecInt contains 3: true found 3 at location 2 vecInt contains 0: false -- copy with ostream_inserter -- 1 2 3 4 5 -- copy with back_inserter -- 1, 2, 3, 4 -- copy with inserter -- 1, 2, 1, 2, 3, 4, 5, 3, 4

In the next example, we develop a Collections construct that, similar to the C++20 std::range, holds a starting iterator and an ending iterator. It, optionally, may also hold a callable object that will be applied to each element of the Collection's container.

We then wrap the std::for_each algorithmn in a foreach function - simple 4 lines of code - that accepts a collection and an operation. With this, the resulting code hides the iterator syntax to make a more readable operation.

Example: Uses Range-Like Construct

In the left panel we define som operations: ShowOp, SumOp and a Range-like construction: Collection that holds first and last iterators and optionally an operation.

In the right panel we show that, using Collections, we get a very readable syntax:

ShowOp<std::string> showCout

foreach(rFriends, showCout)

That tells the reader that we are showing each of our friends names on std::cout.

The traditional for_each is much more verbose:

std::for_each(vecSt.begin(), vecStr.end(), ShowOp<std::string>());

The meaning is not particularly obvious until you look at the code in detail.

Chap8ModifiedDemos.cpp

#include <string> #include <vector> #include <list> #include <iostream> #include <algorithm> #include <type_traits> #include "../Chapter7-Display/Chap7Display.h" template<typename V> class ShowOp { public: ShowOp(const std::string& prefix = ", ") : prefix_(prefix) {} void operator()(V v) { if (first) { std::cout << "\n " << v; first = false; } else { std::cout << prefix_ << v; } } private: bool first = true; std::string prefix_ = ", "; }; template<typename V> class SumOp { public: void operator()(V v) { sum_ += v; } V sum() { return sum_; } private: V sum_; }; template<typename C> bool contains(C c, typename C::value_type v) { typename C::iterator iter = std::find(c.begin(), c.end(), v); return iter != c.end(); } template<typename C> void show(C& c) { std::cout << " "; for_each( c.begin(), c.end(), ShowOp<typename C::value_type>() ); } template<typename T> using Vec = std::vector<T>; template<typename T> using Lst = std::list<T>; template<typename T> using vecIterator = typename std::vector<T>::iterator; template<typename O> struct Null {}; /*----------------------------------------- This is an important part - defines Range-like construct -----------------------------------------*/ template< typename C, template<typename> class Op = Null > struct Collection { Collection( C& c, Op<typename C::value_type> op_ = Null< typename C::value_type>() ) : op(op_) { first = c.begin(); last = c.end(); } typename C::iterator first; typename C::iterator last; Op<typename C::value_type> op; }; /*----------------------------------------- This is another important part - defines foreach taking a Collection -----------------------------------------*/ template< typename C, template<typename> class Op > typename Op<typename C::value_type> foreach( Collection<C, Op> rng, Op<typename C::value_type> op ) { return std::for_each(rng.first, rng.last, op); } template< typename C, template<typename> class Op > typename Op<typename C::value_type> foreach( Collection<C> rng, Op<typename C::value_type> op ) { return std::for_each(rng.first, rng.last, op); } template< typename C, template<typename> class Op > typename Op<typename C::value_type> foreach(Collection<C, Op> rng) { return std::for_each( rng.first, rng.last, rng.op ); }

Using Code:

int main() { displayDemo("-- traditional algo use --"); Vec<int> vecInt{ 1, 2, 3, 4, 5 }; std::for_each( vecInt.begin(), vecInt.end(), ShowOp<int>() ); displayDemo("\n -- using generic synonyms --"); Vec<std::string> vecStr{ "Joe", "Sally", "Ashok", "Ming", "Hasim" }; Collection<Vec<std::string>, ShowOp> rFriends(vecStr, ShowOp<std::string>()); /*-- std algorithm with synonym arguments*/ std::for_each( rFriends.first, rFriends.last, rFriends.op ); /*------------------------------------------- prettified using Collection with embedded operation -------------------------------------------*/ foreach(rFriends); /*------------------------------------------- prettified using Collection and separate operation -------------------------------------------*/ ShowOp<std::string> showCout; foreach(rFriends, showCout); putline(); Collection<Vec<int>, SumOp> vecIntColl(vecInt, SumOp<int>()); SumOp<int> ret = foreach(vecIntColl, SumOp<int>()); show(vecInt); std::cout << "\n sum = " << ret.sum(); /*------------------------------------------- More tests -------------------------------------------*/ displayDemo("\n -- more tests --"); putline(); Vec<double> vecDbl{ 1.0, -1.0, 0.5 }; Collection< Vec<double>, SumOp> vecDblColl(vecDbl, SumOp<double>()); Collection<Vec<double>> vecDblColl2(vecDbl); SumOp<double> retd = foreach(vecDblColl2, SumOp<double>()); double sumd = foreach( vecDblColl2, SumOp<double>() ).sum(); show(vecDbl); std::cout << "\n sumd = " << retd.sum(); std::list<int> listInt{ 1, 2, 3, 2, 1 }; Collection<Lst<int>> listIntColl(listInt); foreach(listIntColl, ShowOp<int>()); int sumi = foreach( listIntColl, SumOp<int>() ).sum(); std::cout << "\n sum of list = " << sumi; putline(2); }

Output:

-- traditional algo use -- 1, 2, 3, 4, 5 -- using generic synonyms -- Joe, Sally, Ashok, Ming, Hasim Joe, Sally, Ashok, Ming, Hasim Joe, Sally, Ashok, Ming, Hasim 1, 2, 3, 4, 5 sum = 15 -- more tests -- 1, -1, 0.5 sumd = 0.5 1, 2, 3, 2, 1 sum of list = 9

Here's a link to a nice description of how the C++20 std::range facility works: C++ Ranges Library - Jonathan Boccara, Fluent C++

11.5 Epilogue

The Standard Template Library (STL) is a very nice collection of containers and algorithms, bound together with iterators. We've shown, in Chapter2 - Data, that complex data structures can be "snapped together" very easily using the existing STL containers.

The algorithms, with a bit of juice from template metaprogramming, can make your code much more declarative - readable and easy to reason about. The std::range facilities coming in C++20 will provide a lot of the benefit we've shown using Collections, so we will be able to just use the std::libraries.

It takes quite a lot of mental energy to wrap your mind around the processes for template metaprogramming. Using TMP you can write very general code. There is some real benefit even if you don't do much more than use an occasional if constexpr (pred) { ... } in your template code.

11.6 References

C++ Networking TS draft
KissNet
Smart Output Iterators - Jonathan Boccara
Smart output iterators become pipes - Jonathan Boccara
C++ Seasoning (video) - Sean Parent - Going Native 2013
string formatting (see answer 15) - stackoverflow