Как разместить объекты, которые кажутся несопоставимыми в C ++ std :: set?

Question

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

struct ServerID
{
  std::string name; // name of the server
  int port;
};

std::set<ServerID> servers; // compiler error, no operator< defined

Это всего лишь один пример распространенной проблемы, когда я хочу сделать объект сопоставимым.

Мое текущее решение обычно выглядит так:

bool operator< (const ServerID & lhs, const ServerID & rhs)
{
  if (lhs.name != rhs.name)
  {
    return lhs.name < rhs.name;
  }
  else
  {
    return lhs.port < rhs.port;
  }
}

Это просто решение, которое я нашел сам. Но я подозреваю, что эта проблема также может быть признана в информатике. Так что, если мне повезет, есть лучшее решение для этого. Кто-нибудь может намекнуть мне на это?

Answer 1

Я бы рекомендовал не реализовывать его как operator

struct server
{
   std::string name;
   int port;
};
struct name_then_port : public std::binary_function<server,server,bool>
{
   bool operator()( server const & lhs, server const & rhs ) {
      // using litb approach (more efficient as it does not call both < and == on strings:
      int cmp = lhs.name.compare(rhs.name);
      return ( cmp < 0 ) || ((cmp==0) && ( lhs.port < rhs.port));
   }
};
struct port_then_name : public std::binary_function<server,server,bool>
{
   bool operator()( server const & lhs, server const & rhs ) {
      return (lhs.port < rhs.port) || ((lhs.port==rhs.port) && (lhs.name<rhs.name));
   }
};
int main()
{
   std::set< server, name_then_port > servers; // or:
   std::set< server, port_then_name > servers2;
}

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

Answer 2

Ваше каноническое решение. Я не уверен, как вы могли бы сделать это так, чтобы было лучше.

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

Возможность, которая может помочь в некоторых обстоятельствах (если вы обнаружите, что в производительности преобладают сравнения), заключается в создании «ключа сортировки» - сравнение строк может быть дорогостоящим. Ключ сортировки - это целое число, которое можно использовать для быстрого сравнения объектов. Если ключ сортировки сравнивается меньше чем, то строка тоже подойдет.

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

В Windows функция LCMapString может использоваться для создания ключа сортировки строк таким образом. Я думаю, что тогда вы можете использовать быструю функцию, такую ​​как memcmp, для сравнения строк вместо более медленного сравнения строк. Это более полезно, если вы будете выполнять сравнение без учета регистра или использовать полный диапазон символов Юникода и хотите получить правильные сравнения в соответствии с их правилами.

Answer 3

Я бы использовал string::compare

bool operator< (const ServerID & lhs, const ServerID & rhs) {
  int lcr = lhs.name.compare(rhs.name);
  return lcr < 0 || (lcr == 0 && lhs.port < rhs.port);
}

Если для вас не имеет смысла сравнивать его, и единственное его использование - вставить его в set, вы можете использовать функтор

struct ServerIdCompare {
  bool operator()(const ServerID & lhs, const ServerID & rhs) const {
    int lcr = lhs.name.compare(rhs.name);
    return lcr < 0 || (lcr == 0 && lhs.port < rhs.port);
  }
};

std::set<ServerID, ServerIdCompare> servers;

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

Answer 4

Я обычно пишу это как:

return x.name < y.name ||
       x.name == y.name && x.port < y.port;

... которую вы можете продолжать расширять для всех имеющихся у вас переменных-членов. Это решение закорочено как можно скорее и устраняет разветвление.

Обратите внимание, что для этого необходимо определить operator< для каждой из переменных-членов, что в любом случае хорошо бы реализовать вне этой подпрограммы.

Answer 5

В этом случае, если порядок не имеет значения, вы можете сравнить порт перед строкой из-за стоимости сравнения строк.

Answer 6

Если все, что вам нужно, это хороший заказ, и вам не важно, каков этот заказ, то ваше решение в порядке.

Answer 7

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

Answer 8

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

Если вы знаете, что у вас не будет двух серверов с одинаковыми именами, но с разными портами (или вы захотите обращаться с ними одинаково), вы можете отказаться от этой части функции сравнения. Более реалистичный пример был бы, если бы у вас было больше элементов в объекте сервера, которые не имели отношения к идентификатору самого сервера (например, кэш «последнего запроса»); в этом случае вы, вероятно, не захотите, чтобы ваш набор различался на основе этого поля, поэтому вы не включили бы его в функцию сравнения. OTOH, это может быть не лучший дизайн для объекта сервера в любом случае.

Если вам трудно ответить на вопрос "Когда два сервера (объекта) следует считать идентичными?" тогда вам может вообще не понадобиться набор.

Answer 9

Я стараюсь помещать оператор <внутри структуры, чтобы все было аккуратно, но в остальном у вас есть именно то, что я положил. </p>