Sign in to follow this  
GodlyGamr

Yet Another std::set question

Recommended Posts

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

Share this post


Link to post
Share on other sites
I'm not exactly sure I follow. If you want to be able to store the same integer multiple times, use a std::multiset:
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 entry
stuff.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
}

Share this post


Link to post
Share on other sites
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:
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);
}
A multi-set is not necessary in this case as the second field breaks any ties.

Edit: Ah crap, I should have read the rest of MaulingMonkey's post. I mean the same thing as his second part.

Share this post


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


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 :)

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this