Algorithms

Most people know how and when to use various STL containers (vector, list, map, etc.). Fewer people, however, make effective use of the algorithms which accompany them, despite algorithms and containers being concurrently designed and completely interoperable. This week we examine some situations where algorithms can improve our code.

---

####Exercise 1 The following code doesn't compile:

  std::list<double> vals(10);
  for(auto i = vals.begin(), e = vals.end(); i < e; ++i)
    *i = std::rand();

The problem is due to the use of operator< rather than operator!=. std::list is a linked list, which means there isn't an O(1) method for determining if one node is before or after another. (This is unlike std::vector, whose elements are stored in memory order.) Rather than allow poor performance with operator<, std::list chooses not to offer it -- requiring the use of operator!= since node equality testing is efficient (and sufficient in many cases).

Even armed with that knowledge, the error messages are none too helpful, and prodigiously long:

2>------ Build started: Project: training, Configuration: Debug Win32 ------
2>  training.cpp
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &)' : could not deduce template argument for 'const std::vector<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\vector(1502) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &)' : could not deduce template argument for 'const std::vector<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\vector(1502) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &)' : could not deduce template argument for 'const std::vector<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\vector(1502) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &)' : could not deduce template argument for 'const std::vector<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\vector(1502) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &)' : could not deduce template argument for 'const std::vector<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\vector(1502) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\list(1588) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\list(1588) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\list(1588) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\list(1588) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\list(1588) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::unique_ptr<_Ty,_Dx> &,const std::unique_ptr<_Ty2,_Dx2> &)' : could not deduce template argument for 'const std::unique_ptr<_Ty,_Dx> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\memory(2582) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::unique_ptr<_Ty,_Dx> &,const std::unique_ptr<_Ty2,_Dx2> &)' : could not deduce template argument for 'const std::unique_ptr<_Ty,_Dx> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\memory(2582) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::unique_ptr<_Ty,_Dx> &,const std::unique_ptr<_Ty2,_Dx2> &)' : could not deduce template argument for 'const std::unique_ptr<_Ty,_Dx> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\memory(2582) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::unique_ptr<_Ty,_Dx> &,const std::unique_ptr<_Ty2,_Dx2> &)' : could not deduce template argument for 'const std::unique_ptr<_Ty,_Dx> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\memory(2582) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::unique_ptr<_Ty,_Dx> &,const std::unique_ptr<_Ty2,_Dx2> &)' : could not deduce template argument for 'const std::unique_ptr<_Ty,_Dx> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\memory(2582) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1368) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1368) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1368) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1368) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1368) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1191) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1191) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1191) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1191) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xutility(1191) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\utility(318) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\utility(318) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\utility(318) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\utility(318) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::_List_iterator<_Mylist>'
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]
2>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\utility(318) : see declaration of 'std::operator <'
2>C:\cygwin\home\ncrookston\dev\training\training.cpp(18): error C2676: binary '<' : 'std::_List_iterator<_Mylist>' does not define this operator or a conversion to a type acceptable to the predefined operator
2>          with
2>          [
2>              _Mylist=std::_List_val<double,std::allocator<double>>
2>          ]

The compiler doesn't say, "You should have used operator!= there." It doesn't even directly say "No operator< defined for std::list<T>::iterator." Instead, it finds all operator< which could possibly be called given the current scope and the arguments, attempts to convert the arguments (list iterators) to the operands of each operator<, and reports the result -- lots of failed attempts. Such inscrutable error messages are a very real problem with C++, and work to remedy the fundamental cause is ongoing.

Other minor inefficiencies in the code are repeatedly calling vals.end() and using post-increment (i++) rather than pre-increment (++i). The corrected for loop:

  std::list<double> vals(10);
  for(auto i = vals.begin(), e = vals.end(); i != e; ++i)
    *i = std::rand();

---

####Exercise 2: We can avoid those error messages and inefficiencies by using standard algorithms. Here's an example of the previous loop written with std::for_each:

std::for_each(vals.begin(), vals.end(), [](double& rD) { rD = std::rand(); });

This is just as efficient as (the second version of) the previous for loop.

---

####Exercise 3: Replacing for with for_each isn't actually a huge win -- yes, it avoids some inefficiencies, but it's still pretty verbose, especially with the lambda. The big wins of algorithms involve correctness for some of the trickier algorithms, and documenting intent. A for loop doesn't say much about when iteration might stop, or if elements might be changed, or where they might be moved -- you need to examine the loop body for that. Conversely, standard algorithms clearly indicates what the intent of iteration is -- e.g., std::find_if doesn't modify (or move) the elements and will stop once it's found an element which satisfies the predicate.

---

#####Exercise 3.1 (trick question): Before:

for(auto i = ints.begin(), e = ints.end(); i != e; ++i)
  *i = std::rand();

After:

std::generate(ints.begin(), ints.end(), std::rand);

---

#####Exercise 3.2: Before:

  std::vector<int>::iterator center = ints.begin();
  for(auto end = ints.end(); center != end;)
  {
    if(*center < val)
      ++center;
    else
      std::swap(*center, *--end);
  }

After:

  auto center = std::partition(ints.begin(), ints.end(),
    [val](int i) { return i < val; });

---

#####Exercise 3.3: Before:

  int maxInt = ints.front();
  for(auto i = ints.begin(), end = ints.end(); i != end; ++i)
    maxInt = std::max(*i, maxInt)

After:

int maxInt = *std::max_element(ints.begin(), ints.end());

---

#####Exercise 3.4: Before:

  std::vector<int>::iterator match = ints.end();
  for(auto i = ints.begin(); i != match; ++i)
  {
    if(*i > 42)
    {
      match = i;
      break;
    }
  }

After:

  auto match = std::find_if(ints.begin(), ints.end(),
      [](int i) { return i > 42; })

---

#####Exercise 3.5: Before:

  auto newEnd = ints.end();
  for(auto i = ints.begin(); i != newEnd;)
  {
    if(*i > RAND_MAX / 2)
      std::swap(*i, *--newEnd);
    else ++i;
  }

After:

  auto newEnd = std::remove_if(ints.begin(), ints.end(),
      [](int i) { return i > RAND_MAX / 2; });

---

Exercise 3.6

Before:

auto mid = ints.begin() + ints.size() / 2;
auto j = mid;
for(auto i = ints.begin(), end = ints.end(); i != mid && j != end; ++i, ++j)
  std::swap(*i, *j);
//Happens when ints has an odd number of elements:
if(j != ints.end())
{
  int prevInt = ints.back();
  while(mid != ints.end())
    std::swap(*mid++, prevInt);
}

After:

std::rotate(ints.begin(), ints.begin() + ints.size() / 2, ints.end());

####Note: The standard template library (STL) was designed to be both efficient and reusable by using an iterator abstraction [^1]. While I won't explore the different types and behaviors of different iterators, it is important to understand that by making algorithms operate only on iterators, it is possible to write a particular algorithm once, and reuse it for any container that models an iterator interface.

An often proposed abstraction to replace iterators is that of a range. While there are open questions on the efficiency of range-based versus iterator-based algorithms, in many cases using ranges leads to more readable code. As an example, you could use Boost.Range to remove all the calls to begin and end without sacrificing generality or performance. You could also use Boost.Phoenix to simplify writing your predicates (though misused phoenix can cause a sometimes baffling amount of error messages). Combining the two would allow you to write the following:

using boost::phoenix::arg_names::arg1;
boost::generate(ints, std::rand);
auto center = boost::partition(ints, arg1 < val);
int maxInt = *boost::max_element(ints);
auto match = boost::find_if(ints, arg1 > 42);
auto newEnd = boost::remove_if(ints, arg1 > RAND_MAX / 2);
boost::rotate(ints, ints.begin() + ints.size() / 2);

• [^1] See http://en.wikipedia.org/wiki/Standard_Template_Library for a good overview of the design. The exercises for this week are based on Items 6 & 7 from Exceptional C++, Effective STL items 32 & 37, and information from a Concepts presentation given at Google by Doug Gregor.

Resources:

• I thought Sean Parent's example at Going Native 2013 was incredibly cool.