[ previous, contents, next ]

11. Smallest and second-smallest element

Program design approach

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.

Combining binary counter and list pool

We built a machine for doing reduction. We also built a pool for very fast lists. Now we have to combine all that so it produces the final algorithm. From where we are now, it should only take 4-5 lines of code to write min_element_1_2 along with type scaffolding.

Inner loop

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

  1. We will do a while loop and add things to a counter.
  2. We will reduce the counter. The result will have the minimum in the list.

  3. 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.

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

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 lines2:

Before the loop we need to define these objects and types. Let’s construct our counter. Do we know it’s 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 it’s 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 it’s 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 work3. 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 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-sensitive4. 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.

Code


  1. In the lectures Alex goes through several rounds of defining and renaming types. I included this section to illustrate the process. If you are confused refer to the final code at the end of the lesson.
  2. These are the only lines which generate assembly instructions for the CPU to execute. All other lines are just to make the C++ type system work.
  3. Much of the scaffolding can be removed in modern C++. Most of the ugly typename ... definitions could be replaced by auto, which was introduced in C++11. A few of the function objects (such as compare_dereference) may also make more sense as C++ lambdas.

  4. This terminology is specific to compilers and theory of computation. It refers to a classification of formal languages based on their complexity to parse.
[ previous, contents, next ]