Title: Student Code Critique Competition 30

There are three errors preventing the program from compiling. The first is that < is not a valid operator for an iterator and needs to be replaced with !=. Then it can not be printed to cout; we could print the the address of the data it references, but that's a useless piece of information in this context, so I think it's better to introduce a second variable called n showing the numerical position we've reached in the list. This is only meaningful as a cue for the user.

I've chosen to initialise it outside the loop and increment it in the loop body rather than in the loop statement to emphasise that the loop is iterating through the list and n is supplemental. The final compile error is that we haven't included <cstdlib> so system is undefined. The pause command is not portable anyway, and C++ makes such a meal of waiting for a user to press Enter that I've just deleted that line and left it up to the user to run the program in a shell or IDE that will give them a chance to read the output.

Even though it will now compile the code is still badly bugged and likely to crash. We're derefencing it without initialising it. Not only that, it is not possible to add elements to a list by writing off the end of it. We need to explicitly create a new element by appending to the list with its push_back method.

Here is my version of the code:

#include <iostream>
using std::cout;
using std::endl;
#include <list>
using std::list;

int main() {
  list<double> lst;
  lst.push_back(34);
  lst.push_back(45);
  lst.push_back(87);
  int n = 0;
  for(list<double>::iterator it = lst.begin();
      it != lst.end(); ++it)
    cout << n++ << '\t' << *it << endl;
  return 0;
}

The problem posed is to provide a correct version of the code.

The first question which needs answering is what is the purpose of this code? It looks very much like someone's first experiment with STL collections and iterators - but they don't really understand what they're trying to do.

#include "Josuttis/The C++ Standard
                            Library/Chapter 5"

11   *it = 34;
12   *++it = 45;
13   *++it = 87;

back_insert_iterator<list<double> > ins_it(lst);
*ins_it = 34;
*++ins_it = 45;
*++ins_it = 87;

for(list<double>::iterator it = lst.begin();
    it != lst.end(); ++it)

for(list<double>::const_iterator it
                                = lst.begin();
    it != lst.end(); ++it)

cout << &*it << '\t' << *it << endl;

const double &value = *it;
cout << &value << '\t' << value << endl;

Overall, the intentions of the author are obvious, but it is clear that some misunderstandings over the use of containers and iterators resulted in non-functional code. The use of headers and using statements was fine, and the general structure of the code was also acceptable, bar two lines that required more indentation.

The first major error is with the use of iterators. When assigning values to the list, the iterator is not initialised and so is invalid (cannot be dereferenced). To compound the error, on the second and third assignments, the iterator is incremented in addition to dereferencing. All these mistakes will result in undefined behaviour.

The push_back() method is probably what the student wants. It looks like there is some confusion over how iterators work. The student needs to understand that iterators "point" to items within a container, and that they are not by themselves responsible for inserting values. Likewise, while an iterator can be incremented, this is only useful when there is a next element in the container, and error checking should be done to check that the new iterator is valid. Like pointers, they need to point to a valid location, and only then may they be dereferenced to access the contained value. For insertion, an iterator would typically only be used when inserting in a specific location in the list (used with the insert() methods), or when using an insert iterator, neither of which are applicable in this case.

The for loop iterator is initialised outside the for statement. While valid, it's not necessary and is bad style. Also, the for loop conditional uses it < lst.end() rather than it != lst.end(). Not all iterators implement operator<, but all implement operator== and operator!=. We only need to know if we are at the end of the list. When outputting the list contents, the iterator is output to an ostream, which is not possible (the operator is not implemented). Iterators do not have a (user-visible) index or a meaningful address, and so if the elements should be numbered, a suitable container should be used (e.g. a vector, which allows access by index), or the numbering should be done "by hand". std::endl is used after outputting each element. This adds a newline and flushes the ostream. The flushing is unnecessary, and would have a negative impact on performance when outputting the contents of a larger container. '\n' is adequate here. A more general issue is the use of list<double>. The numbers could more easily be stored in an int, or short int. I would also have used a vector<int> myself, given that the additional features a list provides are not used, and impose a greater overhead than a vector (e.g. memory usage).

Lastly, system("pause") is both system-dependent (non-portable) and mostly useless. I've only come across its use in Windows environments in order to stop the terminal window closing on program exit. This won't work on platforms without a pause command (e.g. UNIX), and is a terminal configuration issue, not something to "fix" in the program code itself. The solution is to configure the terminal window not to close on exit, or to run the program directly from the shell. A version of the code rewritten to take the above into consideration follows:

#include <iostream>
using std::cout;
using std::endl;
#include <vector>
using std::vector;

int main() {
  vector<int> coll;
  vector<int>::iterator pos;
  coll.push_back(34);
  coll.push_back(45);
  coll.push_back(87);

  int n = 0;
  for(pos = coll.begin(); pos != coll.end();
      ++n, ++pos)
    cout << n << '\t' << *pos << '\n';

  return 0;
}

Where to begin, where to begin...

cout << it
list<double>::iterator it;
//...
cout << it //...

cout << &*it //...

system("pause")

it < lst.end()

it != lst.end()

list<double>::iterator  it;
list<double>            lst;

*it = 34;
*++it = 45;
*++it = 87;

lst.push_back(34);
lst.push_back(45);
lst.push_back(87);

typedef list<double> Collection;

#include <iostream>
using std::cout;
using std::endl;
#include <list>
using std::list;
#include <cstdlib>  // for system(char const*)

int main() {
  typedef list<double> Collection;
  Collection lst;
  lst.push_back(34);
  lst.push_back(45);
  lst.push_back(87);

  for(Collection::iterator it = lst.begin();
      it != lst.end(); ++it)
    cout << &*it << '\t' << *it << endl;

  system("pause");
  return 0;
}

static const Collection::value_type 
initialElements[] = {34, 45, 87,};
Collection lst(initialElements, 
initialElements + 3);

Collection lst(initialElements,
        initialElements
          + sizeof initialElements
                 / sizeof initialElements[0]);

#include <cstddef>  // for size_t
template <typename T, size_t N>
inline size_t size(T (&)[N]) { return N; }
template <typename T, size_t N>
inline T* begin(T (&a)[N]) { return a; }
template <typename T, size_t N>
inline T* end(T (&a)[N]) { return a + N; }

Collection lst(begin(initialElements),
               end(initialElements));

#include <iostream>
using std::cout;
using std::endl;
#include <list>
using std::list;
#include <cstdlib>  // for system(char const*)
#include <cstddef>  // for size_t
template <typename T, size_t N>
inline size_t size(T (&)[N]) { return N; }
template <typename T, size_t N>
inline T* begin(T (&a)[N]) { return a; }
template <typename T, size_t N>
inline T* end(T (&a)[N]) { return a + N; }

int main() {
  typedef list<double> Collection;
  static const Collection::value_type initialElements[] = {34, 45, 87,};
  Collection lst(begin(initialElements), end(initialElements));
  for(Collection::iterator it = lst.begin(); it != lst.end(); ++it)
    cout << &*it << '\t' << *it << endl;
  system("pause");
  return 0;
}

This is my first attempt at an SCC solution, so I may learn more than our student. Anyway, here goes:

Trying to compile your code, GCC flags the line with the for loop as an error. Trying to evaluate it < lst.end() is the problem, since the list::iterator is a bidirectional iterator, and so doesn't have the less-than operation defined. It would work if we used a vector container instead of the list, since vector::iterator is a random-access iterator which is more powerful, and has more operations defined for it, including one for less-than. In order to make this loop do what was intended, we can look to a C++ idiom for help: use != as the loop condition check. This operation is defined for all of the five iterator categories, and so will work for iterators over any of the standard container types. The loop still looks unusual, because the idiomatic style is to make use of the initialiser part of the for-loop syntax. The maintenance programmer (which could be you in about 6 months) will see that combination of (; and will needlessly have to wonder if that's a mistake. Make it explicit, and put in the initialization. This has the wonderful side-effect of limiting the scope of the it variable. While we are here, we can notice that you don't modify the value pointed to by the iterator it, and can make that explicit in the code by using a const_iterator instead. So now the loop looks like this:

for(list<double>::const_iterator it = lst.begin();
    it != lst.end(); ++it)
cout << it << '\t' << *it << endl;

which is made much clearer to a C++ programmer through its use of the standard idioms.

Unfortunately, the code still won't compile; this time because there is no output operator (<<) defined for the const_iterator type. I assume that the intention of cout << it was to print the address of the object pointed to by the iterator. This might just happen to work if list iterators were actually pointers, but they are more complicated than that. What I think you want here is &*it, which is the address-of operator applied to the result of dereferencing the iterator, and gives us the memory address of the double that is pointed to by the iterator.

Well, now the code will compile, but running it gives a segmentation fault on my Linux machine, which tells us that we aren't finished yet. This is due to using an iterator to access memory that we don't own, and means that there's some work to be done on understanding how to create our list. In the first line of main(), you define the iterator it but don't give it a value, which leaves it in an unknown state. Trying to dereference that iterator is a big mistake, which causes the segfault. The iterator would have to be made to point to a valid member of a list before we can use it, but there are no valid members of an empty list. We have to find another way of populating the list. My preferred solution would be to use push_back on the list and drop the iterator altogether, which leaves us with the following working code:

#include <iostream>
using std::cout;
using std::endl;
#include <list>
using std::list;

int main() {
  list<double> lst;
  lst.push_back(34);
  lst.push_back(45);
  lst.push_back(87);

  for(list<double>::const_iterator it = lst.begin();
      it != lst.end(); ++it)
    cout << &*it << '\t' << *it << endl;

  system("pause"); // if we must...
  return 0;
}

As an aside, if you really want to use an iterator interface to do the job, you'll have to learn about Insert Iterators. A back_insert_iterator will call push_back for you, and you can then fill the list with the iterator interface, like this:

#include <iterator>
using std::back_insert_iterator;
// other includes, as before

int main() {
  list<double> lst;
  back_insert_iterator<list<double> > it(lst);
  *it = 34;
  *it++ = 45;
  *it++ = 87;
  // ... as before

I'm not sure what this buys you though, except that you get to learn about the added confusion that it++ and ++it are no-ops, and so both the increments in that snippet could be dropped.

First, some comments about style, before we examine correctness. The program starts with:

#include <iostream>
using std::cout;
using std::endl;
#include <list>
using std::list;

Now, in this case, for a source file (not header file), it's generally safe to do:

using namespace std;

instead of the using-declarations. Any name clashes will be flagged by the compiler, and you may save yourself considerable amounts of typing this way. I know this is a hot topic, but anyway. Another alternative is explicit qualification of the names in the code: std::cout << it.

The code has a weird indentation, with some lines indented a couple of places for no apparent reason at all. This gives the code a messy/untidy look, and clarity is important; unclear code is a good breeding ground for bugs. Moving beyond pure layout, there are some other general comments that can be made:

This corrects the problems mentioned in points 1-11.

If you thought I would stop here, you don't know me well enough. ;) Let's step back, and try to see what is the intent of the code. The code should express the intent as clearly as possible. Well, does it? Let's find out. The code inserts few values into a list, and then prints them out. The code above says quite a bit more than this. One thing that is commonly mentioned is to use for_each, rather than for, in such situations. However, using only the standard library, you need to then create another class to do the printing. This isn't necessarily an improvement, as you can't define the class at the point of use. However, as Kevlin Henney shows in his "Omit Needless Code" article, there are several alternatives to printing out the values. One is to use stream iterators:

typedef std::ostream_iterator<double> out;
std::copy(percent_list.begin(),
          percent_list.end(),
          out(std::cout,"\n"));

This makes it rather more succinct. Now, the code focuses on what to do - printing or copying the values to the output stream - rather than how to do it.

If you need more advanced formatting (such as enclosing each value in braces), this won't do, though. Fortunately, there are libraries that allow us to create function objects on the fly, usable with algorithms, such as Boost.Lambda [1]. With it, we may substitute the above with:

std::for_each(percent_list.begin(),
              percent_list.end(),
              std::cout << _1 << "\n");

That takes care of the printing. What about the insertion of values? That looks rather repetitive, doesn't it? Well, Boost can again help us, here, with the Assignment library [2]:

percent_list+=34.0,45.0,87.0;

Here's the last revised version of the code:

#include <iostream>
#include <list>
#include <algorithm>
#include <boost/assign/std/list.hpp>
#include <boost/lambda/lambda.hpp>
using boost::assign::operator+=;
using boost::lambda::_1;

int main() {
  std::list<double> percent_list;
  percent_list+=34.0, 45.0, 87.0;
  std::for_each(percent_list.begin(),
                percent_list.end(),
                std::cout << _1 << "\n");
}

Now, there's no fluff; the code states what it does (at least when you learn the abstractions involved). A further improvement might be if there were overloaded versions of the standard algorithms taking containers, rather than iterators:

std::for_each(percent_list,
              std::cout << _1 << "\n"):

David wasn't kidding when he said the code contains "various mistakes for such a few lines"... This small snippet also turned out to be a good opportunity to demonstrate some software development fundamentals, as well as more advanced techniques.

[1] http://www.boost.org/libs/lambda/doc/index.html

[2] Available in the CVS, but not yet in the current release.