Thread: external memory sorting

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    28

    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

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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?

  3. #3
    Registered User
    Join Date
    Jun 2006
    Posts
    28
    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
    Last edited by Salem; 04-18-2007 at 11:43 AM. Reason: format and de-smily

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I was close. It is saying that there is no operator<< available. Do you have an operator<< that can output a node?

  5. #5
    Registered User
    Join Date
    Jun 2006
    Posts
    28
    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;
    }

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Suggestions on this C style code
    By Joelito in forum C Programming
    Replies: 11
    Last Post: 06-07-2007, 03:22 AM
  3. Shared Memory - shmget questions
    By hendler in forum C Programming
    Replies: 1
    Last Post: 11-29-2005, 02:15 AM
  4. external memory programming utilizing SD card format
    By cbraddoss in forum C Programming
    Replies: 2
    Last Post: 08-18-2005, 10:59 AM
  5. debug to release modes
    By DavidP in forum Game Programming
    Replies: 5
    Last Post: 03-20-2003, 03:01 PM