Comment placer des objets qui semblent ne pas être comparables dans un C ++ std :: set?

voix
2

Supposons que je veux mettre des objets qui permettent d' identifier un serveur dans un stl set. Ensuite , je dois vous assurer que je mets en œuvre aussi operator<pour ces objets , sinon je courrais dans une erreur de compilation:

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

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

Ceci est juste un exemple d'un problème commun où je veux faire un objet comparable.

Ma solution actuelle va généralement comme ceci:

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

Ceci est juste une solution que je me suis retrouvé. Mais je pense que ce problème pourrait aussi avoir été reconnu dans la science informatique. Donc, si je suis chanceux il y a une meilleure solution pour cela. Quelqu'un peut-il me faire allusion à cela?

Créé 26/08/2009 à 22:53
source utilisateur
Dans d'autres langues...                            


9 réponses

voix
14

Je ne recommanderais pas la mise en œuvre comme opérateur <, pour éviter toute confusion possible, mais passe plutôt la fonction de commande en tant que paramètre à l'argument modèle défini std ::.

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

A propos de la question de savoir si ce problème a été identifié avant, il a. La solution générale est exactement ce que vous avez publié: ordre lexicographique . Bien que le terme est généralement appelé à la commande de chaîne, mais l'ordre est le même: prendre le premier élément, comparer si elle ne définit pas une commande prendre le prochain élément de données et itérer.

Créé 26/08/2009 à 23:27
source utilisateur

voix
4

Le vôtre est la solution canonique. Je ne sais pas comment vous pourriez vous le faire d'une manière qui serait mieux.

Pour développer sur ce point , si vous avez des nmembres de votre classe , vous constaterez que vous devez comparer un certain nombre de ces domaines afin d'établir un ordre strict. Il n'y a pas vraie solution, bien que vous trouverez peut - être qu'il est possible de rendre la fonction de comparaison de meilleurs résultats (en termes de complexité moyenne) , si vous commandez les comparaisons afin que ceux qui sont plus susceptibles de contribuer à la réussite de la comparaison viendra en premier. Cela contribue à abandonner la comparaison plus rapide.

Une possibilité qui peut aider dans certaines circonstances (si vous trouvez que la performance est dominé par des comparaisons) est d'établir une « clé de tri » - cordes comparaison peuvent être coûteux. Une clé de tri est un entier qui peut être utilisé pour faire une comparaison rapide des objets. Si la clé de tri compare moins, la chaîne ferait aussi.

Dans votre cas, une clé de tri simpliste peut impliquer le traitement de la représentation binaire des chaînes comme entiers - ce qui a de nombreux bugs de la manière - et compare ensuite les entiers au lieu des cordes.

Sous Windows, la LCMapString fonction peut être utilisée pour produire une clé de tri pour les chaînes de cette façon. Je pense que vous pouvez utiliser une fonction rapide comme memcmppour comparer les chaînes au lieu d'une comparaison de chaînes plus lente. Ceci est plus utile si vous rendriez cas des comparaisons insensibles ou en utilisant la gamme complète de caractères unicode et je voulais corriger des comparaisons en fonction de leurs règles.

Créé 26/08/2009 à 22:57
source utilisateur

voix
3

j'utiliserais 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);
}

Si elle n'a pas de sens pour vous d'avoir comparable, et l'utilisation que cela serait à farcir dans la set, vous pouvez utiliser un foncteur

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;

Si vous fournissez cependant l'opérateur indépendant (ne pas utiliser le foncteur) comme ci - dessus, prévoirait également <=, ==, >=et !=de le garder cohérent.

Créé 27/08/2009 à 02:03
source utilisateur

voix
3

Je l'habitude d'écrire comme:

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

... que vous pouvez continuer à se développer pour autant de variables membres que vous avez. Cette solution est court-circuité le plus tôt possible et élimine la ramification.

Notez que cela nécessite de operator<définir pour chacune des variables membres, ce qui est une bonne chose d'avoir mis en œuvre en dehors de cette routine de toute façon.

Créé 26/08/2009 à 22:58
source utilisateur

voix
2

Dans ce cas, si l'ordre n'a pas d'importance que vous pouvez comparer le port avant la chaîne en raison du coût d'une comparaison de chaînes.

Créé 26/08/2009 à 23:06
source utilisateur

voix
2

Si tout ce que vous avez besoin est un bien pour, et vous ne se soucient pas d'une façon ou l'autre ce que l'ordre est, votre solution est très bien.

Créé 26/08/2009 à 22:57
source utilisateur

voix
2

A la fin de la journée, il vous suffit de trouver une fonction de comparaison qui répond à vos besoins immédiats. Cela peut être difficile - par exemple, comment voulez-vous comparer deux bitmaps de différentes tailles?

Créé 26/08/2009 à 22:56
source utilisateur

voix
0

Votre solution est à peu près la bonne façon de le faire. Votre fonction de comparaison devrait être mis en place pour identifier chaque serveur (ce que cela signifie en fait dépend de votre cas d'utilisation), si l'on compare le nom / port est probablement suffisant.

Si vous savez que vous ne serez pas avoir deux serveurs avec le même nom mais différents ports (ou vous voulez traiter ces même), alors vous pouvez déposer cette partie de votre fonction de comparaison. Un exemple plus réaliste serait si vous aviez plus de membres dans votre objet serveur qui n'ont à voir avec l'identité du serveur lui-même (par exemple un cache « dernière demande »); dans ce cas, vous auriez probablement pas que votre ensemble à distinguer en fonction de ce domaine, de sorte que vous ne seriez pas l'inclure dans votre fonction de comparaison. OTOH, cela peut ne pas être la meilleure conception de l'objet serveur de toute façon.

Si vous trouvez qu'il est difficile de répondre à la question « Quand faut-deux serveurs (objets) sont considérés comme identiques? » alors vous ne pouvez pas vraiment besoin d'un ensemble du tout.

Créé 26/08/2009 à 23:17
source utilisateur

voix
0

J'ai tendance à mettre l'opérateur <à l'intérieur du struct de garder les choses plus propre, mais sinon vous avez exactement ce que je mets.

Créé 26/08/2009 à 22:58
source utilisateur

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more