Jak umístit objekty, které se zdají být srovnatelná nejen v C ++ std :: set?

hlasů
2

Dejme tomu, že chci, aby objekty, které identifikují server na STK set. Pak bych se ujistit, že jsem také implementovat operator<pro tyto objekty, jinak bych narazit na chyby kompilátoru:

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

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

To je jen jeden z příkladů, společný problém, kde chci, aby se objekt srovnatelné.

Můj současný řešení obvykle vypadá takto:

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

To je jen řešení, které jsem se ocitla. Ale mám podezření, že tento problém by mohl také byly uznány v informatice. Takže pokud budu mít štěstí, že je lepší řešení pro toto. Může mi někdo naznačují mě na to?

Položena 26/08/2009 v 22:53
zdroj uživatelem
V jiných jazycích...                            


9 odpovědí

hlasů
14

Doporučil bych neprovádí jako operátor <, aby se předešlo možnému nedorozumění, ale předat funkci objednávky jako parametr std :: set šablona argument.

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

O otázce, zda byl tento problém předtím identifikována, že má. Obecné řešení je přesně to, co jste psali: lexikografické pořadí . Zatímco termín je obvykle označován řetězec objednávání, ale uspořádání je stejný: učinit první prvek, porovná-li to nedefinuje objednávku učinit další datový prvek a iterovat.

Odpovězeno 26/08/2009 v 23:27
zdroj uživatelem

hlasů
4

Yours je kanonická řešení. Nejsem si jistý, jak byste chtěli, aby to takovým způsobem, který by byl lepší.

Rozšířit o tom, jestli máte nčlenů ve své třídě, zjistíte, že budete muset srovnat určitý počet těchto oblastech s cílem zavést přísný uspořádání. Neexistuje žádný skutečný způsob, jak vyřešit tento problém, i když možná zjistí, že je možné, aby funkci srovnání dosahují lepších výsledků (co se týče průměrné složitosti), pokud si objednáte porovnání tak, že ty, které jsou více pravděpodobné, že přispějí k úspěchu srovnání bude na prvním místě. To pomáhá, aby vypadnout z porovnání rychlejší.

Jednou z možností, které mohou pomoci v některých případech (pokud zjistíte, že výkon je ovládán srovnání) je vytvořit „třídící klíč“ - Srovnání řetězce mohou být drahé. Jakési klíč je celé číslo, které může být použito k tomu rychlý srovnání objektů. Pokud je klíč sort porovnává nižší než, pak řetězec bude dělat také.

Ve vašem případě, zjednodušující řadící klíč může zahrnovat léčbu binární reprezentaci strun jako celá čísla - to má mnoho chyb mimochodem - a pak porovnávající celá čísla namísto strun.

Ve Windows LCMapString funkci lze použít k výrobě třídící klíč pro řetězce tímto způsobem. Myslím, že pak můžete použít funkce rychlého chtěli memcmpporovnat struny namísto pomalejšího porovnání řetězců. To je užitečné, pokud bude dělat malá a velká písmena porovnání nebo pomocí celé řady unicode znaky a chtěl správné srovnání podle jejich pravidel.

Odpovězeno 26/08/2009 v 22:57
zdroj uživatelem

hlasů
3

Chtěl bych použít 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);
}

Pokud to nemá smysl na vás, abyste si to srovnatelné, a jediné využití, které by ji nacpat do set, můžete použít funktor

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;

Máte-li však zajistit, aby nezávislý provozovatel (nepoužíváte funktor), jako je uvedeno výše, a pak také <=, ==, >=a !=aby to konzistentní.

Odpovězeno 27/08/2009 v 02:03
zdroj uživatelem

hlasů
3

Obvykle jsem to napsat jako:

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

... které si můžete i nadále rozšiřovat tak mnoha členských proměnných, které jste. Toto řešení je zkratovat co nejdříve a eliminuje větvení.

Všimněte si, že to vyžaduje operator<být definována pro každý z členských proměnných, což je dobrá věc, zavedly mimo této rutiny v každém případě.

Odpovězeno 26/08/2009 v 22:58
zdroj uživatelem

hlasů
2

V tomto případě, pokud je objednávka nevadí vám mohou chtít porovnat port před řetězec v důsledku nákladů na porovnání řetězců.

Odpovězeno 26/08/2009 v 23:06
zdroj uživatelem

hlasů
2

Pokud vše, co potřebujete, je dobře pořadí, a je vám to jedno jednu nebo na druhou stranu to, že objednávka, pak se vaše řešení je v pořádku.

Odpovězeno 26/08/2009 v 22:57
zdroj uživatelem

hlasů
2

Na konci dne, se prostě musí přijít s funkcí srovnávání, který splňuje vaše okamžité potřeby. To může být obtížné - například, jak byste porovnat dvě bitmapy různých velikostí?

Odpovězeno 26/08/2009 v 22:56
zdroj uživatelem

hlasů
0

Vaše řešení je do značné míry správný způsob, jak to udělat. Váš srovnání funkce by měl být nastaven tak, aby jednoznačně identifikovat každý server (co to ve skutečnosti znamená, že záleží na vaší use-case), takže ve srovnání jméno / port je pravděpodobně dostačující.

Pokud víte, že nebudete mít dva servery se stejným názvem, ale různých portech (nebo byste chtěli léčit tyto stejné), pak můžete odevzdat, že část vašeho porovnání funkce. Realističtější příklad by bylo, kdyby jste měli více členů ve svém objektu serveru, které nebyly mají co do činění s identitou serveru samotném (například „last-request“ Cache); V tomto případě pravděpodobně nebude chtít svůj set odlišit na základě této oblasti, takže byste jej zahrnout do vaší porovnání funkcí. OTOH, nemusí to být nejlepší design pro objekt serveru stejně.

Pokud jste zjišťují, že je těžké odpovědět na otázku „Kdy by dva servery (objekty) považovat za totožné?“ pak nemusí být ve skutečnosti potřebovat sadu vůbec.

Odpovězeno 26/08/2009 v 23:17
zdroj uživatelem

hlasů
0

Mám ve zvyku dát operátor <uvnitř struct, aby to krásnější, ale jinak budete mít přesně to, co jsem dal.

Odpovězeno 26/08/2009 v 22:58
zdroj uživatelem

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