Thread: Help on std::sort on pair variables

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    2

    Help on std::sort on pair variables

    This works fine, if i declare a pair of <double, int>

    Code:
    std::vector< pair<double,int> >test;
    	test.push_back(pair<double,int>(0.1,3));
    	test.push_back(pair<double,int>(0.3,6));
    	test.push_back(pair<double,int>(0.2,75));
    	sort(test.begin(),test.end());
    However when i used a pair of <double, CvPoint>, where CvPoint is a opencv struct, the compiler complains of
    Code:
    error C2784: 'bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'const CvPoint'
    1>        c:\program files\microsoft visual studio 9.0\vc\include\vector(1320) : see declaration of 'std::operator <'
    Is it possible to use a structure in a vector pair?

    Heres the code:
    Code:
    struct CvPoint{
     int x;
     int y;
    }
    
    std::vector< pair<double,CvPoint> >test;
    	test.push_back(pair<double,CvPoint>(0.1,cvPoint(1,2)));
    	test.push_back(pair<double,CvPoint>(0.3,cvPoint(2,4)));
    	test.push_back(pair<double,CvPoint>(0.2,cvPoint(3,6)));
    	sort(test.begin(),test.end());

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Unless you're using "using std:: pair", don't forget to prepend "std::" to "pair"...

    Also, you'll need an operator< implemented for CvPoint. You'll need it for sort (last edit I said I didn't see why it would be required, but obviously you're SORTING, which needs the operator<, obviously).
    Damn. That took me about 10 edits to get right :P.
    Last edited by EVOEx; 04-27-2010 at 09:34 AM.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    2
    Hi EVOEx,

    Thanks for replying.

    May I how can i implement an operator for CvPoint, and where should i put it?

    I am sorting the paired values on the basis of increasing double values, with the corresponding CvPoint structures.

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    I wouldn't implement an operator in this case. Instead do this;
    Code:
    bool mycompare(const std::pair<double, CvPoint> &x, const std::pair<double, CvPoint> &y)
    {
        // compare x and y, return true if we deem x < y, otherwise false
    }
    
    int main()
    {
            std::vector< pair<double,CvPoint> >test;
    	test.push_back(pair<double,CvPoint>(0.1,cvPoint(1,2)));
    	test.push_back(pair<double,CvPoint>(0.3,cvPoint(2,4)));
    	test.push_back(pair<double,CvPoint>(0.2,cvPoint(3,6)));
    	sort(test.begin(),test.end(), mycompare);
    }
    If you really want to, name "mycompare" as "operator<" but, given that sorting a pair of anything can have multiple possible meanings, better to be specific in your choice of functions.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    I *would* implement the operator<, as it's also useful would you ever want to use those points in things like sets (damned useful!).

    Like this:
    Code:
    bool operator<(const CvPoint &p1, const CvPoint &p2)
    {
      /* Code to compare here. If p1 < p2, return true, otherwise false */
    }
    What you consider to be less doesn't matter, as long as it's a legal operation (eg. the points can legally be sorted). You could use something like: it's less if p1.x is less than p2.x OR if p1.x is equal to p2.x and p1.y is less than p2.y... That should work.

  6. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by EVOEx View Post
    I *would* implement the operator<, as it's also useful would you ever want to use those points in things like sets (damned useful!).
    Since one of the template parameters when creating a set is a comparator (eg a function or functor that is used to compare relative order of two objects) it is not necessary to implement the function as operator<.

    Where I'm coming from is that there is a difference between saying "A is ordered before B" and "A is less than B". With a std::pair<double, CVPoint> the first statement may make sense, but the second may not. Since the STL allows the programmer to express the first concept, no need to make code more cryptic by pretending an operator<() makes sense when it doesn't.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    If you got rid of this silly CvPoint thing, and just used a std:: pair< int, int >, then you'd get it for free. Your data type would then be std:: pair< double, std:: pair< int, int > >.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by brewbuck View Post
    If you got rid of this silly CvPoint thing, and just used a std:: pair< int, int >, then you'd get it for free. Your data type would then be std:: pair< double, std:: pair< int, int > >.
    That's actually a moot point, as the original question concerned how to do it with CvPoint, not the merits of CvPoint versus other approaches.

    In any event, you would only "get it for free" if you don't consider loss of readability or extendability as a cost.

    If - for sake of discussion - the purpose of CvPoint is to represent two-dimensional coordinates, then code using it will be more readily understandable if those coordinates are named x and y rather than first and second. The reader does not have to remember to do a mental mapping "first means x" and "second means y", and does not have to be reminded (eg using a comment in code). Code that is more understandable is easier to get right, and easier (less costly) to maintain.

    Representing the coordinates using an std::pair<> will make it significantly more difficult should the code ever need to be extended to represent three-dimensional coordinates, say (x, y, z), or four-dimensional coordinates, say (x, y, z, t).
    Last edited by grumpy; 04-27-2010 at 09:44 PM.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I don't believe brewbuck necessarily intended to suggest that one should use that apporach, but rather that one simply could. His post is rather useful in that it shows how convenient std::pair can be, and what is easily possible when using it. Of course the downside is that it might push someone into doing something evil like this:
    Code:
    #define x first
    #define y second
    I'd take grumpy's advice.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by iMalc View Post
    I don't believe brewbuck necessarily intended to suggest that one should use that apporach, but rather that one simply could.
    Given that he described the alternative as silly, I did not interpret it that way.
    Quote Originally Posted by iMalc View Post
    His post is rather useful in that it shows how convenient std::pair can be, and what is easily possible when using it.
    I agree.
    Quote Originally Posted by iMalc View Post
    Of course the downside is that it might push someone into doing something evil like this:
    Code:
    #define x first
    #define y second
    I will admit I had more benign cases than that in mind when I wrote my post. Clearly, I need to refresh my memory of Murphy's Law, to reduce such lapses of misplaced optimism about programmer conduct ;)
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by plasma View Post
    Hi EVOEx,

    Thanks for replying.

    May I how can i implement an operator for CvPoint, and where should i put it?

    I am sorting the paired values on the basis of increasing double values, with the corresponding CvPoint structures.
    The problem is that the operator < for std::pair is defined as:
    Code:
    return lhs.first < rhs.first || lhs.second < rhs.second;
    So it will compare both the members in the pair, and not necessarily sort after the first value. Beware.
    Last edited by Elysia; 04-28-2010 at 05:02 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Elysia View Post
    The problem is that the operator < for std:air is defined as:
    Code:
    return lhs.first < rhs.first || lhs.second < rhs.second;
    So it will compare both the members in the pair, and not necessarily sort after the first value. Beware.
    That would contradict how the standard defines operator<, so I would be surprised to find that happen.

    (The standard says it is
    Code:
    lhs.first < rhs.first || (!(rhs.first < lhs.first) && lhs.second < rhs.second);
    so that the second elements are compared only if the first elements compare equal.)

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Elysia View Post
    The problem is that the operator < for std::pair is defined as:
    Code:
    return lhs.first < rhs.first || lhs.second < rhs.second;
    So it will compare both the members in the pair, and not necessarily sort after the first value. Beware.
    I have no idea where that came from. No admissable less-than operator can ever look like that really.

    tabstop shows what it actually looks like in any compiler header files I've ever seen.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Probably too quick a glance at the code, I guess.
    It seems that it's...
    Code:
    	return (_Left.first < _Right.first ||
    		!(_Right.first < _Left.first) && _Left.second < _Right.second);
    ...what Tabstop said.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. basic question about global variables
    By radeberger in forum C++ Programming
    Replies: 0
    Last Post: 04-06-2009, 12:54 AM
  2. Remotely Creating Variables
    By Rajin in forum C++ Programming
    Replies: 1
    Last Post: 04-26-2005, 11:20 PM
  3. Declaring an variable number of variables
    By Decrypt in forum C++ Programming
    Replies: 8
    Last Post: 02-27-2005, 04:46 PM
  4. hwnd and variables in them
    By underthesun in forum Windows Programming
    Replies: 6
    Last Post: 01-16-2005, 06:39 PM
  5. functions to return 2 variables?
    By tim in forum C Programming
    Replies: 5
    Last Post: 02-18-2002, 02:39 PM