Sorting MyClass

I have created a class.
A Linked List holds pointers to those classes.

I'd like to sort the entire linked list in alphabetical order based on one of the character arrays in each class.

...I know <list> has a sort method but I believe that I need to Overload an operator for my class (operator >) I think.

Could someone explain this please, I couldn't find anything that wasn't so broad on the net regarding to this topic.

if you don't overload the < operator for the class then you can develop a function to do the desired comparison and pass the function/operator:

list.sort(widgetCompare);

sorts an STL list of widgets using the widgetCompare function (or maybe a widgetCompare function object, I'm not sure)

or you could always write your own sort() function.

writing your own sort function then requires you to create a new list since i need the items stored in the linked list to be in sorted order.

right ?

if you wish the original list to be maintained in unsorted order, then yes, you would need to copy the original list into a second list and sort the second list. If you are going to do that and write your own sort function, then I would consider doing an insertion sort rather than a bubble sort as there is less pointer manipulation. If you don't care what the original sequence of nodes was after completion of the sort, then you can do some sort of a sort (bubble, quick, merge, whatever) on the original list.

My List Declaration :

list<Sstring *> theList; (in a class called Holder)

( Sstring is my own class containing a char * to an array )

-I don't care about the order of the old (unsorted) list.

-The order I need the list to be is alphabetical by the char * in each class.

So I can be able to do :

Code:

  int main (void){

	Holder h;	//contains list

	Sstring a("Axxx");
	Sstring b("Bxxx");
                Sstring c("Cxxx");

	h.addMe(&c);
	h.addMe(&b);
	h.addMe(&a);

	h.dsp_all();

	h.MySort();  // sort funct to be here	

	h.dsp_all();

current output:
Cxxx
Bxxx
Axxx

WANTED OUTPUT
Axxx
Bxxx
Cxxx


So should I overload the < operator so i can say
" theList.sort(); " in the Holder::Mysort();

>So should I overload the < operator

Yes, then you can call std::list::sort(), and don't have to implement you're own algorithm.

You may want to try a different container, as std::sort() rather than std::list::sort() may be quicker in your case, but needs random access iterators. It depends where your bottleneck is; at the insertion point, or when the elements are sorted.

Where should I overload the < operator ?

1. In the Holders class where the list is.
2. In the Sstring class where the char* I'm evaluating is.
3. Outside all classes (tells me i don't have access to the char*)

and

would the signature be :

bool operator < (Sstring l, Sstring r)

If you've got a list of pointers you'll need a global function (or functor) to plug into your list sort otherwise it'll sort by pointer value. This creates a list of pointers to strings, sorts and outputs them -

Code:

#include <iostream>
#include <list>
#include <string>
using namespace std;

class stringsort
{
public:
	bool operator()(string* A,string* B)
	{
		return *A<*B;
	}
};

int main()
{

	list <string*> sl;
	string a ="abc";
	string b ="hij";
	string c ="efg";

	sl.push_back(&a);
	sl.push_back(&b);
	sl.push_back(&c);

	sl.sort(stringsort());

	for(list<string*>::iterator it=sl.begin();it!=sl.end();++it)
		cout << **it;

	return 0;
}

If this sorting functor needs access to private data you can declare it as a friend in the class.

The last resort :

...If someone could do the honors...

Code:

#include <iostream>
#include <string>
#include <list>
using namespace std;

class Sstring{
	private:
		char *toStr;
	public:
		Sstring(char *s){
			toStr=new char[strlen(s)+1];
			strcpy(toStr, s);
		}
		
		~Sstring(){if (toStr) delete [] toStr;}
		
		void dsp(void){cout<<toStr;}

		char* gets(){return toStr;}

		friend bool operator < (const Sstring* s1, const Sstring* s2){
			bool rv= s1->toStr[0] < s2->toStr[0];
			cout<<endl<<"  rv  =  "<<rv<<endl;
		return rv;
		}

		
};


class Holder{
	private:
		list<Sstring *> theList;
	
	public:
		void addMe(Sstring *IN){
			theList.push_front(IN);
		}

		void dsp_all(){
			list<Sstring *>::iterator i = theList.begin();
			cout<<endl<<"--TOP--"<<endl<<endl;
			while(i != theList.end()){
				(*i)->dsp();//toStr;
				cout<<endl;
				i++;
			}
			cout<<endl<<"--END--"<<endl;
		}

		void ListSort(){
			cout<<"Holder::ListSort()"<<endl;

			theList.sort(op);
		}


		bool op(const Sstring* s1, const Sstring* s2){ 
			return *s1 < *s2; 
		} 


};




int main (void){

	Holder h;	

	Sstring a("ANumber One");
	Sstring b("BNumber Two");
	Sstring c("CNumber Three");

	h.addMe(&a);
	h.addMe(&b);
	h.addMe(&c);

	h.dsp_all();

	h.ListSort();	

	h.dsp_all();


return 1;
}

Here -

Code:

#include <iostream>
#include <string>
#include <list>
using namespace std;

class Sstring{
	private:
		char *toStr;
	public:
		Sstring(char *s){
			toStr=new char[strlen(s)+1];
			strcpy(toStr, s);
		}
		
		~Sstring(){if (toStr) delete [] toStr;}
		
		void dsp(void){cout<<toStr;}

		char* gets(){return toStr;}

		friend bool operator<(const Sstring& s1,const Sstring& s2){
			return s1.toStr[0] < s2.toStr[0];

		}

				
};

class s
{
public:
	bool operator()(const Sstring* a, const Sstring* b){ 
			return *a < *b; 
		} 
};

class Holder{
	private:
		list<Sstring *> theList;
	
	public:
		void addMe(Sstring *IN){
			theList.push_front(IN);
		}

		void dsp_all(){
			list<Sstring *>::iterator i = theList.begin();
			cout<<endl<<"--TOP--"<<endl<<endl;
			while(i != theList.end()){
				(*i)->dsp();//toStr;
				cout<<endl;
				i++;
			}
			cout<<endl<<"--END--"<<endl;
		}

		void ListSort(){
			cout<<"Holder::ListSort()"<<endl;

			theList.sort(s());
		}

		


};




int main (void){

	

	Holder h;
	
	Sstring a("ANumber One");
	Sstring b("BNumber Two");
	Sstring c("CNumber Three");

	
	h.addMe(&a);
	h.addMe(&b);
	h.addMe(&c);

	h.dsp_all();

	h.ListSort();	

	h.dsp_all();


	return 0;
}

Compiling...
themain.cpp
C:\TEMP\srt\themain.cpp(60) : error C2664: 'void __thiscall std::list<class Sstring *,class std::allocator<class Sstring *> >::sort(struct std::greater<class Sstring *>)' : cannot convert parameter 1 from 'class s' to 'struct std::greater<class Sstr
ing *>'
No constructor could take the source type, or constructor overload resolution was ambiguous
Error executing cl.exe.

srt.exe - 1 error(s), 0 warning(s)

Here's a workaround for MSVC 6.0. You may want to look into upgrading/changing your compiler if you're planning on using templates -

Code:

#include <iostream>
#include <string>
#include <list>
using namespace std;

class Sstring{
	private:
		char *toStr;
	public:
		Sstring(char *s){
			toStr=new char[strlen(s)+1];
			strcpy(toStr, s);
		}
		
		~Sstring(){if (toStr) delete [] toStr;}
		
		void dsp(void){cout<<toStr;}

		char* gets(){return toStr;}

		friend bool operator<(const Sstring& s1,const Sstring& s2){
			return s1.toStr[0] < s2.toStr[0];

		}

				
};

template <class T>
struct s:public greater<T>
{
    bool operator()(const T* a, const T* b){ 
	    	return *a < *b; 
	           } 
};

class Holder{
	private:
		list<Sstring *> theList;
	
	public:
		void addMe(Sstring *IN){
			theList.push_front(IN);
		}

		void dsp_all(){
			list<Sstring *>::iterator i = theList.begin();
			cout<<endl<<"--TOP--"<<endl<<endl;
			while(i != theList.end()){
				(*i)->dsp();//toStr;
				cout<<endl;
				i++;
			}
			cout<<endl<<"--END--"<<endl;
		}

		void ListSort(){
			cout<<"Holder::ListSort()"<<endl;

			theList.sort(s<Sstring*>());
		}

		


};




int main (void){

	

	Holder h;
	
	Sstring a("ANumber One");
	Sstring b("BNumber Two");
	Sstring c("CNumber Three");

	
	h.addMe(&a);
	h.addMe(&b);
	h.addMe(&c);

	h.dsp_all();

	h.ListSort();	

	h.dsp_all();


	return 0;
}

Excellent.....

I really want to understand how that worked !

What's with creating a seperate class 's' and passing a classname with () to list::sort() ?

and

Now that you've seen the program, could have this been done with simply overloading the < operator and coding theList.sort() without supplying any parameters ?

and

Why shouldn't you use templates with VC++
(or what makes it more difficult) ?

>What's with creating a seperate class 's' and passing a classname with () to list::sort() ?

They're called functors (function objects), which enable the comparison function to be inlined by std::list::sort(), which gives performance advantages (especially when you've got a large number of elements to sort). In a proper STL implementation you can still pass the address of a comparison function, but with an efficiency loss.

>Now that you've seen the program, could have this been done with simply overloading the < operator and coding theList.sort() without supplying any parameters ?

You'd still need to overload the < operator, but you could have used the default functor (thisList.sort()) if the list contained copies of the Sstrings rather than pointers (std::list<String> ). Otherwise all you're comparing is addresses.

>Why shouldn't you use templates with VC++

You can, but a soon as you try to do something that deviates from the norm (eg the above case, and partial template specialisation) you'll run into problems. VC++.NET (or Dev C++(Mingw) is better).

I swear all i touched were the strings in the main
and push_front to push_back. and now it's not sorting

UNCLE !!! alright there, i said it........

Code:

#include <iostream>
#include <string>
#include <list>
using namespace std;

class Sstring{
	private:
		char *toStr;
	public:
		Sstring(char *s){
			toStr=new char[strlen(s)+1];
			strcpy(toStr, s);
		}
		
		~Sstring(){if (toStr) delete [] toStr;}
		
		void dsp(void){cout<<toStr;}

		friend bool operator<(const Sstring& s1,const Sstring& s2){
			return s1.toStr[0] < s2.toStr[0];
		}

				
};

template <class T>
struct s:public greater<T>
{
    bool operator()(const T* a, const T* b){ 
		return *a < *b; 
    } 
};

class Holder{
	private:
		list<Sstring *> theList;
	
	public:
		void addMe(Sstring *IN){
			theList.push_back(IN);
		}

		void dsp_all(){
			list<Sstring *>::iterator i = theList.begin();
			cout<<endl<<"--TOP--"<<endl<<endl;
			while(i != theList.end()){
				(*i)->dsp();//toStr;
				cout<<endl;
				i++;
			}
			cout<<endl<<"--END--"<<endl;
		}

		void ListSort(){
			cout<<"should be sorted";

			theList.sort(s<Sstring*>());
		}

};



int main (void){

	Holder h;
	
	Sstring a("cccc");
	Sstring b("aaaa");
	Sstring c("bbbb");

	h.addMe(&a);
	h.addMe(&b);
	h.addMe(&c);

	h.dsp_all();

	h.ListSort();	

	h.dsp_all();


	return 0;
}