Sorting a list of structs

This is a discussion on Sorting a list of structs within the C++ Programming forums, part of the General Programming Boards category; Hi, after using the search function for quite some time for the question i have i finally got to the ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    30

    Sorting a list of structs

    Hi,

    after using the search function for quite some time for the question i have i finally got to the point to post myself.

    I have a struct defined as:

    Code:
    typedef struct{
      double d; //distance
      int c;  //classtype
    }classifyprobe;
    typedef list<classifyprobe> KNNLIST;

    Now i have that list and want to sort that list by its d, so i can see which classifyprobes have the least d so i can classify it. (Next neighbourhood classification)

    How can i do it?

    Thanks in advance!

    ~Jan

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >How can i do it?
    Write a comparison function and just call the sort member function of the std::list container.
    Code:
    myList.sort(myCompareFunction);
    My best code is written with the delete key.

  3. #3
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571

    Re: Sorting a list of structs

    Originally posted by Jan79
    Hi,

    after using the search function for quite some time for the question i have i finally got to the point to post myself.

    I have a struct defined as:

    Code:
    typedef struct{
      double d; //distance
      int c;  //classtype
    }classifyprobe;
    typedef list<classifyprobe> KNNLIST;

    Now i have that list and want to sort that list by its d, so i can see which classifyprobes have the least d so i can classify it. (Next neighbourhood classification)

    How can i do it?

    Thanks in advance!

    ~Jan
    1) Define your struct like this:

    Code:
    struct classifyprobe{
      double d; //distance
      int c;  //classtype
      bool operator<(const classifyprobe & c2)const{
        return d < c2.d;
      }
    };
    2) Do this:

    KNNLIST.sort();

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    148
    Write a functor (inherit from binary_function)
    Code:
    struct sortClass : public binary_function<classifyprobe,classifyprobe,bool>
    {
    	result_type operator()(const first_argument_type& lhs,const second_argument_type& rhs) const {
    		return lhs.d < rhs.d; 
    	}
    };
    ...
    //Call
    aList.sort(sortClass());
    //or
    aList.sort(not2(sortClass()));

  5. #5
    Registered User
    Join Date
    Oct 2002
    Posts
    30
    i have now this piece of code. I use (try) a compare function for the following struct:

    Code:
    typedef struct{
    	double d; //Distanz
    	int c; //Klassentyp
    }tknnclassify;
    and my compare function is:

    Code:
    bool ccompare(tknnclassify* a, tknnclassify* b)
    {
        return *a.d < *b.d;
    }

    later i just say:

    Code:
    typedef list<tknnclassify> CLASSIFYLIST;
    CLASSIFYLIST cl;
    cl.sort(ccompare);
    while compiling it gives out the following error:
    knnprobe.cc:413: error: request for member `d' in `a', which is of non-class
    type `tknnclassify*'
    knnprobe.cc:413: error: request for member `d' in `b', which is of non-class
    type `tknnclassify*'

    how can i fix it?


    Thanks in advance!

    ~Jan

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    looks like compiler doens't believe a or b are of type tknnclassify *. Instead of this:
    Code:
    typedef struct{
    	double d; //Distanz
    	int c; //Klassentyp
    }tknnclassify;
    I would try this:
    Code:
    struct tknnclassify
    {
       double d; //Distanz
       int c; //Klassentyp
    }
    because I think C++ style structs are less confusing than C style structs. To do this;
    Code:
    bool ccompare(tknnclassify* a, tknnclassify* b)
    {
        return *a.d < *b.d;
    }
    I would call it like this:

    compare(first , second);

    where first and second are both of type tknnclassify * and declared like this:

    tknnclassify * first;

    or this;

    tknnclassify * second = new tknnclassify;

    and each are given a tknnclassify object to point to like this:

    tknnclassify temp(1.23, 45);

    first = &temp;

    before being passed as parameters to compare().

  7. #7
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Originally posted by Jan79
    i have now this piece of code. I use (try) a compare function for the following struct:

    Code:
    typedef struct{
    	double d; //Distanz
    	int c; //Klassentyp
    }tknnclassify;
    and my compare function is:

    Code:
    bool ccompare(tknnclassify* a, tknnclassify* b)
    {
        return *a.d < *b.d;
    }

    later i just say:

    Code:
    typedef list<tknnclassify> CLASSIFYLIST;
    CLASSIFYLIST cl;
    cl.sort(ccompare);
    while compiling it gives out the following error:
    knnprobe.cc:413: error: request for member `d' in `a', which is of non-class
    type `tknnclassify*'
    knnprobe.cc:413: error: request for member `d' in `b', which is of non-class
    type `tknnclassify*'

    how can i fix it?


    Thanks in advance!

    ~Jan
    1) Don't use the C-stye structs, as mentioned.
    2) You are making a list of tknnclassify *objects* but your comparison uses *pointers*; this is no good. Do:

    Code:
    bool ccompare(tknnclassify& a, tknnclassify& b)
    {
        return a.d < b.d;
    }
    You will also need to tell it that you're passing a function pointer, not a functor object. So:

    cl.sort(ptr_fun(ccompare));

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    By the way, std::ptr_fun is in <functional>
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  9. #9
    Registered User
    Join Date
    Oct 2002
    Posts
    30
    okay, i did that.

    now while compiling i get a strange error i dont understand:

    i use the following structs and methods:

    Code:
    typedef struct{
    	double d; //Distanz
    	int c; //Klassentyp
    }tknnclassify;
    
    using namespace std;
    typedef list<tfingertip> FINGERLIST;
    typedef list<tknnclassify> CLASSIFYLIST;
    
    //prototypes
    bool ccompare(tknnclassify, tknnclassify);
    int kclassify(int, int, int);
    
    bool ccompare(tknnclassify& a, tknnclassify& b)
    {
        return a.d < b.d;
    }
    
    int kclassify(int rx, int ry, int k){
    CLASSIFYLIST cl;
    
    double dist;
    int z = 1;
    int f1 = 0;
    int f2 = 0;
    int f3 = 0;
    int f4 = 0;
    int f5 = 0;
    
    
    typedef FINGERLIST::const_iterator fliter;
    	for(fliter i = flist.begin();i != flist.end();++i){
    		dist = computeD(rx, ry, i->x, i->y);
    		tknnclassify tkc = {dist, i->c};
    		cl.push_back(tkc);
    }
    
    cl.sort(ccompare);
    .
    .
    .
    }
    
    //i know this method is dumb progged
    double computeD(int rx, int ry, int listx, int listy){
    double ret;
    double tx;
    double ty;
    double tt;
    double p1;
    double p2;
    
    tx = rx - listx;
    ty = ry - listy;
    p1 = pow(tx, 2);
    p2 = pow(ty, 2);
    tt = p1 + p2;
    ret = sqrt(tt);
    
    return ret;
    
    }
    When i go for compiling then it says:

    /tmp/ccsxkW2X.o(.text+0x1819): In function `kclassify(int, int, int)':
    : undefined reference to `ccompare(tknnclassify, tknnclassify)'
    collect2: ld returned 1 exit status


    Who can help me there?

    Thanks in advance!
    ~Jan

  10. #10
    Registered User
    Join Date
    Oct 2002
    Posts
    30
    got it, had to write as prototype

    bool ccompare(tknnclassify&, tknnclassify&);


    ~Jan

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  3. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 02:27 PM
  4. CAN'T FIGURE IT -- structs on a linked list
    By Unregistered in forum C++ Programming
    Replies: 6
    Last Post: 04-01-2002, 05:22 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21