Thread: std::map::find() crashing

  1. #1
    Registered User
    Join Date
    Jun 2007
    Posts
    219

    std::map::find() crashing

    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.
    Code:
    typedef
      std::map<ConstructPointer, QStringList*, ConstructPointer::FakeLessFunctor>
        ConstructMap;
    ConstructMap constructList;
    Code:
    		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
    Code:
    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
    Code:
      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
    Code:
    _Rb_tree_impl<_Compare> _M_impl;
    Code:
    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
    Code:
    template<typename _Key, typename _Val, typename _KeyOfValue,
               typename _Compare, typename _Alloc = allocator<_Val> >
        class _Rb_tree{
    which means
    Code:
    _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

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Your FakeLessOperator is completely useless to the map, since it doesn't determine a strict weak ordering. Delete it and use LessFunction or something else that does.

    Equality, if I'm not mistaken is determined when Compare(a, b) and Compare(b, a) both return false.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by noobcpp
    But how will understand by LessFunctor::operator()() wheather its equal or not
    What do you mean?

    Does it crash when you use LessFunction instead of FakeLessFunctor? You might want to provide the smallest and simplest compilable code that demonstrates the problem.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Jun 2007
    Posts
    219
    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()

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    62
    You should a map work if it cannot compare its keys?

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    find() requires a real honest-to-goodness ordering, since it uses binary search (well, it doesn't have to, I suppose, but something logarithmic, but it's going to use that ordering). If you lie to the system, well, it's not much of a surprise that it doesn't work.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by noobcpp
    I don't need any kinda ordering in the map (I know you would say me to use unordered_map).
    If you can indeed use a more appropriate container then do so. The comparator for a map must obey the strict weak ordering (i.e., "less than comparable") requirement, otherwise things like searching would not work correctly.

    Quote Originally Posted by noobcpp
    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()
    Post the smallest and simplest compilable code that demonstrates the problem. There is no point posting about your standard library implementation since your standard library implementation is far more likely to be correct than your own code.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Jun 2007
    Posts
    219
    Quote Originally Posted by laserlight View Post
    What do you mean?
    at the end I wrote the stl code that is
    Code:
    _M_impl._M_key_compare(__k,_S_key(__j._M_node))
    which actually is
    Code:
    _Rb_tree_impl<_Compare>::_Key_compare(__k,_S_key(__j._M_node))
    and that means
    Code:
    _Compare(__k,_S_key(__j._M_node))
    which means
    Code:
    _Compare()(__k,_S_key(__j._M_node))
    and here this _Compare is the template argument that represent's the LessFubctor. and it returns bool value wheather lhs < rhs or not. But why and how it is being used for comparisn

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by noobcpp
    and here this _Compare is the template argument that represent's the LessFubctor. and it returns bool value wheather lhs < rhs or not. But why and how it is being used for comparisn
    It is used for the comparison because you provided it as the predicate for use in comparing. How it is used depends on the implementation, and std::map is typically implemented with a balanced binary tree. These facts, however, are secondary to your problem, since you should not be concerned about the implementation of a std::map when you are merely using it.
    Last edited by laserlight; 12-28-2008 at 08:38 AM. Reason: Let's be more generic with our trees.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by noobcpp View Post
    But why and how it is being used for comparisn
    anon was being cautious, but he shouldn't have been. It knows that it's found what it's looking for when neither target < key nor key < target is true. (In other words, just like < in numbers -- if a and b are different numbers, then either a < b or b < a; but if a = b, then neither of the < will be true.)

  11. #11
    Registered User
    Join Date
    Jun 2007
    Posts
    219
    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.
    Last edited by noobcpp; 12-28-2008 at 10:04 AM.

  12. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I think I've found the problem LessFunctor is designed in such a way that more than one element can get equal weight.
    If you want to compare based on both members, it might look something like that:

    Code:
    struct LessFunction{
        bool operator()(const ConstructPointer& lhs, const ConstructPointer& rhs) const{
            return lhs.t < rhs.t || (lhs.t == rhs.t && lhs.c < rhs.c);
        }
    };
    i.e compare by first criterion (t) or if they are equal by second criterion (c).

    Now the map will consider ConstructPointers equivalent only if their both members are equal.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Testing which forum can answer the fastest huh?:
    http://www.gamedev.net/community/for...opic_id=519109
    I put my answer there this time.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Jun 2007
    Posts
    219
    LOL don't take it offensive.Think practically. I need to solution quickly.sometimes c-board takes time and sometime gamedev.net takes time. so I've posted in both of them.
    and I've never said your helps were unhelpful but I located that problem when I was just screwing up the LessFunctor:perator()() however at the begining I thought that the problem was in a different area.
    Last edited by noobcpp; 12-28-2008 at 11:15 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Strange windows STL crashing problem
    By kdmiller in forum C++ Programming
    Replies: 5
    Last Post: 06-23-2010, 02:25 PM
  2. Program crashing, Need help!
    By Obsidian_179 in forum C Programming
    Replies: 3
    Last Post: 06-19-2008, 05:26 PM
  3. need help program crashing
    By tunerfreak in forum C++ Programming
    Replies: 14
    Last Post: 05-22-2006, 11:29 AM
  4. Replies: 5
    Last Post: 06-03-2005, 10:41 PM
  5. function crashing on Unix but not Windoze
    By mlupo in forum C Programming
    Replies: 3
    Last Post: 11-18-2001, 09:43 AM