The Standard Librarian: Sorting in the Standard Library

Listing 3: Measurements — Comparing direct and indirect sort

#include <utility>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <time.h>

using std::vector;
using std::string;
using std::pair;

template <class Iterator>
struct indirect_lt {
  bool operator()(Iterator x, Iterator y) const 
    { return *x < *y; }
};

struct timer {
  clock_t start;
  timer() { start = clock(); }
  double time() const {
    return double(clock() - start) / CLOCKS_PER_SEC;
  }
};

void
report(vector<pair<string, double> > v,
       std::ostream& os)
{
  typedef vector<pair<string, double> > Vect;
  
  os << std::setw(20) << "sorting method" << "    " 
     << "t (sec)" << std::endl;
  for (Vect::iterator i = v.begin(); i != v.end(); ++i)
    os << std::setw(20) << i->first << "    "
       << i->second << std::endl;
}

pair<string, double> 
do_sort(vector<string> c)
{
  timer t;
  std::sort(c.begin(), c.end());
  return std::make_pair(string("sort"),
                        t.time());
}

pair<string, double> 
do_indirect_sort(vector<std::vector<std::string>
                   ::const_iterator> c)
{
  timer t;
  std::sort(c.begin(), c.end(),
            indirect_lt<std::vector<std::string>
              ::const_iterator>());
  return std::make_pair(string("indirect sort"), 
                        t.time());
}

int main(int argc, const char** argv)
{
  if (argc != 2) {
    std::cerr << "Usage: "
              << argv[0] << " <file>"
              << std::endl;
    return 1;
  }
  
  std::ifstream in(argv[1]);
  if (!in) {
    std::cerr << "Can't open " << argv[1] << std::endl;
    return 1;
  }

  vector<string> v;
  string str;
  while (std::getline(in, str))
    v.push_back(str);

  std::cout << "Sorting a file of "
            << v.size() << " lines."
            << std::endl;

  typedef std::vector<std::string>::const_iterator iter;
  std::vector<iter> iv;
  for (iter i = v.begin(); i != v.end(); ++i)
    iv.push_back(i);

  vector<pair<string, double> > results;
  results.push_back(do_indirect_sort(iv));
  results.push_back(do_sort(v));
  report(results, std::cout);

  return 0;
}