Using a (mathematical) vector in a std::map

Question

Related: what can I use as std::map keys?

I needed to create a mapping where specific key locations in space map to lists of objects. std::map seemed the way to do it.

So I'm keying a std::map on an xyz Vector

class Vector
{ 
  float x,y,z
} ;

, and I'm making a std::map<Vector, std::vector<Object*> >. So note the key here is not a std::vector, its an object of class Vector which is just a math xyz vector of my own making.

To produce a "strictly weak ordering" I've written the following overload for operator<:

  bool Vector::operator<( const Vector & b ) const {
    // z trumps, then y, then x
    if( z < b.z )
    {
      return true ;
    }
    else if( z == b.z )
    {
      if( y < b.y )
      {
        // z == b.z and y < b.y
        return true ;
      }
      else if( y == b.y )
      {
        if( x < b.x )
        {
          return true ;
        }
        else if( x == b.x )
        {
          // completely equal
          return false ;
        }
        else
        {
          return false ;
        }
      }
      else
      {
        // z==b.z and y >= b.y
        return false ;
      }
    }
    else
    {
      // z >= b.z
      return false ;
    }
  }

Its a bit long but basically makes it so any vector can consistently be said to be less than any other vector ((-1, -1, -1) < (-1,-1,1), and (-1, -1, 1) > (-1,-1,-1) for example).

My problem is this is really artificial and although I've coded it and it works, I am finding that it "pollutes" my Vector class (mathematically) with this really weird, artificial, non-math-based notion of "less than" for a vector.

But I need to create a mapping where specific key locations in space map to certain objects, and std::map seems the way to do it.

Suggestions? Out-of-box solutions welcome!!

Answer 1

Instead of defining operator< for your key class, you can give the map a custom comparator. This is a function object that takes two arguments and returns true if the first comes before the second. Something like this:

struct CompareVectors
{
    bool operator()(const Vector& a, const Vector& b)
    {
        // insert comparison code from question
    }
};

typedef std::map<Vector, Value, CompareVectors> VectorValueMap;

Answer 2

You can separate it from the class. Then specify it as the comparison operator for the std::map.

std::map<Vector,std::vector<Object*>,Compare>  data;

Where Compare is a function (or functor) that can compare tow Vector objects.
I also think you can simplify your Compare operation.

bool Compare<( const Vector& lhs, const Vector& rhs)
{
   // z trumps, then y, then x
   if( lhs.z < rhs.z )
   {    return true ;
   }
   else if (lhs.z > rhs.z)
   {    return false;
   }
   // Otherwise z is equal
   if( lhs.y < rhs.y )
   {    return true ;
   }
   else if( lhs.y > rhs.y )
   {    return false;
   }
   // Otherwise z and y are equal
   if ( lhs.x < rhs.x )
   {    return true;
   }
   /* Simple optimization Do not need this test
      If this fails or succeeded the result is false.
   else if( lhs.x > rhs.x )
   {    return false;
   }*/
   // Otherwise z and y and x are all equal
   return false;
}

Notice we test for less then greater and then fall through for equal. Personally I like the simplicity of this style. But I often see this being compressed like this:

bool Compare<( const Vector& lhs, const Vector& rhs)
{
    // Note I use three separate if statements here for clarity.
    // Combining them into a single statement is trivial/
    //
    if ((lhs.z < rhs.z)                                        ) {return true;}
    if ((lhs.z == rhs.z) && (lhs.y < rhs.y)                    ) {return true;}
    if ((lhs.z == rhs.z) && (lhs.y == rhs.y) && (lhs.x < rhs.x)) {return true;}

    return false;
}

Answer 3

I think std::tr1::unordered_map is just what you need. No strict weak ordering will be required. GCC has a something similar in tr1 namespace as well. Or go for Boost.Unordered.

The unordered counterparts of the more pedestrian map or set gives you two advantages:

• You don't need to define a less-than operator where none makes sense

• Hash tables may perform better than balanced binary trees, the latter being the preferred method of implementing the ordered map or set structures. But that depends on your data access pattern/requirements.

So, just go ahead and use:

typedef std::tr1::unordered_map<Vector, std::vector<Object *> > VectorMap;

This makes use of a default hash function that takes care of insertion/search for your map.

PS: the > > thingy will be fixed in the upcoming standard and hence future compiler versions.

Answer 4

It's normal that you find that your class is polluted by this. It's also polluted from a CS point of view.

The normal way of defining such an operator is through (potentially friend) free functions.

However the first question to ask yourself is: does it makes sense. The issue is that you have defined a method for your class that is only meaningful in a limited context but accessible everywhere. That's why the "pollution" feeling kicks in.

Now, if I were to need such mapping from a Vector to a collection of Objects, here are the questions I would ask myself:

• Do I need the Vector to be ordered ? Yes: std::map, No: std::unordered_map or std::tr1::unodered_map or std::hash_map or boost::unordered_map.
• Will this collection owns the Object ? Yes: boost::ptr_vector<Object> or std::vector< std::unique_ptr<Object> >, No: std::vector<Object*>

Now, in both cases (map and unordered_map), I will need something to transform my key. The collection provide a supplementary template argument which takes a Functor type.

Beware: as has been mentioned in another answer, floating point representation is awkward in a computer, therefore you will probably need to relax the meaning of equality and ignore the lower order digits (how many depends on your computations).

Answer 5

I think your approach is fine. If you're worried about polluting the Vector class, then I believe a stand-alone function will work just as well:

bool operator<( const Vector& lhs, const Vector& rhs )
{
    ...
}

But just a word of warning: what you're doing here is pretty risky. There are often errors in floating point calculations. Suppose you insert some point into your map. Then you calculate a point and check the map to see if it's there. Even if, from a strictly mathematical point of view, the second point is the same as the first, there's no guarantee that you'll find it in the map.