CppStory Repo

Chapter #11 - Standard Template Libraries (STL)

containers, iterators, algorithms and example code

11.0 Prologue

C++ ships with a rich collection of standard libraries. Scores of well-designed facilities exist, and more arrived with C++20 standardization. This chapter covers the Standard Template Libraries (STL).

11.1 STL Libraries

Fig 1. STL Iterators
The STL provides a large collection of containers, scores of algorithms, and iterators. Iterators bind algorithms to containers. Iterators are a special form of smart pointer. Each container defines iterators that know how to traverse its structure. For contiguous containers like std::vector, traversal is straightforward. For std::unordered_map, the iterator must traverse a hash table, step over empty slots, and walk up bucket lists. Containers define sets of iterators - C::iterator, C::const_iterator, C::reverse_iterator, and more. They also define traits like C::value_type. A value_type is an alias for the element type in a specific container instantiation. For std::vector<std::pair<int, double>>, the value type is std::pair<int, double>.

11.2 Containers

STL containers fall into three groups: sequential, associative, and adaptor. Sequential containers arrange elements in a linear sequence. Sets and maps are associative containers built on binary trees or hash tables. std::stack, std::queue, and std::priority_queue are adaptors built on top of other containers. All remaining 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 containers support value semantics: copy, assignment, and move. Classes with only numeric or STL container members get value semantics through compiler-generated methods. These classes stay small and simple because the STL containers handle most of the work.

11.3 Algorithms

STL algorithms are not engineering or scientific algorithms such as optimization or fast Fourier transforms. They are straightforward operations on collections of data stored in STL containers.

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
In C++17, code using standard algorithms tends to be cluttered with iterators and difficult to compose. C++20 improves this with range technology. The examples below show ways to clean up algorithm code in the meantime.

11.4 Examples

The first example shows standard usage of std::for_each, std::find, and std::copy. With std::copy, we use std::ostream_iterator, std::inserter, and std::back_inserter, which performs 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
The next example develops a Collections construct that, like C++20 std::range, holds starting and ending iterators. It optionally holds a callable applied to each element of the Collection's container. We then wrap std::for_each in a foreach function - just 4 lines of code - that accepts a collection and an operation. The resulting code hides iterator syntax for a more readable interface.
Example: Uses Range-Like Construct
The left panel defines operations ShowOp and SumOp, plus a range-like construct Collection that holds first and last iterators and optionally an operation. The right panel shows that Collections produce a readable syntax: ShowOp<std::string> showCout
foreach(rFriends, showCout) This tells the reader that we are displaying each friend's name on std::cout. The traditional for_each call is far more verbose: std::for_each(vecSt.begin(), vecStr.end(), ShowOp<std::string>()); The meaning is not apparent without reading the code closely. 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
This link describes how the C++20 std::range facility works: C++ Ranges Library - Jonathan Boccara, Fluent C++

11.5 Epilogue

The Standard Template Library (STL) provides containers and algorithms bound together by iterators. Chapter 2 - Data showed that complex data structures snap together easily using existing STL containers. Algorithms, augmented with template metaprogramming, make code more declarative - readable and easy to reason about. The std::range facilities in C++20 deliver much of what we demonstrated using Collections, so you can use the standard libraries directly. Template metaprogramming demands significant mental effort to learn. TMP enables very general code. Even occasional use of if constexpr (pred) { ... } in template code delivers real benefit.

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