Como colocar objetos que não parecem ser comparáveis ​​em um std C ++ :: set?

votos
2

Suponha que eu queira colocar objetos que identificam um servidor em um stl set. Então eu teria que ter certeza que eu também implementar operator<para esses objetos, caso contrário eu seria executado em um erro do compilador:

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

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

Este é apenas um exemplo de um problema comum onde eu quero fazer um objeto comparável.

Minha solução atual geralmente é assim:

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

Esta é apenas uma solução que me encontrava. Mas eu suspeito que este problema pode também foram reconhecidos em ciência da computação. Então, se eu tiver sorte há uma solução melhor para isso. Alguém pode me sugerir no sentido de que?

Publicado 26/08/2009 em 22:53
fonte usuário
Em outras línguas...                            


9 respostas

votos
14

Eu recomendaria não implementá-lo como operador <, para evitar possíveis confusões, mas sim passar a função de ordem como um parâmetro para o argumento de modelo std :: set.

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

Sobre a questão de saber se este problema foi identificado antes, ele tem. A solução geral é exatamente o que você postou: ordem lexicográfica . Embora o termo é normalmente referido ordenamento string, mas a ordem é a mesma: dar o primeiro elemento, comparar se não definir uma ordem dar o próximo elemento de dados e interagir.

Respondeu 26/08/2009 em 23:27
fonte usuário

votos
4

Tua é a solução canónica. Eu não sei como você pôde gostar de fazê-lo de uma forma que seria melhor.

Para expandir sobre isso, se você tem nmembros de sua classe que você vai achar que você tem que comparar um número destes campos, a fim de estabelecer uma ordenação estrita. Não há nenhuma maneira real de contornar isso, mas você pode achar que é possível fazer a função de comparação melhor desempenho (em termos de complexidade média), se você pedir as comparações de modo que os que são mais propensos a contribuir para o sucesso da a comparação virá primeiro. Isto ajuda-o a abandonar a comparação mais rápido.

A possibilidade de que pode ajudar em algumas circunstâncias (se você achar que o desempenho é dominado por comparações) é estabelecer uma "chave de ordenação" - cordas comparando pode ser caro. A chave de ordenação é um número inteiro que pode ser usado para fazer uma comparação rápida dos objetos. Se a chave de ordenação compara menor que, em seguida, a corda faria também.

No seu caso, uma chave de classificação simplista pode envolver o tratamento a representação binária das cordas como inteiros - este tem muitos erros pelo caminho - e em seguida, comparando os números inteiros em vez das cordas.

No Windows, o LCMapString função pode ser usada para produzir uma chave de classificação para cordas em desta forma. Eu acho que você pode usar uma função rápido gosto memcmpde comparar as cordas em vez de uma comparação de string mais lento. Isso é mais útil se você estaria fazendo caso comparações insensíveis ou usando a gama completa de caracteres Unicode e queria comparações corretas de acordo com suas regras.

Respondeu 26/08/2009 em 22:57
fonte usuário

votos
3

eu usaria 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);
}

Se isso não faz sentido para você tê-lo comparável, eo único uso desse seria enchê-lo em o set, você pode usar um functor

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;

Se você porém fornecer ao operador independente (não usando o functor) como acima, então também fornecem <=, ==, >=e !=para mantê-lo consistente.

Respondeu 27/08/2009 em 02:03
fonte usuário

votos
3

Eu costumo escrever como:

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

... que você pode continuar a se expandir para o maior número de variáveis ​​de membro que você tem. Esta solução é em curto-circuito o mais rápido possível e elimina ramificação.

Note que este exige operator<ser definida para cada uma das variáveis de membro, o que é uma boa coisa para ter implementado fora dessa rotina de qualquer maneira.

Respondeu 26/08/2009 em 22:58
fonte usuário

votos
2

Neste caso, se a ordem não importa que você pode querer comparar o porto antes da seqüência devido ao custo de uma comparação de cadeia.

Respondeu 26/08/2009 em 23:06
fonte usuário

votos
2

Se tudo que você precisa é de uma ordem bem, e você não se importa uma forma ou de outra o que essa ordem é, em seguida, a solução é muito bem.

Respondeu 26/08/2009 em 22:57
fonte usuário

votos
2

No final do dia, você simplesmente tem que vir para cima com uma função de comparação que atenda às suas necessidades imediatas. Isso pode ser difícil - por exemplo, como você compararia dois bitmaps de diferentes tamanhos?

Respondeu 26/08/2009 em 22:56
fonte usuário

votos
0

Sua solução é praticamente o caminho certo para fazê-lo. Sua função de comparação deve ser configurado para identificar cada servidor (o que isso significa, na verdade, depende do seu caso de uso), então comparando nome / porto é provavelmente suficiente.

Se você sabe que você não vai ter dois servidores com o mesmo nome mas diferentes portas (ou você gostaria de tratá-los da mesma), então você pode deixar cair essa parte de sua função de comparação. Um exemplo mais realista seria se você tivesse mais membros em seu objeto de servidor que não têm a ver com a identidade do servidor em si (por exemplo, uma "última-request" cache); neste caso, você provavelmente não quer que seu conjunto de distinguir com base neste campo, para que você não incluí-lo em sua função de comparação. OTOH, isso pode não ser o melhor projeto para o objeto do servidor de qualquer maneira.

Se você está encontrando dificuldades para responder à pergunta "Quando deve dois servidores (objetos) ser considerados idênticos?" então você não pode realmente precisa de um conjunto de todo.

Respondeu 26/08/2009 em 23:17
fonte usuário

votos
0

I tendem a colocar o operador <dentro da estrutura para manter as coisas mais puro, mas por outro lado você tem exatamente o que eu coloquei.

Respondeu 26/08/2009 em 22:58
fonte usuário

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