Using a (mathematical) vector in a std::map
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. 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) 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!!
5 ответов
Вместо определения operator < для вашего ключевого класса вы можете дать карте собственный компаратор. Это функциональный объект, который принимает два аргумента и возвращает истину , если первый идет раньше второго. Примерно так:
struct CompareVectors
{
bool operator()(const Vector& a, const Vector& b)
{
// insert comparison code from question
}
};
typedef std::map<Vector, Value, CompareVectors> VectorValueMap;
Думаю, std :: tr1 :: unordered_map - это именно то, что вам нужно. Никакого строгого слабого упорядочивания не потребуется. GCC имеет нечто подобное в пространстве имен tr1 . Или выберите Boost.Unordered .
Неупорядоченные аналоги более пешеходной карты или набора дают вам два преимущества:
Вам не нужно определять оператор «меньше чем» там, где нет смысла
Хеш-таблицы могут работать лучше, чем сбалансированные бинарные деревья, последнее является предпочтительным методом реализации структур упорядоченных
картилинаборов. Но это зависит от вашего шаблона / требований доступа к данным.
Итак, просто используйте:
typedef std::tr1::unordered_map<Vector, std::vector<Object *> > VectorMap;
Здесь используется хеш-функция по умолчанию, которая заботится о вставке / поиске вашей карты.
PS: вещь >> будет исправлена в следующем стандарте и, следовательно, в будущих версиях компилятора.
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
Vectorto be ordered ? Yes:std::map, No:std::unordered_maporstd::tr1::unodered_maporstd::hash_maporboost::unordered_map. - Will this collection owns the
Object? Yes:boost::ptr_vectororstd::vector< std::unique_ptr, No:std::vector
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.
Осторожно: как было сказано в другом ответе, представление с плавающей запятой неудобно в компьютере, поэтому вам, вероятно, придется ослабить значение равенства и игнорировать цифры нижнего порядка (сколько - зависит от ваших вычислений).
Я думаю, ваш подход хорош. Если вы беспокоитесь о загрязнении класса Vector, то я считаю, что отдельная функция будет работать так же хорошо:
bool operator<( const Vector& lhs, const Vector& rhs )
{
...
}
Но просто слово предупреждения: то, что вы здесь делаете, довольно рискованно. В вычислениях с плавающей запятой часто возникают ошибки. Предположим, вы вставляете какую-то точку в свою карту. Затем вы вычисляете точку и проверяете карту, чтобы убедиться, что она там есть. Даже если со строго математической точки зрения вторая точка такая же, как и первая, нет никакой гарантии, что вы найдете ее на карте.
Вы можете отделить его от класса. Затем укажите его как оператор сравнения для std :: map.
std::map<Vector,std::vector<Object*>,Compare> data;
Где Compare - функция (или функтор), которая может сравнивать два объекта Vector.
Я также думаю, что вы можете упростить операцию сравнения.
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;
}
Обратите внимание, что мы проверяем меньшее, чем большее, а затем проваливаемся, чтобы получить равное. Лично мне нравится простота этого стиля. Но я часто вижу это сжатым так:
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;
}