• Advertisement
Sign in to follow this  

std::map::find() crashing

This topic is 3406 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

In one of my code std::map::find() is crashing the programm. actually I am using map<ConstructPointer, QStringList*> My ConstructPointer contains and constructed by two data members of integer type (Enums), and it also have operator==() overload. I've my own LessFunctor for Compare.
typedef
  std::map<ConstructPointer, QStringList*, ConstructPointer::FakeLessFunctor>
    ConstructMap;
ConstructMap constructList;
		class ConstructPointer{
			private:
				Construct c;
				ConstructType t;
			public:
				Construct construct(){return c;}
				ConstructType constructType(){return t;}
			public:
				ConstructPointer(Construct cns, ConstructType cnsT):c(cns), t(cnsT){}
				bool operator==(const ConstructPointer& cnsPt) const{
					return (cnsPt.c == c && cnsPt.t == t);
				}
				/*
				friend bool operator==(const ConstructPointer& lCnsPt, const ConstructPointer& rCnsPt){
					return (lCnsPt.c == rCnsPt.c && lCnsPt.t == rCnsPt.t);
				}
				*/
			public:
				struct LessFunction{
					bool operator()(const ConstructPointer& lhsCnsPt, const ConstructPointer& rhsCnsPt) const{
						return lhsCnsPt.t < rhsCnsPt.t;
					}
				};
				struct FakeLessFunctor{
					bool operator()(const ConstructPointer&, const ConstructPointer&) const{return true;}
				};
		};

In my code I am executing constructList.find() in the following way
ConstructPointer cnsPt(cns, cnsTp);//Constructing a new Object
ConstructMap::const_iterator it = constructList.find(cnsPt);
My program is crashing on the line where I am executing find(). ____________________ MY INVESTIGATION ```````````````````` To investigate I looked at the STL source. where I found std::map executes find() method of Tree and from that stl_tree.h I found
  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue,
		      _Compare, _Alloc>::const_iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k) const
    {
      const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
      return (__j == end()
	      || _M_impl._M_key_compare(__k, 
					_S_key(__j._M_node))) ? end() : __j;
    }
So I saw
_Rb_tree_impl<_Compare> _M_impl;
template<typename _Key_compare, 
	       bool _Is_pod_comparator = __is_pod(_Key_compare)>
struct _Rb_tree_impl : public _Node_allocator
        {
	  _Key_compare		_M_key_compare;

and this is the _Rb_tree class template declaration
template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc = allocator<_Val> >
    class _Rb_tree{

which means
_M_key_compare(__k,_S_key(__j._M_node))
will invoke the lessFunction's operator()() which returns bool type if lhs < rhs. But how will understand by LessFunctor::operator()() wheather its equal or not

Share this post


Link to post
Share on other sites
Advertisement
FakeLessFunctor is an inadmissible comparison. For a comparison L, if L(a, b) is true, then L(b, a) must be false. Since FakeLessFunctor violates this rule, bad things happen. Don't use it.

Share this post


Link to post
Share on other sites
I don't need any kinda ordering in the map (I know you would say me to use unordered_map). so I did it always returns true.
thats why I named it FakeLess However I've another LessFunctor that I can use. I have given that LessFunctor a try But I don't think thats the reason cause It is still crashing on the same line due to std::map::find()

Share this post


Link to post
Share on other sites
I think I've found the problem LessFunctor is designed in such a way that more than one element can get equal weight. But its not a multimap.
and Ya I just made sure that KeyT doesn't need an operator==() .
as the map is a balanced ordered tree it works just by comparing is less then travarse towards more and if more stop and return last element.and vice versa way.

Share this post


Link to post
Share on other sites
Quote:
Original post by nlbs
I don't need any kinda ordering in the map (I know you would say me to use unordered_map). so I did it always returns true.
thats why I named it FakeLess However I've another LessFunctor that I can use. I have given that LessFunctor a try But I don't think thats the reason cause It is still crashing on the same line due to std::map::find()
You might not need it to have any ordering, but to insert the items into its tree it needs to know whether to follow the left or right pointer of each node. Also, more importantly, when you search for the same item next time, it needs to be able to find the item, which (assuming no other items have been added since) means going down through the same nodes in the tree to find the item.
Instead of the class you've posted, consider using std::pair, if your class does actually only have two data members. Although the member variable names are pretty generic, it does nice things like provide a propper less-than operator for you etc. Or you could just study the less-than operator it provides.

If you're not prepared to provide a means of finding an item in O(log n) time by strict-weak-ordering though, then you may as well throw performance out the window and just use a list.

Edit:
Quote:
I think I've found the problem
You mean others found it for you...

Share this post


Link to post
Share on other sites
If you're using a compiler like Visual Studio, compile and run your program as debug build, and usually the STL pops up assertion failures when you try to do invalid things with iterators and such. Highly recommended for catching problems, saved my ass many a time.

And yes, you must have a proper operator< regardless of whether you 'need' sorting - std::map works by sorting whether you like it or not.

Share this post


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

  • Advertisement