Keeping std::map balanced when using an object as key <p>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".</p> <p>Here is a simplified example of the kind of objects i am dealing with:</p> <pre><code> class key { int x,y,w,h; } class object { ... } std::map&lt;key, object, KeyCompare&gt; m_mapOfObjects; </code></pre> <p>Quite simple, the first thought was to create a compare functions like this:</p> <pre><code> struct KeyCompare { bool operator()(const key &amp;a, const key &amp;b) { return a.x &lt; b.x || a.y &lt; b.y || a.w &lt; b.w || a.h &lt; b.h; } } </code></pre> <p>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. </p> <p>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 &lt; 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. </p> <p>I figure multiplying them all together is a no no for obvious reasons.</p> <p>So the only solution i could come up with was to create a "UID" base on the info:</p> <pre><code> typedef long unsigned int UIDType; class key { private: UIDType combine(const UIDType a, const UIDType b) { UIDType times = 1; while (times &lt;= b) times *= 10; return (a*times) + b; } void AddToUID(UIDType number) { if(number &lt; 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 &amp;a, const key &amp;b) { return a.UID &lt; b.UID; } } </code></pre> <p>But not only does that feel a little hacky, "long unsigned int" isn't big enough to hold the potential numbers. I <em>could</em> put it in a string, but speed is an issue here and I assumed an std::string &lt; is expensive. Overall though the smaller i can make this object the better. </p> <p>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. </p> <p>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</p>