Sign in to follow this  
GodlyGamr

std::set.insert() question

Recommended Posts

GodlyGamr    396
Hey all, I'm trying to create a set of a PATHBLKs, where PATHBLK is defined as follows:
struct Location
{
	int x;
	int y;

	Location* nextLocation;
};

struct PATHBLK
{
	int f;
	int g;
	int h;

	Location myLocation;
	Location myParent;
	int myParentDirection;

};


When I try to use the set.insert() function to insert a PATHBLK into the set, I get errors and warnings such as these: warning C4786: 'std::pair<std::_Tree<PATHBLK,PATHBLK,std::set<PATHBLK,std::less<PATHBLK>,std::allocator<PATHBLK> >::_Kfn,std::less<PATHBLK>,std::allocator<PATHBLK> >::iterator,std::_Tree<PATHBLK,PATHBLK,std: :set<PATHBLK,std::less<PATHBLK>,std::allocator<PATHBLK> >::_Kfn,std::less<PATHBLK>,std::allocator<PATHBLK> >::iterator>' : identifier was truncated to '255' characters in the debug information error C2784: 'bool __cdecl std::operator <(const class std::multiset<_K,_Pr,_A> &,const class std::multiset<_K,_Pr,_A> &)' : could not deduce template argument for 'const class std::multiset<_K,_Pr,_A> &' from 'const struct PATHBLK' 8 errors and 4 warnings in total. Perhaps I'm just getting the parameters wrong. What are the correct parameters for the insert function? Thanks, Jeff

Share this post


Link to post
Share on other sites
snk_kid    1312
Did you overload the relational less than operator for PATHBLK? if not did you provide a custom predicate type for PATHBLK to std::set?

Either do:


bool operator<(const PATHBLK& lhs, const PATHBLK& rhs) { // or make it a member function
return ...; // must impose a Strict Weak Ordering of elements
}


or


struct compare {
bool operator()(const PATHBLK& lhs, const PATHBLK& rhs) const {
return ...; // must impose a Strict Weak Ordering of elements
}
};

typedef std::set<PATHBLK, compare> my_set;

Share this post


Link to post
Share on other sites
JohnBolton    1372
warning C4786:

This warning is saying that the name of the symbol is too long to store in the debug information, so the compiler stores a truncated version instead. This has never caused me any problems, so I always disable this warning.

error C2784:

The problem is that there is no '<' operator defined for your class. You need to do one of the following:
  1. Pass a comparison function or functor as one of the template parameters for std::set<>
  2. Overload operator<( PATHBLK const &, PATHBLK const & ) or PATHBLK::operator<( PATHBLK const & )
  3. Specialize std::less<PATHBLK>

#1 is generally the best when '<' is not a natural operation for the class. #3 is generally not the best thing to do.

Share this post


Link to post
Share on other sites
Zahlman    1682
To explain further:

A multiset is an expansion of the set concept. One of the guarantees of a set is that it will not contain duplicate elements.

In order to do this efficiently, the set has to be able to quickly check if a matching element is already in the set - efficiently. The dumb way would be to just compare against every element. In order to speed that up, the set sorts your elements as they are inserted, keeping them in a binary tree (with some extra work done behind the scenes to keep the tree balanced) - then it can do a binary search for an element on each insert (to guard against multiple inclusion), and also figure out where to insert.

A multiset doesn't need to prevent duplication of elements (of course), but it still keeps things sorted in order to offer quick insertion/retrieval/deletion (in general, quick *lookup* - figuring out where the important element is). Since it's not an indexed container, after all, it needs to be able to find elements quickly according to what they are, not where they are.

So in order to do that sorting, it has to be possible to compare elements. By default, the template code is set up to compare elements according to the element's operator<, which means that compilation will fail if that doesn't exist - not in the template code, but once the template is instantiated for the element type.

To keep things general (since more than one sorting order might be reasonable for an element type, or because no sorting order might be "natural", but you'll have to specify one anyway - and then keep it separated out, so that *other* clients don't try to operator< your class), it's set up to accept a comparison functor (like Comparator subclasses, if you've used those in Java) as the third parameter. So that it works with the element operator< by default, the third parameter defaults to an object of the class "std::less", which is a comparison functor which just calls the object's operator<.




P.S. Please consider if using std::list - or some other container for that matter - might simplify your Location objects. :) It looks like you are trying to hand-roll a linked list :\

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