Yet Another std::set question
Author
Hey again,
I've almost got my A* code working, but as this really isn't a matter of pathfinding, I'll ask my question here. I have a std::set in which I'm comparing an integer value in order to sort the set. However, there is a very good chance that two elements will have the same value, and because of this, these values aren't added to the set. Is there a way to sort the set by one variable and use a different variable for checking if the value is already in the set?
If so, help is greatly appreciated.
If not, what would you recommend I use instead of the set?
Thanks,
Jeff
I'm not exactly sure I follow. If you want to be able to store the same integer multiple times, use a std::multiset:
If you have a structure which needs to be sorted by an integer, without duplicates, but with some structures using the same integer, then the solution is to also sort based on the other data. For example:
The way to allow for this is to make sorting work also on b, even though you don't consider it important. Our new operator would be:
std::multiset< int > ms;ms.insert( 1 );ms.insert( 2 );ms.insert( 2 );ms.insert( 3 );std::copy( ms.begin() , ms.end() , std::ostream_iterator< int >( std::cout , " " ) ); //prints "1 2 2 3 "If you have a structure which needs to be sorted by an integer, without duplicates, but with some structures using the same integer, then the solution is to also sort based on the other data. For example:
//Original structure:struct foo { int a; int b; foo( int a , int b ) : a( a ) , b( b ) { } friend bool operator<( const foo & lhs , const foo & rhs ) { return lhs.a < rhs.a; //b isn't important to our sorting};std::set< foo > stuff;stuff.insert( foo( 1 , 4 ) );stuff.insert( foo( 1 , 4 ) ); //you don't want this to add a second entrystuff.insert( foo( 1 , 5 ) ); //but you do want this one to.The way to allow for this is to make sorting work also on b, even though you don't consider it important. Our new operator would be:
friend bool operator<( const foo & lhs , const foo & rhs ) { if ( lhs.a != rhs.a ) return lhs.a < rhs.a; //sort first by a if ( lhs.b != rhs.b ) return lhs.b < rhs.b; //then (if lhs.a == rhs.a) sort by b return false; //lhs == rhs, so return false}
From what I understand, he wants to add both, but sort by multiple fields.
In that case you do exactly what I did this week and make the less-than operator kinda like this:
Edit: Ah crap, I should have read the rest of MaulingMonkey's post. I mean the same thing as his second part.
In that case you do exactly what I did this week and make the less-than operator kinda like this:
bool MySet::operator < (const MySetItem &rhs) const{ // Normally sort by field1, but use field2 for tie-breaker return (m_field1 < rhs.m_field1) || (m_field1 == rhs.m_field1) && (m_field2 < rhs.m_field2);}Edit: Ah crap, I should have read the rest of MaulingMonkey's post. I mean the same thing as his second part.
Author
It's not that I actually have to sort by b. I only have to sort by a. The problem is that because it is a set, if there is more than one value with the same a, it will not add that element to the set. I have my definitions as follows:
Where, in A*, my set should be sorted by a PATHBLK's f value (for those who haven't used A*, f = distance traveled + estimated distance to target). This works. However, because it is a set, if I try to add a PATHBLK with an f value equal to another already in the set.
EDIT: Actually, I may have just solved this by changing the < in my pathcompare to <=. I'll post back if it doesn't work :)
struct PATHBLK{ int f; int g; int h; Location myLocation; Location myParent; PATHBLK* parent; PATHBLK* next; int myParentDirection;};struct pathcompare{ bool operator()(const PATHBLK* lhs, const PATHBLK* rhs) const { return (lhs->f < rhs->f); }};Where, in A*, my set should be sorted by a PATHBLK's f value (for those who haven't used A*, f = distance traveled + estimated distance to target). This works. However, because it is a set, if I try to add a PATHBLK with an f value equal to another already in the set.
EDIT: Actually, I may have just solved this by changing the < in my pathcompare to <=. I'll post back if it doesn't work :)
Quote:Original post by GodlyGamr
EDIT: Actually, I may have just solved this by changing the < in my pathcompare to <=. I'll post back if it doesn't work :)
DO NOT DO THAT. YOU NOW HAVE A BUG. The STL *requires* that your ordering be such that for a != b, (ordering(a, b) || ordering(b,a)) returns false. If you do it otherwise, you risk ending up with your values improperly sorted; it's also possible that much worse things will happen.
The proper way to do this is either to use a multiset, or to implement the tiebreaker comparison. Neither one will compromise the sortedness of your values.
Quote:Original post by GodlyGamr
Where, in A*, my set should be sorted by a PATHBLK's f value (for those who haven't used A*, f = distance traveled + estimated distance to target). This works. However, because it is a set, if I try to add a PATHBLK with an f value equal to another already in the set.
EDIT: Actually, I may have just solved this by changing the < in my pathcompare to <=. I'll post back if it doesn't work :)
Did you read my post?
If you want to allow duplicate, identical entries, use a std::multimap.
If you don't want duplicates (now that I think about it, I believe even if you do), std::set requires you to sort every non identical entry, wheither or not you need the end result sorted.
Please see the second part of my original post in which I explain that even if you don't care if (using (f,g,h)) (3,0,3) comes before or after (3,2,-1), std::set cares, and thus you have to decide one way or the other.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
