The design of the STL

Published April 18, 2017 - 7 Comments

As a logical part of the STL learning resource, here is how the STL has been designed, and how you can design your components to make them benefit from the power of the STL.

The design of the STL has been driven by the intention of separating algorithms from data structures.

Algorithms include:

those in the header <algorithm>,
those we write when our need cannot be solved by a standard algorithm.

Data include:

standard STL containers such as std::map and std::vector,
C arrays,
user-defined collections,
any subpart of the above.

Data can even be drawn from a stream as we see in How to split a string in C++.

The intention to separate algorithms from data structures has been accomplished with an interface: iterators.

In order to benefit from all the advantages offered by the large variety of algorithms, data has to present an Iterator interface.

Here we show how to do this for different kinds of data.

STL containers

Iterators can be obtained via:

begin(), end()
rbegin(), rend() for reverse order iterators,
cbegin(), cend() (or simply begin() and end() on const containers) for const iterators,
crbegin(), crend()(or simply rbegin() and rend() on const containers) for const reverse order iterators.

C arrays

For C arrays, pointers play the role of iterators.

int myInts[100];

std::for_each(myInts, myInts + 100, doSomething);

Even if strictly speaking, myInts is not a pointer but an array, it still gives access to the first element of the array, while myInts + 100 points to the “one-after-the-end” address, which follows the begin-end semantics.

So C arrays can be used with algorithms, which can be of great help in legacy code.

Note that a new uniform syntax has been introduced since C++11, with std::begin (and std::end) free functions (and not class methods). They can be used uniformly on any type showing a begin (resp. end) method that can be called with no argument, and they can also be used on C arrays.
The following code gives an example of this uniformity:

int myInts[100];
std::vector<int> vec(100, 0); // vector of size 100 initialized with zeros

std::for_each(std::begin(vec), std::end(vec), doSomething);
std::for_each(std::begin(myInts), std::end(myInts), doSomething);

This makes C arrays easier to use, and is quite convenient for generic code.

Note that the std namespace has to be written explicitly for the C array, because it cannot use ADL, but could be omitted on the vector. More on ADL on in a later post.

User-defined collections

Sometimes we write our own collection that reflect domain needs. Let’s take the example of the user-defined FlowCollection class, that represents a collection of financial flows. Given what we saw above, it needs to publish iterators in order to benefit for algorithms. How do we do this?

Typedef a standard collection

Every time you want to write a collection, ask yourself if a standard one won’t do. This would be as much code that you don’t write. In quite a few cases a standard collection suffices, and you can put a domain name on it with a typedef. For exemple for our collection of flows:

using FlowCollection = std::vector<Flow>;

This way you get all the iterators plus all the functionalities of std::vector for free, while having a type with a domain name.

Recycle the standard iterators

If a domain functionality is really necessary for the collection, or if you only want a subpart of what a standard container offers, you may have to define a class that wraps a standard container. In this case, iterators can be implemented with the standard container’s iterators:

// INTERFACE

class FlowCollection
{
public:
    // ...domain interface...

    // iterators to allow data access
    using const_iterator = std::vector<Flow>::const_iterator;
    const_iterator begin() const;
    const_iterator end() const;

    // iterators to allow data modification
    using iterator = std::vector<Flow>::iterator;
    iterator begin();
    iterator end();

    // other iterators...

private:
    std::vector<Flow> m_flows;
    // ...domain data...
};


// IMPLEMENTATION

FlowCollection::iterator FlowCollection::begin()
{
    return m_flows.begin();
}

Implement your own iterators

If your collection has such a degree of complexity that the two previous techniques won’t do, you may have to implement your own iterators. This is more complex to do and outside the scope of this post, and the occasions for such a need should be very rare.

This is where the STL stands in the C++ of today (<= C++17). To have a glimpse of how the STL is shaping for the future (and to see how you can start using it right now), hop over to ranges.

Don't want to miss out ? Follow:
Share this post!

About Jonathan Boccara