This project has been created as part of the 42 curriculum by baelgadi.
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.
|
CPP Module 08:
3 exercises. C++98 standard only. Compiler: c++ · Flags: -Wall -Wextra -Werror · Must compile with -std=c++98Exercise 00: Easy find · ex00/ · easyfind.hpp, a function template over any container of intExercise 01: Span · ex01/ · Span.hpp + Span.cpp, shortest and longest distance between N numbersExercise 02: Mutated abomination · ex02/ · MutantStack.hpp + MutantStack.tpp, a std::stack that can be iteratedForbidden: 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 |
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 + 5andit2 - it1are one instruction.
Bidirectional means only++and--, sostd::distanceon astd::listwould have to walk the whole way.
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.
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 forT&returningT::iterator, one forconst T&returningT::const_iterator.
Without the second one:easyfind(frozen, 999)on aconst std::vector<int>does not compile, becausebegin()on a const container hands outconst_iterator.
[!NOTE] Associative containers are excluded by the subject, and for a reason:
Astd::map<int, int>holdsstd::pair<const int, int>, sostd::findhas nothing to compare against.
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 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())));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_differencecopies the first element as is (x[i] - 0), then writesx[i] - x[i - 1]for the rest.
Sogaps[0] = 3is not a gap at all. Hencebegin() + 1(ignoring the first).
[!WARNING]
intholds-2147483648to2147483647. The distance between those 2 is4294967295which does not fit.
Subtracting them asintis signed overflow and in practice it prints-1.
Both spans returnlongand work on astd::vector<long>copy, soINT_MINandINT_MAXgive4294967295.
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.hppand 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 onlySpan.hppandSpan.cppfor this exercise, with no.tpp.
“No function implementation in a header” excepts templates.
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 parentstd::stack<T, Container>depends onTand the compiler refuses to look inside a dependent base while it first reads the template.
this->cmakes the name depend onTtoo (the compiler sees thatthisis aMutantStack<T>*), so the lookup waits untilTis known.
[!NOTE] In
Span,this->would be optional.Spanis 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;std::listThe 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::stackhas no virtual destructor.
Deleting aMutantStackthrough astd::stack*is UB.
MutantStack adds no members, so it never shows, but it is a reason the STL is not usually inherited from.
# ──── 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 ./mutantstackstd::findstd::adjacent_differencestd::stackA container that hides its contents is lonely.
Give it iterators, and every algorithm in the STL becomes its friend.
Glorious!