external memory sorting

Hi,

I am trying to use an external sort method I found in this book:
http://www.informatik.hs-bremen.de/~brey/stlbe.html

the interface is this:

Code:

---

int main() {
  std::less<long> Comparison;              // descending
  //    std::greater<long> Comparison;            // ascending
    std::istream_iterator<long> suitable_iterator;

    std::cout << externalSorting(
                suitable_iterator,  // type of file
                "random.dat",      // file name
                "\n",              // separator
                Comparison)        // sorting criterion
        << " sorting runs" << std::endl;
}

---

and the externalSorting(...) method is

Code:

---

template<class IstreamIterator, class Compare>
int externalSorting(IstreamIterator& InputIterator,
                    const char *SortFile,
                    const char *Separator,
                    const Compare& comp) {
    typedef typename std::iterator_traits<IstreamIterator>::value_type
            valueType;
    bool sorted = false;

    // arbitrary names for auxiliary files
    const char *TempFile1 = "esort001.tmp",
              *TempFile2 = "esort002.tmp";

    int Run = 0;      // number of sort-merge cycles
    do {
      std::ifstream Inputfile(SortFile);
      SubsequenceIterator<valueType, Compare>
                      FileIterator(Inputfile, comp);


      split(FileIterator, TempFile1, TempFile2, sorted);
      Inputfile.close();

      if(!sorted) {
          // prepare for merging
          std::ifstream Source1(TempFile1);
          std::ifstream Source2(TempFile2);

          SubsequenceIterator<valueType, Compare> I1(Source1, comp);
          SubsequenceIterator<valueType, Compare> I2(Source2, comp);
          SubsequenceIterator<valueType, Compare> End;

          // open SortFile for writing
          std::ofstream Outputfile(SortFile);
          std::ostream_iterator<valueType> Result(Outputfile, Separator);

          mergeSubsequences(I1, End, I2, End, Result, comp);
          ++Run;
      }
    } while(!sorted);
    return Run;
}

---

I want to sort records stored in a text file of the form

Code:

---

class node{
        public:
        long key;
        string values;
};

---

and sort them by key.

but when I create my own comparator function, it does not compile, I am trying to do this

Code:

---

struct less2 : binary_function<node, node, bool> {
  bool operator()(const node& x, const node& y) const { return x.key < y.key; }
};

int main() {

  less2 Comparison;              // descending
 
    std::istream_iterator<node> suitable_iterator;
               
    std::cout << externalSorting(
            suitable_iterator,  // type of file
            "random.dat",      // file name
            "\n",              // separator
            Comparison)        // sorting criterion  <-- gives error, says "instantiated from here
        << " sorting runs" << std::endl;
}

---

Any ideas as how to fix this?

thanks

Can you give the full text of all error messages. "instantiated from here" is only partial text and doesn't help much.

My initial question is whether there is an operator>> for your node class. Does the istream_iterator know how to read in a node?

here it is,


Building file: ../extsort.cpp
Invoking: GCC C++ Compiler
g++ -O0 -g3 -Wall -c -fmessage-length=0 -oextsort.o ../extsort.cpp
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stream_iterator.h: In member function `std::ostream_iterator<_Tp, _CharT, _Traits>& std::ostream_iterator<_Tp, _CharT, _Traits>::operator=(const _Tp&) [with _Tp = node, _CharT = char, _Traits = std::char_traits<char>]':
../extsort.h:102: instantiated from `void split(SubSeqIterator&, const char*, const char*, bool&) [with SubSeqIterator = SubsequenceIterator<node, less2>]'
../extsort.h:178: instantiated from `int externalSorting(IstreamIterator&, const char*, const char*, const Compare&) [with IstreamIterator = std::istream_iterator<node, char, std::char_traits<char>, ptrdiff_t>, Compare = less2]'
../extsort.cpp:64: instantiated from here
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stream_iterator.h:196: error: no match for 'operator<<' in '*((std::ostream_iterator<node, char, std::char_traits<char> >*)this)->std::ostream_iterator<node, char, std::char_traits<char> >::_M_stream << __value'


thanks

I was close. It is saying that there is no operator<< available. Do you have an operator<< that can output a node?

I fixed it, now it works. Here is how it looks now (below). However I still have a small bug.
the structure of my file looks something like this:
23 1 0
43 0 1
56 0 1
...

The fist column is my sorting criteria, and I want to store the rest of the line in the string field "values"; however, it stops as soon as it finds the first whitespace.

any ideas?

Code:

---

class CNode{
        public:
        long key;
        string values;               

  friend istream& operator >>(istream &is, CNode &obj);
  friend ostream& operator <<(ostream &os,const CNode &obj);
   
        struct greater : binary_function<CNode, CNode, bool> {
          bool operator()(const CNode& x, const CNode& y) const { return x.key > y.key; }               
        };
};


               
istream& operator >>(istream &is, CNode &obj){
      is>>obj.key;     
      is>>obj.values;
      //is.ignore(512, '\n');
      return is;
}
ostream& operator <<(ostream &os, const CNode &obj){
      os<<obj.key<<" ";
      os<<obj.values;
      return os;
}




int main() {

 
    std::istream_iterator<CNode> suitable_iterator;
               
    std::cout << externalSorting(
            suitable_iterator,  // type of file
            "random.dat",      // file name
            "\n",              // separator
            CNode::greater())        // sorting criterion 
        << " sorting runs" << std::endl;
}

---

Use getline instead of operator>>. It will read the rest of the line into the string, without stopping at spaces and tabs.

The values string will contain the space that comes between it and the key. I would think that would be ok for you, although you would probably not want to output the extra space in operator<<. If you don't want the space to be at the start of values, then ise ignore() to ignore it before using getline.