      1  #include <algorithm>
      2  #include <fstream>
      3  #include <iostream>
      4  #include <iterator>
      5  #include <queue>
      6  #include <sstream>
      7  #include <vector>
      8
      9  using namespace std;
     10
     11  /**
     12     Create a temporary file name.
     13  */
     14  string temp_name()
     15  {
     16     static int file_count = 0;
     17     ostringstream name;
     18     name << "temp" << file_count;
     19     file_count++;
     20     return name.str();
     21  }
     22
     23  /**
     24     A generator for strings from standard input
     25  */
     26  class WordGen
     27  {
     28  public:
     29     string operator()();
     30  };
     31
     32  string WordGen::operator()()
     33  {
     34     string in;
     35     if (cin >> in)
     36     {
     37        return in;
     38     }
     39     return "";
     40  }
     41
     42  void phase1(queue<string>& file_names)
     43  {
     44     const int max_words = 10;
     45     WordGen wgen;
     46     while (cin)
     47     {
     48        // Read max_words into vector, sort them, write to temp file
     49        vector<string> a;
     50        generate_n(back_inserter(a), max_words, wgen);
     51        sort(a.begin(), a.end());
     52
     53        vector<string>::iterator p = unique(a.begin(), a.end());
     54        a.erase(p, a.end());
     55
     56        string tname = temp_name();
     57        file_names.push(tname);
     58        ofstream out_file(tname.c_str());
     59        copy(a.begin(), a.end(), ostream_iterator<string>(out_file, "\n"));
     60        out_file.close();
     61     }
     62  }
     63
     64  void phase2(queue<string>& file_names)
     65  {
     66     while (file_names.size() > 1)
     67     {
     68        // Merge two temp files into one
     69        string t1 = file_names.front();
     70        file_names.pop();
     71        string t2 = file_names.front();
     72        file_names.pop();
     73
     74        ifstream f1(t1.c_str());
     75        ifstream f2(t2.c_str());
     76        string tname = temp_name();
     77        ofstream out_file(tname.c_str());
     78
     79        merge(istream_iterator<string>(f1),
     80           istream_iterator<string>(),
     81           istream_iterator<string>(f2),
     82           istream_iterator<string>(),
     83           ostream_iterator<string>(out_file, "\n"));
     84
     85        f1.close();
     86        f2.close();
     87        out_file.close();
     88
     89        // Now remove duplicates from resulting file
     90        ifstream in_file(tname.c_str());
     91        string tname2 = temp_name();
     92        ofstream out_file2(tname2.c_str());
     93
     94        unique_copy(istream_iterator<string>(in_file),
     95           istream_iterator<string>(),
     96           ostream_iterator<string>(out_file2, "\n"));
     97
     98        in_file.close();
     99        out_file2.close();
    100        file_names.push(tname2);
    101     }
    102  }
    103
    104  int main()
    105  {
    106     queue<string> file_names;
    107
    108     phase1(file_names);
    109     phase2(file_names);
    110
    111     string tname = file_names.front();
    112     ifstream in_file(tname.c_str());
    113     copy(istream_iterator<string>(in_file),
    114        istream_iterator<string>(),
    115        ostream_iterator<string>(cout, "\n"));
    116
    117     return 0;
    118  }