Need help sorting structs.

Started by
5 comments, last by Belgium 16 years, 10 months ago
Hi, I am receiving an error when I try to use sort() from stl algorithms on a struct. Below is code which duplicates the problem;


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

struct Tally
{
    Tally(int count, std::string name, int whatever)
        : count( count ),
          name( name ),
          whatever( whatever )
        {}

    int         count;
    std::string name;
    int         whatever;

    bool operator< (Tally& tally)
    {
        return (this->count < tally.count);
    }

    bool operator> (Tally& tally)
    {
        return (this->count > tally.count);
    }

};

int main()
{
    std::vector<Tally> vTally;
    vTally.push_back( Tally(42, "Art",    16));
    vTally.push_back( Tally(13, "Marv",    3));
    vTally.push_back( Tally(66, "Trish", 103)); 

    // Verify my overloaded operators work correctly.
    if ( vTally.at(0) < vTally.at(1) ) std::cout << "LessThan" << std::endl;
    else if ( vTally.at(0) > vTally.at(1) ) std::cout << "GreaterThan" << std::endl;

    // Attempt to use sort().  This is where the error occurs.
    sort( vTally.begin(), vTally.end() );  

    system("pause");
}



The compile log states it can find no match for operator<. It notes the one I built as a candidate. I can't figure out how it wants operator< to be constructed. I've tried building one which takes Tally* and one which takes a copy of Tally but they received the same error. I also tried one which receives two arguments but the compiler stated it could receive exactly one argument for operator<. Dev-C++ brings up stl_algo.h when it errors out. I've attempted to look at what it wants but it's Greek to me. I have verified that my overloaded operators work. They just don't seem to work with sort(). I'd appreciate any pointers. Thanks. Compiler: Default compiler Executing g++.exe... g++.exe "C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.cpp" -o "C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.exe" -Wall -Wformat -Werror -s -I"C:\Main\Tools\Dev-Cpp\lib\gcc\mingw32\3.4.2\include" -I"C:\Main\Tools\Dev-Cpp\include\c++\3.4.2\backward" -I"C:\Main\Tools\Dev-Cpp\include\c++\3.4.2\mingw32" -I"C:\Main\Tools\Dev-Cpp\include\c++\3.4.2" -I"C:\Main\Tools\Dev-Cpp\include" -L"C:\Main\Tools\Dev-Cpp\lib" C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h: In function `const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&) [with _Tp = Tally]': C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h:2484: instantiated from `void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Tally*, std::vector<Tally, std::allocator<Tally> > >, _Size = int]' C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h:2555: instantiated from `void std::sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Tally*, std::vector<Tally, std::allocator<Tally> > >]' C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.cpp:39: instantiated from here C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h:90: error: no match for 'operator<' in '__a < __b' C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.cpp:18: note: candidates are: bool Tally::operator<(Tally&) C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h:91: error: no match for 'operator<' in '__b < __c' C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.cpp:18: note: candidates are: bool Tally::operator<(Tally&) C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h:93: error: no match for 'operator<' in '__a < __c' C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.cpp:18: note: candidates are: bool Tally::operator<(Tally&) C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h:97: error: no match for 'operator<' in '__a < __c' C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.cpp:18: note: candidates are: bool Tally::operator<(Tally&) C:/Main/Tools/Dev-Cpp/include/c++/3.4.2/bits/stl_algo.h:99: error: no match for 'operator<' in '__b < __c' C:\Main\Tools\Dev-Cpp\MyStuff\Tests\sort.cpp:18: note: candidates are: bool Tally::operator<(Tally&) Execution terminated
Advertisement
sorry confused on the question before when I was trying to help, anyhow I noticed you were from cary, nc. same here originally.

I can't seem to reproduce the problem in visual studio 2003 with your code just copied and pasted. Everything compiles and at least seems to run fine.
I'm not sure (I've never worked with g++), but I think that the only thing that is wrong with the code in the OP is that operators take the arguments as non-const references and that the operators them selfs are not const members...

In other words, you only need to add four "const" in that code and it should work!
    bool operator< (Tally const& tally) const    {        return (this->count < tally.count);    }    bool operator> (Tally const& tally) const    {        return (this->count > tally.count);    }
Thanks, vtchill and Paulius! Both responses worked. A bit frustrating as I was somewhat close to coming up with the answer but couldn't get there on my own. This also has the bonus of fixing a very similar problem I was having inserting a struct into a set.

vtchill, your initial response, which had me creating a two argument overloaded operator outside of the struct, worked too. I quickly tested it and left for lunch a happy person. You've since deleted it. Was there a subtle problem with it? I'm not originally from Cary. I'm a Michigan-Yankee so that's why I was put in CARY when I moved for the job seven years ago.

Quote:Original post by Belgium
Thanks, vtchill and Paulius! Both responses worked. A bit frustrating as I was somewhat close to coming up with the answer but couldn't get there on my own. This also has the bonus of fixing a very similar problem I was having inserting a struct into a set.

vtchill, your initial response, which had me creating a two argument overloaded operator outside of the struct, worked too. I quickly tested it and left for lunch a happy person. You've since deleted it. Was there a subtle problem with it? I'm not originally from Cary. I'm a Michigan-Yankee so that's why I was put in CARY when I moved for the job seven years ago.


Only reason I deleted it was because initially when I first read your problem I immediately thought that making it a free function would fix it and I see now that it did. However, I only tried your original code after I posted my fix and I saw that it too was not giving me any complaints, so instead of posting my fix I simply changed it to say that I could not recreate your problem. Here is the code anyway again in case you need to it.

bool operator< (const Tally& rhs, const Tally& lhs){	return (rhs.count < lhs.count);}bool operator> (const Tally& rhs, const Tally& lhs){	return (rhs.count > lhs.count);}
Note that having an operator> is redundant. It is usual to define operator< and operator== instead; these two are sufficient to make up all six comparison operations (<, <=, ==, !=, >= and >).

Although this leaves you with a bit of a problem, because to get operators that work consistently for sorting, you'd want operator== to only consider the 'count', but Tallys with different names are unequal regardless of their count. As it happens, std::sort doesn't need to compare things for equality, but more broadly speaking we have a slight semantic issue here: we're saying that the count is the only thing that matters when comparing the objects, and that may not be true in all contexts.

The problem is that there are many ways we might want to compare the objects, but only one "built-in" set of operators.

The usual way to get around this is to define only built-in-to-the-class operators (that includes free functions that operate on two instances!) that are "natural" (here that's only operator==), and handle artificial comparisons for sorting (etc.) by writing comparison functors:

struct Tally {// ...    bool operator== (const Tally& t) const {        return count == t.count && name == t.name && whatever == t.whatever;    }};// define a structure that is "callable", and instance itstruct TallyCountLt {    bool operator()(const Tally& a, const Tally& b) {        return a.count < b.count;    }} tallyCountLt;// Most code I've seen makes temporary instances of the structure whereever// they are needed. The idea is that each instance of the struct can have its// own state. Here, there is no state, so I just reuse an instance.// But because there is no state, we could also just use a function like this:// bool tallyCountLt(const Tally& a, const Tally& b) {//     return a.count < b.count;// }// Doing it that way, we call std::sort() below in exactly the same way, just // that 'tallyCountLt' becomes a function pointer rather than an instance name.int main() {    // ...    // can't use < or > here, because they don't make sense    // but we could invoke the comparator if needed:    isLess = tallyCountLt(aTally, anotherTally);    // We pass the comparator as the optional 3rd argument to std::sort:    sort(tallies.begin(), tallies.end(), tallyCountLt);      // Don't artificially pause your programs at the end, please.}
Quote:Original post by Zahlman
...
Although this leaves you with a bit of a problem, because to get operators that work consistently for sorting, you'd want operator== to only consider the 'count', but Tallys with different names are unequal regardless of their count. As it happens, std::sort doesn't need to compare things for equality, but more broadly speaking we have a slight semantic issue here: we're saying that the count is the only thing that matters when comparing the objects, and that may not be true in all contexts.


I think I understand what you're getting at. In the source I originally had problems with, I compared several elements of the struct for equality or being less than / greater than. Below is a snippet;

struct Tally{    Tally(std::string location,          EType type,          int outs,          EFldPos fielder,          EBag r0Dest, std::string r0Play,          EBag r1Dest, std::string r1Play,          EBag r2Dest, std::string r2Play,          EBag r3Dest, std::string r3Play )            : location( location ),     // Location of batted ball.              type( type ),             // Type of batted ball.              count ( 1 ),              // Number of times this event has occured.              outsMade( outs ),         // Number of outs made in event.                 fieldedBy( fielder ),     // Player fielding batted ball.              r0Destination( r0Dest ),  // Destination of batter                 r0Play( r0Play ),         // play on batter.              r1Destination( r1Dest ),              r1Play( r1Play ),              r2Destination( r2Dest ),              r2Play( r2Play ),              r3Destination( r3Dest ),              r3Play( r3Play )          {}    bool operator== (Tally& tally)    {        // count is not compared for equality.  If the following is true        // then it will be incremented to indicate the number of times this        // exact set of data has been noted.        if ( ( this->location      == tally.location )      &&             ( this->type          == tally.type )          &&             ( this->outsMade      == tally.outsMade )      &&             ( this->r0Destination == tally.r0Destination ) &&             ( this->r0Play        == tally.r0Play )        &&             ( this->r1Destination == tally.r1Destination ) &&             ( this->r1Play        == tally.r1Play )        &&             ( this->r2Destination == tally.r2Destination ) &&             ( this->r2Play        == tally.r2Play )        &&             ( this->r3Destination == tally.r3Destination ) &&             ( this->r3Play        == tally.r3Play ) )           {            ++this->count;            return true;        }        return false;    }    bool operator< (const Tally& tally) const    {        if ( this->location < tally.location ) return true;        if ( this->location > tally.location ) return false;        if ( this->type < tally.type ) return true;        if ( this->type > tally.type ) return false;        if ( this->outsMade < tally.outsMade ) return true;        if ( this->outsMade > tally.outsMade ) return false;        return ( this->fieldedBy < tally.outsMade );    }...};


This is used to sort information regarding events in baseball games for research I'm doing. This works well for what I need specifically.

// ** source by Zahlman **// define a structure that is "callable", and instance itstruct TallyCountLt {    bool operator()(const Tally& a, const Tally& b) {        return a.count < b.count;    }} tallyCountLt;


I thought the bit above was very interesting. It certainly opened my eyes up to some possibilities. Do you suggest that if I should find a need to compare Tallys in a different manner, which I undoubtedly will, I should make callable structures for each unique compare method?

Regardless, thank you for your comments and the above snippet. It's given me a new view on things.

This topic is closed to new replies.

Advertisement