Keeping std::map balanced when using an object as key

Question

I am writing some code where I am storing lots of objects that I want to get back based on set criteria. So to me it made sense to use a map with an object as a key. Where the object would contain the "set criteria".

Here is a simplified example of the kind of objects i am dealing with:

    class key
    {
         int x,y,w,h;
    }
    class object
    {
       ...
    }
    std::map<key, object, KeyCompare> m_mapOfObjects;

Quite simple, the first thought was to create a compare functions like this:

    struct KeyCompare
    {
       bool operator()(const key &a, const key &b)
       {
            return a.x < b.x || a.y < b.y || a.w < b.w || a.h < b.h;
       } 
    }

but then i thought the chances of this returning true are quite high. So I figured this would lead to a very unbalanced tree and therefore slow searching.

My main worry is that as I understand it, std::map uses that one function in this way: if( keyCompare(a,b) ) { //left side } else if (keyCompare(b,a)) { //right side } else { //equal } So i can't just use a.x < b.x, because then anything with the same x would be considered equal, which is not what i want. I would not mind it ordering it in this way but its the "equal" bit i just can't seem to solve without making it unbalanced.

I figure multiplying them all together is a no no for obvious reasons.

So the only solution i could come up with was to create a "UID" base on the info:

    typedef long unsigned int UIDType; 
    class key
    {           
        private:
        UIDType combine(const UIDType  a, const UIDType b) 
        {
            UIDType times = 1;
            while (times <= b)
            times *= 10;
            return (a*times) + b;
        } 

        void AddToUID(UIDType number)
        {
            if(number < m_UID)
            {
                m_UID = combine(number, m_UID);
            }
            else
            {
                m_UID = combine(m_UID, number);
            }
        }
        UIDType UID;
        public:
        int x,y,w,h;
        key()
        {
            AddToUID(x);
            AddToUID(y);
            AddToUID(w);
            AddToUID(h);
        }
    }
    struct KeyCompare
    {
       bool operator()(const key &a, const key &b)
       {
            return a.UID < b.UID;
       } 
    }

But not only does that feel a little hacky, "long unsigned int" isn't big enough to hold the potential numbers. I could put it in a string, but speed is an issue here and I assumed an std::string < is expensive. Overall though the smaller i can make this object the better.

I was wondering if anyone has any suggestions for how to do this better. Perhaps i need to use something other then a std::map or perhaps there is another overload. Or perhaps there is something glaringly obvious that i'm missing here. I really feel like i'm over-complicating this, perhaps im really barking up the wrong tree with a map.

As i was writing this it occurs to me that divide is another way to get a "unique" number but that could also equal very large numbers

one of the related questions has brought up the term "lexicographical ordering" I think this requires more research! — chrispepper1989, Apr 24 '13 at 16:39
`std::map`, and also `std::set` balances themselves, otherwise they woudln't meet the complexity criteria from the specification. — Zyx 2000, Apr 24 '13 at 16:41
surely they can only balance themselves based on the comparison function given though? can you explain how they balance themselves? — chrispepper1989, Apr 24 '13 at 16:51

score 2 · Accepted Answer · answered Apr 24 '13 at 16:44

2

All you need is to implement a strict weak ordering, which you can easily achieve using std::tie, which has a less than comparison operator< which performs a lexicographical comparison:

#include <tuple>

struct KeyCompare
{
   bool operator()(const key& a, const key& b) const
   {
        return std::tie(a.x, a.y, a.w, a.h) < std::tie(b.x, b.y, b.w, b.h);
   } 
}

If you do not have the required C++11 support, you can use std::tr1::tie from <tr1/tuple> or equivalent versions from the boost libraries.

answered Apr 24 '13 at 16:44

juanchopanza

223,364
34
402
480

Thank you for bringing my attention to tuple, that does seems a good solution. I also came across a good solution here: http://stackoverflow.com/questions/2500664/whats-the-simplest-way-of-defining-lexicographic-comparison-for-elements-of-a-c would you mind if i add an alternative do your answer? – chrispepper1989 Apr 24 '13 at 16:56
@chrispepper1989 you are allowed to answer your own questions, so you can actually add your solution as an answer. – juanchopanza Apr 24 '13 at 19:23

score 0 · Answer 2 · edited May 23 '17 at 11:57

I feel juanchopanza has a very good solution, for those who do not have C++11 support or boost libraries

I found a very simple solution on: What's the simplest way of defining lexicographic comparison for elements of a class?

This solution works for my particular problem a little better then tuple would (as i also have an array of values that i would like to consider). But I would highly recommend considering tuple in future, as will I.

    struct keyCompare
    {
          bool operator()(const key &a, const key&b)
          {   
            if(a.x != b.x) return a.x < b.x;
            if(a.y != b.y) return a.y < b.y;
            if(a.w != b.w) return a.w < b.w;
            if(a.h != b.h) return a.h < b.h;

            return false; //they must be equal 
          }   
    }

thanks to juanchopanza for his answer and to anyone else who had a look in

Keeping std::map balanced when using an object as key

2 Answers2