Thread: Sorting MyClass

  1. #1
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187

    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.

  2. #2
    Unregistered
    Guest
    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.

  3. #3
    Unregistered
    Guest
    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 ?

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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.

  5. #5
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187

    Please, explain a bit more (great info so far)

    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();

  6. #6
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    >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.

  7. #7
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187
    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)

  8. #8
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    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.

  9. #9
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187

    ...Eternally Confused...

    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;
    }

  10. #10
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    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;
    }

  11. #11
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187

    On Compile (VC++ 6.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)

  12. #12
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    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;
    }

  13. #13
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187
    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) ?

  14. #14
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    >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).

  15. #15
    Unregistered
    Guest
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. Sorting Algorithm Help
    By cjwenigma in forum C++ Programming
    Replies: 8
    Last Post: 11-02-2007, 02:04 PM
  3. vector: sort multiple fields
    By FoodDude in forum C++ Programming
    Replies: 4
    Last Post: 09-28-2005, 11:00 AM
  4. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  5. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM