Использование (математического) вектора в std :: map - PullRequest
8 голосов
/ 18 августа 2010

Связано: что я могу использовать как std::map ключи?

Мне нужно было создать отображение, где конкретные ключевые места на космической карте со списками объектов. std::map казалось способ сделать это.

Так что я набираю std::map на xyz Vector

class Vector
{ 
  float x,y,z
} ;

, и я делаю std::map<Vector, std::vector<Object*> >. Итак, обратите внимание, что ключ здесь не a std::vector, это объект class Vector, который является просто математическим вектором xyz моего собственного создания.

Чтобы создать «строго слабый порядок», я написал следующую перегрузку для 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 ;
    }
  }

Это немного длинно, но в основном делает так, чтобы любой вектор можно было последовательно назвать меньшим, чем любой другой вектор ((-1, -1, -1) <(-1, -1,1), и (- 1, -1, 1)> (-1, -1, -1), например).

Моя проблема в том, что это действительно искусственно, и хотя я закодировал его, и он работает, я обнаружил, что он "загрязняет" мой класс Vector (математически) этим действительно странным, искусственным, не математическим понятием " меньше чем "для вектора.

Но мне нужно создать отображение, в котором конкретные ключевые местоположения в пространстве сопоставляются с определенными объектами, и std :: map кажется способом сделать это.

Предложения? Приветствуются готовые решения !!

Ответы [ 5 ]

5 голосов
/ 18 августа 2010

Вместо определения operator< для вашего ключевого класса вы можете дать карте собственный компаратор. Это функциональный объект, который принимает два аргумента и возвращает true, если первый предшествует второму. Примерно так:

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

typedef std::map<Vector, Value, CompareVectors> VectorValueMap;
3 голосов
/ 18 августа 2010

Вы можете отделить его от класса.Затем укажите его как оператор сравнения для 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;
}
1 голос
/ 19 августа 2010

Это нормально, что вы обнаружите, что ваш класс загрязнен этим. Это также загрязнено с точки зрения CS.

Обычный способ определения такого оператора - использование (потенциально дружественных) свободных функций.

Однако первый вопрос, который нужно задать себе: имеет ли это смысл. Проблема в том, что вы определили метод для вашего класса, который имеет смысл только в ограниченном контексте, но доступен везде. Вот почему возникает чувство «загрязнения».

Теперь, если бы мне понадобилось такое отображение из Vector в набор Object с, вот вопросы, которые я бы сам себе задал:

  • Нужно ли заказывать Vector? Да: std::map, Нет: std::unordered_map или std::tr1::unodered_map или std::hash_map или boost::unordered_map.
  • Будет ли эта коллекция владельцем Object? Да: boost::ptr_vector<Object> или std::vector< std::unique_ptr<Object> >, Нет: std::vector<Object*>

Теперь в обоих случаях (map и unordered_map) мне понадобится что-то для преобразования моего ключа. Коллекция предоставляет дополнительный аргумент шаблона, который принимает тип Functor.

Осторожно: как уже упоминалось в другом ответе, представление с плавающей точкой неудобно в компьютере, поэтому вам, вероятно, придется ослабить значение равенства и игнорировать цифры младшего разряда (сколько зависит от ваших вычислений).

1 голос
/ 18 августа 2010

Я думаю std::tr1::unordered_map это то, что вам нужно.Никакого строгого слабого заказа не потребуется.GCC имеет нечто похожее и в tr1 пространстве имен.Или перейдите на Boost.Unordered .

Неупорядоченные аналоги более пешеходных map или set дает вам два преимущества:

  • Вам не нужно определять оператор меньше, где ни один не имеет смысла

  • Хеш-таблицы могут работать лучше, чем сбалансированные двоичные деревья, причем последний является предпочтительным методом реализации упорядоченного map или set структур.Но это зависит от вашего шаблона / требований доступа к данным.

Итак, просто продолжайте и используйте:

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

Это использует хеш-функцию по умолчанию, которая принимаетосторожность при вставке / поиске вашей карты.

PS: > > вещь будет исправлена ​​в следующем стандарте и, следовательно, в будущих версиях компилятора.

0 голосов
/ 18 августа 2010

Я думаю, что ваш подход в порядке. Если вы беспокоитесь о загрязнении класса Vector, то я считаю, что автономная функция будет работать так же хорошо:

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

Но только предупреждение: то, что вы здесь делаете, довольно рискованно. Часто возникают ошибки в вычислениях с плавающей запятой. Предположим, вы вставили какую-то точку на карту. Затем вы вычисляете точку и проверяете карту, чтобы увидеть, есть ли она там. Даже если со строго математической точки зрения вторая точка совпадает с первой, нет гарантии, что вы найдете ее на карте.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...