11. Smallest and second-smallest element

Write code backward

You all learned that the first thing you do when programming is define abstract things, then do specific things. I am teaching you intentionally the opposite approach. I am not smart enough to write interfaces first. First you write the code. You write the algorithm. Then you figure out what you need for the algorithm. The interface comes out of the use, not from contemplation.

I prefer to write code backward. Then everything just falls out. Delay thinking. Be lazy. For most algorithms you also need objects. So you can design those after. All the best programmers are lazy. If they were not lazy, they would do work with their hands. They invented programming languages to be lazy. Imitate them.

Overview

We will call the function which finds the smallest and second smallest element min_element1_2. Note that I picked this algorithm not because it is of paramount importance for your future work. I pick this algorithm because it allows us to learn how to do decomposition and learn these components like list_pool and binary_counter along the way.

Let me sketch the grand plan of the whole algorithm.

1. We already showed that we want to arrange our comparisons like a tennis tournament, and binary_counter helps us do this. Instead of comparing by left reduction, we compare by balanced reduction.

2. We also want to keep a history for each element of all the other elements which they have beat. This history will be used to determine the second-place guy.

   We will store this history in a list (using list_pool) along with each element in the binary counter. Note that the counter works on generic elements, so it doesn’t need to be modified to know about this history tracking.

From where we are now, it should only take 4-5 lines of code to write min_element_1_2 along with type scaffolding.

Combining binary counter and list pool

Inner loop

To start, let us imagine you have all the materials to build it (we don’t) and discuss the main loop:

1. Do a while loop over a range of elements and add them to a binary_counter.

   Actually we will store iterators pointing to the elements, rather than the elements themselves so we can return all the useful information.

2. Reduce the counter. The result will be the minimum element.

3. The winner will also have a list of other elements it was compared with. Use std::min_element to find the second place element in the list of losers.

4. Take the result of 2 and 3 and combine them in a pair. Return it.

Now let’s start writing it, even though we don’t have all the parts. It’s programming with smoke and mirrors¹.

while (first != last) counter.add(std::make_pair(first++, pool.empty_queue()));
result_type min1_list = counter.reduce();
I min1 = min1_list.first;
I min2 = *std::min_element(iterator(pool, min1_list.second.first), iterator(pool), cmp);
return std::make_pair(min1, min2);

We will have to adjust it, but these are the only instruction generating lines²:

Before the loop we need to define these objects and types. Let’s construct our counter. Do we know its type? No. That’s ok, call it counter_type.

counter_type counter(op, std::make_pair(last, pool.empty_queue()));

We need a counter operation. Do we know its type? No. Do the lazy thing, call it op_type.

op_type op(cmp, pool);

Now define the pool. We do know its type:

list_pool<I, std::size_t> pool;

Notice that we use std::min_element on our list pool. Will that work? Yes, because we added iterators to our list pool. Define our iterator type:

typedef typename list_pool<I, std::size_t>::iterator iterator;

We are almost done. There are bunch of typedef and a bunch of little classes to write, but we are sort of done.

Comparing iterator values

We will be storing list_pool iterators, We don’t want to compare iterators, we want to compare their values. Let’s write a type function which takes any comparison operation on type T, and returns a comparison for iterator<T>.

template <typename Compare>
class compare_dereference
{
private:
  Compare cmp;
public:
  compare_dereference(const Compare& cmp) : cmp(cmp) {}
  template <typename I>
  bool operator() (const I& x, const I& y) const {
    return cmp(*x, *y);
  }
};

So in the main loop replace cmp with cmp_deref and add the following lines:

typedef compare_dereference<Compare> compare_type;
compare_type cmp_deref(cmp);

Reduction operation

We will define a reduction function object to be used in the binary counter to find the min. What it will do is apply a comparison operation between two elements cmp(a, b). When an element wins a comparison, the loser will be added to a list of elements which have lost to a. In other words, it will keep track of the elements which each element has beaten. This list of “losers” associated with each element is stored in a list_pool.

template <typename T, typename N, typename Compare>
class op_min1_2 
{
private:
  Compare cmp;
  list_pool<T, N>* p;
public:
  typedef typename list_pool<T, N>::list_type list_type;
  typedef std::pair<T, std::pair<list_type, list_type> > argument_type;

  op_min1_2(const Compare& cmp, list_pool<T, N>& pool) : cmp(cmp), p(&pool) {}

  argument_type operator()(const argument_type& x, 
                           const argument_type& y) {
    if (!cmp(y.first, x.first)) {
      p->free(y.second);
      return std::make_pair(x.first, p->push_back(x.second, y.first));
    } else {
      p->free(x.second);
      return std::make_pair(y.first, p->push_front(y.second, x.first));
    }
  }
};

When an element wins, we can combine its list of losers with the element it beat, due to transitivity. We want this operation to be stable, so we need to be careful with the order in which the losers are stored. Note that one uses push_back and the other push_front.

Finishing the scaffolding

Now that we have all the parts, we can define the final missing types and the signature:

template <typename I, typename Compare>
// requires I is a ForwardIterator
// and Compare is a StrictWeakOrdering on ValueType(I)
std::pair<I, I> min_element1_2(I first, I last, Compare cmp) {
  if (first == last || successor(first) == last) {
    return std::make_pair(first, last);
  }

  typedef op_min1_2<I, size_t, compare_type> op_type;
  typedef binary_counter<op_type> counter_type;
  typedef typename op_type::argument_type result_type;

  // ...
}

If you put all these components together, and get it to compile it should work³. The fact that you can do that, is to me a miracle. There is quite a lot of complexity going on. This sense of wonder does not disappear.

Exercise: Implement this algorithm in another language. It will help you see language limitations and understand the algorithm better.

Why do we need the typename keyword?

Once upon a time there were templates, there was STL, people were writing code, but there was no typename and everything worked. Of course, clever people (all the clever people reside in the standard committee (joke)) brought up this example:

template <class T>
class foo {
    typedef T::value_type value_type;
};

Obviously what you are trying to do is extract T’s value_type and use it here. Let us try to follow the committees logic. The logic says maybe T::value_type refers to a static variable in T, which it could be of course. But, don’t you know from the context that it’s supposed to be a type? Since they are very well educated, they say, “but that will make our grammar context-sensitive⁴. We need to figure out the meaning of a token without referring to the context in which it appears”.

So they came up with the following rule: If you don’t put typename, the compiler must assume it is a variable, even if it is a type. This is done to maintain the property that you don’t need to know outside context. Of course, the problem here does not really relate to typename. The problem exists because T is not specified. The language has no concepts. For example if we said Container T instead of class T, and had a concept Container, the definition of Container would say that it is required to have an affiliated type value_type. Then the compiler could figure out what we really mean.

What often happens is that instead of solving the real problem, a partial problem is solved. We still do not have concepts. One of the great things about C++ is the language has been evolving for 40 years which is also one of the terrible problems. All its features have been added over time. So, it works with all kinds of quirks.

The advice Bjarne gives right now, is use typename whenever you can, even in the context when it’s not absolutely required.

Code

• min_element1_2.h
• test_min1_2.cpp