This project has been created as part of the 42 curriculum by baelgadi.

CPP Module 08

Templated containers, iterators, algorithms


On Tamaran, a friend does not hide what they carry.
A container that refuses to let you look inside is but a locked door.

The STL is 3 things that were built to never know one another.
Containers hold, algorithms work, and iterators are the hands that pass one to the other.


Previously…


CPP Module 08:

3 exercises. C++98 standard only.
Compiler: c++ · Flags: -Wall -Wextra -Werror · Must compile with -std=c++98

Exercise 00: Easy find · ex00/ · easyfind.hpp, a function template over any container of int
Exercise 01: Span · ex01/ · Span.hpp + Span.cpp, shortest and longest distance between N numbers
Exercise 02: Mutated abomination · ex02/ · MutantStack.hpp + MutantStack.tpp, a std::stack that can be iterated

Forbidden: using namespace (-42) · friend (-42) · printf · *alloc · free · C++11 · Boost · function bodies in headers (templates excepted)
Required: STL containers and <algorithm> wherever they fit · Orthodox Canonical Form · at least 10,000 numbers in the Span tests · MutantStack output identical to a std::list run

3 strangers working together

For 7 modules the STL was forbidden but here you are now and it is not only allowed, but it is expected.

Listen carefully, because the design is the lesson.
std::find has never heard of std::vector, and std::vector has never heard of std::find:

template <class InputIterator, class T>
InputIterator   find(InputIterator first, InputIterator last, const T& value);

It asks for 2 iterators and nothing else.
Every container hands out iterators so every algorithm works on every container. Nobody had to write find for vector, then for list, then for deque.

Container Memory Iterator What is it good at
std::vector 1 contiguous block Random access Indexing, appending, being sorted
std::list Linked nodes Bidirectional Inserting in the middle without moving anyone
std::deque Chunks of blocks Random access Pushing and popping at both ends
std::stack Whatever it wraps (not a container but a container adaptor) None Nothing but the top

[!NOTE] Random access means it + 5 and it2 - it1 are one instruction.
Bidirectional means only ++ and --, so std::distance on a std::list would have to walk the whole way.


ex00: easyfind

When I search the sky for a friend… I do not ask what the sky is made of.
I only need to know where it begins and where it ends.

template <typename T>
typename T::iterator    easyfind(T& container, int value)
{
    typename T::iterator    it = std::find(container.begin(), container.end(), value);

    if (it == container.end())
        throw std::runtime_error("easyfind value not found");

    return it;
}

The whole search is 1 line, and it is std::find.

The typename in front of T::iterator is not decoration.


Until T is known, the compiler will not be able to tell whether T::iterator is a type or a static member so it assumes the latter.
typename promises it is a type.

Returning an iterator rather than a bool or an index means the caller can use what was found:

    std::vector<int>::iterator  found = easyfind(vec, 30);
    *found = 999;

[!IMPORTANT] There are 2 easyfind: one for T& returning T::iterator, one for const T& returning T::const_iterator.
Without the second one: easyfind(frozen, 999) on a const std::vector<int> does not compile, because begin() on a const container hands out const_iterator.

[!NOTE] Associative containers are excluded by the subject, and for a reason:
A std::map<int, int> holds std::pair<const int, int>, so std::find has nothing to compare against.


ex01: Span, the distance between stars

class Span
{
    //...
    private:
        unsigned int        _n;
        std::vector<int>    _numbers;
};

_n is the promise, _numbers is what was actually given.
A std::vector because the numbers are appended once, read many times, and sorted.
Note that that is exactly what contiguous memory is good at.

void    Span::addNumber(int number)
{
    if (_numbers.size() >= _n)
        throw std::out_of_range("Span is full");
    _numbers.push_back(number);
}

The longest span

The 2 farthest apart are always the smallest and the largest.
No sorting needed:

    return (static_cast<long>
            (*std::max_element(_numbers.begin(), _numbers.end()))
        - static_cast<long>
            (*std::min_element(_numbers.begin(), _numbers.end())));

The shortest span

Before I measure anything, I put everything in order.
Once they are sorted, the 2 closest numbers are always neighbours.

    std::vector<long>   sorted(_numbers.begin(), _numbers.end());
    std::sort(sorted.begin(), sorted.end());

    std::vector<long>   gaps(sorted.size());

    std::adjacent_difference(sorted.begin(), sorted.end(), gaps.begin());

    return (*std::min_element(gaps.begin() + 1, gaps.end()));

With the subject’s example:

Step Values
Added 6 3 17 9 11
std::sort 3 6 9 11 17
std::adjacent_difference 3 3 3 2 6
std::min_element from begin() + 1 2

The answer is 2, between 9 and 11.

[!NOTE] adjacent_difference copies the first element as is (x[i] - 0), then writes x[i] - x[i - 1] for the rest.
So gaps[0] = 3 is not a gap at all. Hence begin() + 1 (ignoring the first).

[!WARNING] int holds -2147483648 to 2147483647. The distance between those 2 is 4294967295 which does not fit.
Subtracting them as int is signed overflow and in practice it prints -1.
Both spans return long and work on a std::vector<long> copy, so INT_MIN and INT_MAX give 4294967295.

Many numbers in a single call

Calling addNumber 100,000 times is not friendship, it is a chore.
So we do what the containers do and take a range:

    template <typename InputIterator>
    void    addNumber(InputIterator first, InputIterator last)
    {
        typename std::iterator_traits<InputIterator>::difference_type   count;

        count = std::distance(first, last);
        if (count < 0)
            throw std::logic_error("Span: invalid range");
        if (_numbers.size() + static_cast<size_t>(count) > _n)
            throw std::out_of_range("Span: not enough space left for this range");
        _numbers.insert(_numbers.end(), first, last);
    }

The size is checked before anything is inserted. A range that does not fit is refused whole and the Span is left exactly as it was.

It accepts iterators from any container, so a std::list<int> or just int[] fill a Span as well as a std::vector<int>.

[!IMPORTANT] This body lives in Span.hpp and it kind of has to.
It’s a member function template, so it has to be visible wherever it’s used and the subject lists only Span.hpp and Span.cpp for this exercise, with no .tpp.
“No function implementation in a header” excepts templates.


ex02: MutantStack

std::stack is a container adaptor, a thin wrapper around a real one that only lets you touch the top.

template <typename T, typename Container = std::deque<T> >
class stack
{
    protected:
        Container   c;
    //...
};

Every push, pop and top is forwarded to c, a std::deque by default.
The deque has iterators. The stack just never hands them out.

template <typename T, typename Container = std::deque<T> >
class MutantStack : public std::stack<T, Container>
{
    public:
        typedef typename Container::iterator                iterator;
        typedef typename Container::const_iterator          const_iterator;
        typedef typename Container::reverse_iterator        reverse_iterator;
        typedef typename Container::const_reverse_iterator  const_reverse_iterator;

        iterator                begin(void);
        iterator                end(void);
        //...
};

c is protected, not private, and that door is left open on purpose.
I did not have to build anything new. The iterators were there all along and I only opened my hands:

template <typename T, typename Container>
typename MutantStack<T, Container>::iterator    MutantStack<T, Container>::begin(void)
{
    return this->c.begin();
}
Relation What it is
std::stack<T, Container> Parent - MutantStack inherits from it The adaptor, push / pop / top
Container Template parameter The type of the underlying container
c Protected member of the parent The object that is actually holding the elements

[!IMPORTANT] Plain c.begin() won’t compile: 'c' was not declared in this scope.
The parent std::stack<T, Container> depends on T and the compiler refuses to look inside a dependent base while it first reads the template.
this->c makes the name depend on T too (the compiler sees that this is a MutantStack<T>*), so the lookup waits until T is known.

[!NOTE] In Span, this-> would be optional. Span is a normal class with nothing dependent above it.

Since MutantStack is a std::stack, the last line of the subject’s test is legal:

    std::stack<int> s(mstack);

The copy only keeps the std::stack part.
The iterators were MutantStack’s, not the data’s.

And because the container is a template parameter, the mutation works on any of them:

    MutantStack<int, std::vector<int> > vstack;

The same as a std::list

The subject asks that the test prints the same thing twice: once with MutantStack, once with std::list and push_back / back / pop_back.
It does do that, because both iterate from the first element pushed to the last one. begin() is the bottom of the stack and rbegin() is the top.

MutantStack std::list
push push_back
top back
pop pop_back
begin() → bottom begin() → first pushed

[!WARNING] std::stack has no virtual destructor.
Deleting a MutantStack through a std::stack* is UB.
MutantStack adds no members, so it never shows, but it is a reason the STL is not usually inherited from.


Instructions

# ──── ex00 ────
# Verify: easyfind works on std::vector, std::list and std::deque
# Verify: a missing value and an empty container don't crash
# Verify: writing through the returned iterator changes the container
cd ex00 && make
./easyfind
valgrind --leak-check=full ./easyfind

# ──── ex01 ────
# Verify: the subject example prints correctly
# Verify: adding to a full Span throws, a span on 0 or 1 numbers throws
# Verify: 100,000 numbers are added in a single call (big.txt, big_sorted.txt)
cd ex01 && make
./span
head -3 big_sorted.txt
valgrind --leak-check=full ./span

# ──── ex02 ────
# Verify: the subject test and the std::list test print the same 7 lines
# Verify: reverse, const iterators and std::find work on a MutantStack
cd ex02 && make
./mutantstack
valgrind --leak-check=full ./mutantstack

Resources


A container that hides its contents is lonely.
Give it iterators, and every algorithm in the STL becomes its friend.

Glorious!