Использование (математического) вектора в std::map

Question

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

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

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

class Vector
{ 
  float x,y,z
} ;

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

Чтобы создать "строго слабый порядок", я написал следующую перегрузку для 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 кажется способом сделать это.

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

Answer 1

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

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

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

Answer 2

Вы можете отделить его от класса. Затем укажите его как оператор сравнения для std::map.

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

Где Compare - это функция (или функтор), которая может сравнивать буксировочные векторные объекты.
Я также думаю, что вы можете упростить операцию сравнения.

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;
}

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

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

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

• Нужно ли мне 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.

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

Answer 5

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

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

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