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  }