Jump to content
  • Advertisement
Sign in to follow this  
Belgium

Need help sorting structs.

This topic is 4051 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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);
}

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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);
}

Share this post


Link to post
Share on other sites
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 it
struct 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.
}

Share this post


Link to post
Share on other sites
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 it
struct 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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!