Сохранение std :: map сбалансировано при использовании объекта в качестве ключа

Question

Я пишу код, в котором храню много объектов, которые я хочу получить, исходя из установленных критериев. Поэтому для меня было целесообразно использовать карту с объектом в качестве ключа. Если объект будет содержать «установленные критерии».

Вот упрощенный пример такого рода объектов я имею дело с:

class key 
    { 
     int x,y,w,h; 
    } 
    class object 
    { 
     ... 
    } 
    std::map<key, object, KeyCompare> m_mapOfObjects; 

Довольно просто, первая мысль была создать сравнения функций, как это:

struct KeyCompare 
    { 
     bool operator()(const key &a, const key &b) 
     { 
      return a.x < b.x || a.y < b.y || a.w < b.w || a.h < b.h; 
     } 
    } 

, но затем Я думал, что шансы на возвращение верны довольно высокими. Поэтому я решил, что это приведет к очень неуравновешенному дереву и, следовательно, к медленному поиску.

Моя главная забота в том, что, как я понимаю, станд :: карта использует, что одна функция таким образом: если (keyCompare (а, б)) { // левая сторона } еще если (keyCompare (Ь, а)) { // правая сторона } еще { // равно } Таким образом, я не могу просто использовать топор < Ьх, потому что тогда все с тем же х будет считаться равным, что не то, что я хочу. Я бы не возражал, чтобы это упорядочивалось таким образом, но его «равный» бит я просто не могу решить, не делая его неуравновешенным.

Я считаю, что их умножение - это нет, по очевидным причинам.

Таким образом, единственное решение я мог придумать было создать «UID» базу на информации:

typedef long unsigned int UIDType; 
    class key 
    {   
     private: 
     UIDType combine(const UIDType a, const UIDType b) 
     { 
      UIDType times = 1; 
      while (times <= b) 
      times *= 10; 
      return (a*times) + b; 
     } 

     void AddToUID(UIDType number) 
     { 
      if(number < 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 &a, const key &b) 
     { 
      return a.UID < b.UID; 
     } 
    } 

Но не только, что чувствую себя немного Hacky, «длинный неподписанных Int» не достаточно большой, чтобы удерживать потенциальные числа. I может положить его в строку, но скорость здесь является проблемой, и я предположил, что std :: string < стоит дорого. В целом, хотя меньше я могу сделать этот объект лучше.

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

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

Answer 1

Все, что вам нужно реализовать strict weak ordering, который вы можете легко достичь с помощью std::tie, который имеет меньше, чем сравнение operator< который выполняет lexicographical сравнения:

#include <tuple> 

struct KeyCompare 
{ 
    bool operator()(const key& a, const key& b) const 
    { 
     return std::tie(a.x, a.y, a.w, a.h) < std::tie(b.x, b.y, b.w, b.h); 
    } 
} 

Если у вас нет необходимой поддержки C++ 11, вы можете использовать std::tr1::tie из <tr1/tuple> или эквивалентных версий от б библиотек oost.

Answer 2

Я чувствую juanchopanza имеет очень хорошее решение, для тех, кто не имеет C++ 11 поддержки или подталкивания библиотеки

Я нашел очень простое решение на: What's the simplest way of defining lexicographic comparison for elements of a class?

Это решение работает для моего конкретная проблема немного лучше, чем кортеж (поскольку у меня также есть массив значений, которые я хотел бы рассмотреть). Но я бы очень рекомендовал, учитывая кортеж в будущем, как будет I.

struct keyCompare 
    { 
      bool operator()(const key &a, const key&b) 
      { 
      if(a.x != b.x) return a.x < b.x; 
      if(a.y != b.y) return a.y < b.y; 
      if(a.w != b.w) return a.w < b.w; 
      if(a.h != b.h) return a.h < b.h; 

      return false; //they must be equal 
      } 
    } 

благодаря juanchopanza за его ответ и на кого-то, кто имел вид в