Title: Student Code Critique Competition 34

First of all, I think I've got to 'fess up that this is the first time - out of three (!) - that I feel satisfied after solving the problem. In the previous times, the problem was more or less trivial, and all we'd got to do was to suggest the programmer how to improve his/her code. This time, we've got a real problem; something which is likely to happen in real programming, and, unfortunately, is not that much uncommon in the commercial world. OK, and now the code, line-by-line:

The first two lines, i.e.

#include <map>
#include <algorithm>

Seem OK. Next we come across

typedef std::multimap<int, int> MyMapType;

(I'm wondering whether the lack of appropriate vertical spacing here is due to lack of enough space in the journal, or is that adjusted so by the programmer. If the latter is the case, add this to the list of drawback of the code.)

This line by itself is OK as well. The programmer has correctly observed the necessity of using typedef's, yet he/she has missed making the job complete. That is, he/she is better to add the following as well:

typedef MyMapType::const_iterator 
        const_iterator;

The following two points about the above line worth mentioning:

First, I've chosen to use MyMapType::const_iterator over MyMapType::iterator as const-correctness implies that according to our usage. This will become clearer as we proceed. (Note that Item#26 of Effective STL does not apply here.)

Second, I've chosen typedefed MyMapType::const_iterator as const_iterator rather than iterator to clarify it for the (potential) code reader that I'm using constant iterators.

I'd like to add the following typedefs according to similar reasons:

typedef MyMapType::value_type value_type;
typedef MyMapType::key_type key_type;

Next:

struct InRange
{
  bool operator () (const MyMapType::
      value_type& value) const
  {
    return (value.second > 5) && 
           (value.second < 10);
  }
};

Although there is no "problem" on retaining this predicate as a function object, it is better to be transformed to its pure function counterpart. (Consult Item#39 for more on the reason.)

Furthermore, those two magic numbers 5 and 10 are asking us to turn them into constants. (See Item#2 of C++ Gotchas for more on magic numbers.) As they apply only to the predicate itself, I'd prefer to make them template parameters. Therefore, here my refined version:

template <int lBound, int uBound>
bool inRange(const value_type& value)
{
  return (value > lBound) && (value < uBound);
}

The comment of

void initMap(MyMapType& map);

Urges me leaving it off, and I'll obey that! Afterwards, there is no special point about the following lines.

int main()
{
  MyMapType myMap;

  initMap(myMap);

until we reach

  MyMapType::iterator lower = 
        myMap.lower_bound(5);

Here is the first place where we should use const_iterator instead of MyMapType::iterator. I say that because we've nowhere tried to manipulate the result of dereferencing of lower.

Furthermore, supposing that this code is going to have enough functionality, 5 turns out to become another magic number. Thus, this is how I refine the above line:

const key_type rangeVal = 5;
const_iterator lower = myMap.lower_bound(rangeVal);

The next line is where the programme goes logically wrong. Hereafter, the programmer has wrongly assumed that he/she has found "an exact" occurrence of 5 unless he's reached to the end of myMap. And that's wrong. That's exactly what has caused him to get astonished by the result of programme execution. I guess the following snippet from the Standard should make it easier to explain what's going on here (row 9 of Table 69):

That is, it does not guarantee that it will return an iterator to an element with the exact key k. Consider the following multi-map for example

Where lower would return <6, …> - in which the key is not 5. Yet it is the first key not less than 5. Accordingly, I change the next line to the following:

  if(lower->first == rangeVal)//if exact match
        found
  {
    const int lBound(5), uBound(10);

    const_iterator iter = 
      std::find(lower, 
                myMap.upper_bound(rangeVal), 
                inRange<lBound, uBound>);

    if(iter != myMap.end())
    {
      //…
    }
    else
    {}
  }
}

A supplementary point about the above programme is that as Scott Meyers explains in Item#45 of Effective STL, if you need to know where the range (potentially) containing what you need is located, you should use std::equal_range(). Considering that, the programme will become:

std::pair<const_iterator, const_iterator> p =
  myMap.equal_range(rangeVal);

//See Item#45 of Effective STL for why this
      works

if(p.first != p.second)//if there is an exact 
      match at all
{
  const_iterator iter = 
    std::find(p.first, p.second,
        inRange<lBound, uBound>);

  if (iter != p.second)//we've got a value
      meeting our criteria
  {
    //…
  }
  else
  {}
//…

This programmer seems to know enough of the basics of STL programming. Yet, he/she lacks deep-enough knowledge of STL. I suggest reading the following books by order:

I suspect that many readers were scared off by this SCC, which reflects people's lack of familiarity with std::multimap. If you are one such reader then I encourage you to explore the range of associative containers in the standard library - in my experience most people always use std::map even where another container might be better. The fundamental problem with the code shown is the test

if (iter != myMap.end ())

to detect failure to find an element in the map. What is wrong with this test? The value of iter on failure is the end of the range not the end of the container. The range ends with upper_bound(5), so this is the value against which iter must be tested to see if a match was found.

In this example the use of multimap was really a bit of a red herring and simply having a good understanding of the use of standard library iterators would have been enough to spot the bug.

A subsidiary problem is the lack of detail in report of the problem. When a failure occurs it would be more helpful to know what the value of the key is (and ideally the complete contents of the container). This could be a good place to start talking with the student about error handling, fault reporting, and designing for testability.

The first solution presented above does fix the bug and moreover covers some other problems with the code. There is even a quotation of the relevant section from the standard to explain what is going wrong. Unfortunately the standard is designed for precision and the technical vocabulary used is not always clear to casual readers!

I do however have a (minor) criticism with the above solution in that I think the first book listed may be too advanced for a student at this stage. I would suggest getting started with the collection classes via a good basic tutorial to using the STL, such as "The C++ Standard Library" by Nicolai Josuttis and progressing to Austern's book later on.

The second solution presented makes it easy for the student - a one line solution to the bug is given. The first remark - that main requires a "return 0" - is one of those things that is true in practice but not in theory… The standard states that main is a special function and that a return statement is not required. One popular compiler does not support that exclusion - so for maximum portability it is probably a good idea to add an explicit return statement.

The editor's choice is: Sayed H. Haeri

Please email <francis@robinton.demon.co.uk> to arrange for your prize.