Iterators and Overloading << Operator

Question

I have truncated this post. The initial post is gone in order to facilitate reading. The relevant parts and problems are still there.

---

UPDATE

The error I was asked to post is:

[mehoggan@desktop qsort]$ g++ -o qsort -Wall main.cpp
/tmp/ccuAUzlh.o: In function `Sorters::QuickSorter<float>::test_and_sort(float*, int)':
main.cpp:(.text._ZN7Sorters11QuickSorterIfE13test_and_sortEPfi[Sorters::QuickSorter<float>::test_and_sort(float*, int)]+0x61): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& Sorters::operator<< <float>(std::basic_ostream<char, std::char_traits<char> >&, Sorters::Sorter<float>&)'
collect2: ld returned 1 exit status
[mehoggan@desktop qsort]$ 

and that is using the following code:

#ifndef SORTERS_H_
#define SORTERS_H_
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <ctime>
#include <assert.h>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::ostream_iterator;
using std::istream_iterator;
using std::next_permutation;
using std::back_inserter;
using std::ostream;

namespace Sorters {
    template<typename T>
    class Sorter {
        public:
            Sorter( ) { };
            virtual ~Sorter( ) { };
            virtual void test_and_sort( T *data, int size )=0;
        protected:
            virtual void sort( typename vector<T>::iterator left, typename vector<T>::iterator right )=0;
            vector<T> m_data;
    };

    template<typename T>
    class QuickSorter : public Sorter<T> {
        public:
            QuickSorter( ) { };
            virtual ~QuickSorter( ) { };
            virtual void test_and_sort( T *data, int size );
        private:
            virtual void sort( typename std::vector<T>::iterator left, typename std::vector<T>::iterator right );
            template<typename S> friend ostream& operator<< ( ostream &stream, Sorter<S> &sorter );
    };
}

template<typename T>
void Sorters::QuickSorter<T>::sort( typename vector<T>::iterator left, typename vector<T>::iterator right ) {

}

template<typename T>
void Sorters::QuickSorter<T>::test_and_sort( T *data, int size ) {
    for( int i=0;i<size;i++ ) {
        vector<T> perm( &data[0], &data[i+1] );
        do {
            cout << (*this) << endl;
            copy( perm.begin( ),perm.end( ),back_inserter( m_data ) );
            this->sort( m_data.begin( ), m_data.end( ) );
        } while( next_permutation( perm.begin( ), perm.end( ) ) );
        m_data.clear( );
    }     
}

template<typename S> ostream& operator<< ( ostream &stream, Sorters::Sorter<S> &sorter ) {
    copy( sorter->m_data.begin( ),sorter->m_data.end( ), ostream_iterator<S>( stream," " ) );
    return stream;
}
#endif

---

UPDATE I have written a smaller example so I know my concept works, it just get obfuscated when I use polymorphism and friend functions.

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

class Sample {
    public:
        Sample( ) { };
        Sample( float *data, int size ) {
            copy(&data[0],&data[size],back_inserter( m_data ) );
        };
        ~Sample( ) { };
    private:
        vector<float> m_data;
        friend ostream& operator<< ( ostream &stream, Sample &s ) {
            copy( s.m_data.begin( ), s.m_data.end( ), ostream_iterator<float>( stream, " " ) );  
            return stream;
        }
};

int main( int argc, char *argv[] ) {
    float data[ ] = {1,2,3,4,5};
    Sample s(data,5);
    cout << s;
}

---

SOLUTION

Now to write the actual algorithm. I noticed though if I move m_data up to the parrent class I get compiler errors saying that m_data cannot be found. I guess that just means Insertion Sort, Radix Sort, Stooge Sort, ... will all have there own container.

#ifndef SORTERS_H_
#define SORTERS_H_
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <ctime>
#include <assert.h>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::ostream_iterator;
using std::istream_iterator;
using std::next_permutation;
using std::back_inserter;
using std::ostream;

namespace Sorters {
    template<typename T>
    class Sorter {
        public:
            Sorter( ) { };
            virtual ~Sorter( ) { };
            virtual void test_and_sort( T *data, int size )=0;
        protected:
            virtual void sort( typename vector<T>::iterator left, typename vector<T>::iterator right )=0;
    };

    template<typename T>
    class QuickSorter : public Sorter<T> {
        public:
            QuickSorter( ) { };
            virtual ~QuickSorter( ) { };
            virtual void test_and_sort( T *data, int size );
        private:
            vector<T> m_data;
            virtual void sort( typename std::vector<T>::iterator left, typename std::vector<T>::iterator right );
            friend ostream& operator<< ( ostream &stream, const QuickSorter &sorter ) {
                copy( sorter.m_data.begin( ),sorter.m_data.end( ),ostream_iterator<T>( stream," " ) );
                return stream;
            }
    };
}

template<typename T>
void Sorters::QuickSorter<T>::sort( typename vector<T>::iterator left, typename vector<T>::iterator right ) {

}

template<typename T>
void Sorters::QuickSorter<T>::test_and_sort( T *data, int size ) {
    for( int i=0;i<size;i++ ) {
        vector<T> perm( &data[0], &data[i+1] );
        do {
            copy( perm.begin( ),perm.end( ),back_inserter( m_data ) );
            cout << (*this) << endl;
            this->sort( m_data.begin( ), m_data.end( ) );
            m_data.clear( );
        } while( next_permutation( perm.begin( ), perm.end( ) ) );
    }
}
#endif

Answer 1

You’re defining the operator << overload outside the Sorters namespace. That’s an error: you need to define it in the same namespace as the class (first of all, this is where you’ve declared it using the friend declaration; and second of all, this is where argument-dependent loopup is looking for the overload when you use it later on).

Answer 2

Why the code as shown acts the way it does is explained in the comments: cout << this prints a pointer, which results in an address being output. Your operator << overload expects a reference to an object, not a pointer, so it does not get used. As you said, the solution to this is to use cout << *this.

When I make that change, I ended up with a linker error. Somewhere between the templates, and the namespaces, something got confused, and I'm not clear on what. So I did the easy solution: define the function within the class.

Instead of

template<typename T>
struct QuickSorter {
   template<typename T> friend ostream& operator <<(ostream&, QuickSorter<T>&);
}

template<typename T>
ostream& operator <<(ostream&, QuickSorter<T>&) { }

I did

template<typename T>
struct QuickSorter {  
   friend ostream& operator <<(ostream&, QuickSorter&) { }
};

Now, you don't have to worry about getting template parameters right and whatnot. Templated functions have to be declared inline anyhow, so you might as well just do this and get it over with. Note that you also do not declare operator << as a template itself... you are only interested in giving friendship to the one overload, for the specific T the class happens to be using.

Then, you get informed that the function accesses a member m_data, which does not exist in Sorter<T>. This is straight forward: Sorter<T> does not have that member; QuickSorter<T> does. So change the second parameter to the function to QuickSorter<T>& so that the compiler can find that particular member. This change is also reflected above.

The last thing I would do is make the operator overload accept a const QuickSorter<T>& instead of a non-const one. It does not modify the object in any way, so there is no reason not to.

Answer 3

First thing that you are printing the address by printing this. You need to print as,

cout << *this << endl;

In the comments you mentioned that you get errors. That's because of following line in operator << ():

vector<S> copy = sorter.m_data;  // <--- where is 'm_data' ??

sorter is of type class Sorter<S> and there is no m_data inside it.

To fix this, either move m_data from QuickSorter to Sorter or overload operator << with QuickSorter<S>&.