O que são comparadores transparentes?

106

No C ++ 14, os contêineres associativos parecem ter mudado do C ++ 11 - [associative.reqmts] / 13 diz:

Os modelos de função de membro find, count, lower_bound, upper_bound, e equal_rangenão devem participar de resolução de sobrecarga, a menos que o tipo Compare::is_transparentexiste.

Qual é o objetivo de tornar um comparador "transparente"?

C ++ 14 também fornece modelos de biblioteca como este:

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

Assim, por exemplo, std::set<T, std::less<T>>que não têm um comparador transparente, mas std::set<T, std::less<>> se tiver um.

Que problema isso resolve e muda a forma como os contêineres padrão funcionam? Por exemplo, os parâmetros do modelo de std::setainda são Key, Compare = std::less<Key>, ..., de modo que o conjunto padrão perder seus find, countetc. membros?

Kerrek SB
fonte
Por exemplo, consulte esta descrição de preferência . E estou me sentindo estúpido agora, porque não estou observando a palavra " modelo de função de membro " ...
Kerrek SB
5
Possivelmente relacionado: stackoverflow.com/questions/18939882/…
cppreference também tem uma sinopse em en.cppreference.com/w/cpp/utility/functional/less_void
Cubbi

Respostas:

60

Que problema isso resolve,

Veja a resposta de Dietmar e resposta de remyabel .

e isso muda a forma como os contêineres padrão funcionam?

Não, não por padrão.

As novas sobrecargas de modelo de função de membro findetc. permitem que você use um tipo que é comparável à chave do contêiner, em vez de usar o próprio tipo de chave. Veja N3465 de Joaquín Mª López Muñoz para justificativa e uma proposta detalhada e cuidadosamente escrita para adicionar este recurso.

Na reunião de Bristol, o LWG concordou que o recurso de pesquisa heterogênea era útil e desejável, mas não podíamos ter certeza de que a proposta de Joaquín seria segura em todos os casos. A proposta do N3465 teria causado sérios problemas para alguns programas (consulte a seção Impacto no código existente ). Joaquín preparou um projeto de proposta atualizado com algumas implementações alternativas com diferentes compensações, o que foi muito útil para ajudar o LWG a entender os prós e os contras, mas todos corriam o risco de quebrar alguns programas de alguma forma, então não houve consenso para adicionar o recurso. Decidimos que, embora não seja seguro adicionar o recurso incondicionalmente, seria seguro se fosse desabilitado por padrão e apenas "opt in".

A principal diferença da proposta do N3657 (que foi uma revisão de última hora por mim e STL com base no N3465 e um rascunho não publicado posteriormente por Joaquín) foi adicionar o is_transparenttipo como o protocolo que pode ser usado para optar pela nova funcionalidade.

Se você não usar um "functor transparente" (ou seja, um que defina um is_transparenttipo), os contêineres se comportam da mesma forma que sempre, e esse ainda é o padrão.

Se você escolher usar std::less<>(o que é novo para C ++ 14) ou outro tipo de "functor transparente", obterá a nova funcionalidade.

Usar std::less<>é fácil com modelos de alias:

template<typename T, typename Cmp = std::less<>, typename Alloc = std::allocator<T>>
  using set = std::set<T, Cmp, Alloc>;

O nome is_transparentvem do N3421 da STL que adicionou os "operadores de diamante" ao C ++ 14. Um "functor transparente" é aquele que aceita qualquer tipo de argumento (que não precisa ser o mesmo) e simplesmente encaminha esses argumentos para outro operador. Tal functor passa a ser exatamente o que você deseja para pesquisa heterogênea em containers associativos, então o tipo is_transparentfoi adicionado a todos os operadores de diamante e usado como o tipo de tag para indicar que a nova funcionalidade deve ser habilitada em containers associativos. Tecnicamente, os contêineres não precisam de um "functor transparente", apenas um que suporte chamá-lo com tipos heterogêneos (por exemplo, o pointer_comptipo em https://stackoverflow.com/a/18940595/981959 não é transparente de acordo com a definição do STL,pointer_comp::is_transparentpermite que seja usado para resolver o problema). Se você apenas pesquisa em seu std::set<T, C>com chaves do tipo Tou intentão Csó precisa ser chamado com argumentos do tipo Te int(em qualquer ordem), não precisa ser verdadeiramente transparente. Usamos esse nome em parte porque não poderíamos encontrar um nome melhor (eu teria preferido is_polymorphicporque esses functores usam polimorfismo estático, mas já existe um std::is_polymorphictraço de tipo que se refere ao polimorfismo dinâmico).

Jonathan Wakely
fonte
3
Ei, foi você a quem STL disse: "Claro que você pode fazer dedução de argumento de modelo em sua cabeça" na conversa Woolstar ligada?
Kerrek SB
10
Não, eu não estava lá, mas há pessoas com muito mais compiladores compatíveis em suas cabeças do que eu :)
Jonathan Wakely
Acho que "operador de diamante" se refere <>na proposta vinculada, mas essa proposta não foi introduzida <>- é a sintaxe existente para uma lista de parâmetros de modelo vazia. "Functores de operador de diamante" seria um pouco menos confuso.
Qwertie
33

Em C ++ 11 não existem modelos de membros find(), lower_bound()etc. Ou seja, nada é perdido por esta mudança. Os modelos de membro foram introduzidos com o n3657 para permitir o uso de chaves heterogêneas com os contêineres associativos. Não vejo nenhum exemplo concreto em que isso seja útil, exceto o exemplo que é bom e ruim!

O is_transparentuso destina-se a evitar conversões indesejadas. Se os modelos de membro não tivessem restrições, o código existente poderia passar por objetos diretamente que teriam sido convertidos sem os modelos de membro. O caso de uso de exemplo de n3657 é localizar um objeto em um std::set<std::string>literal de string usando: com a definição do C ++ 11, um std::stringobjeto é construído ao passar literais de string para a função de membro correspondente. Com a mudança, é possível usar o literal de string diretamente. Se o objeto de função de comparação subjacente for implementado exclusivamente em termos std::stringdisso, isso é ruim porque agora um std::stringseria criado para cada comparação. Por outro lado, se o objeto de função de comparação subjacente pode levar umstd::string e um literal de string, que pode evitar a construção de um objeto temporário.

O is_transparenttipo aninhado no objeto de função de comparação fornece uma maneira de especificar se a função de membro modelada deve ser usada: se o objeto de função de comparação pode lidar com argumentos heterogêneos, ele define esse tipo para indicar que ele pode lidar com argumentos diferentes de forma eficiente. Por exemplo, os novos objetos de função de operador apenas delegam operator<()e afirmam ser transparentes. Isso, pelo menos, funciona para o std::stringque tem sobrecarregado menos do que os operadores tomando char const*como argumento. Uma vez que esses objetos de função também são novos, mesmo que façam a coisa errada (ou seja, exijam uma conversão para algum tipo), não seria, pelo menos, uma mudança silenciosa resultando em uma degradação do desempenho.

Dietmar Kühl
fonte
Obrigado - veja meu comentário sobre a outra questão: Você obtém o comportamento transparente por padrão?
Kerrek SB
8
@KerrekSB: o comportamento transparente é habilitado quando is_transparenté definido no objeto de função de comparação de acordo com 23.2.4 [associative.reqmts] parágrafo 13. Os objetos de função de comparação padrão estão de std::less<Key>acordo com 23.4.2 [associative.map.syn] e 23.4. 3 [associative.set.syn]. De acordo com 20.10.5 [de comparação] parágrafo 4 o modelo geral para std::less<...>que não definem um tipo aninhado is_transparentmas a std::less<void>especialização faz. Ou seja, não, você não obtém um operador transparente por padrão.
Dietmar Kühl
Você tem alguma ideia do nome? Quero dizer por quê is_transparent?
plasmacel
Você quer um "exemplo concreto em que isso seja útil"? Este é meu caso de uso
spraff de
19

O seguinte é todo copy-pasta do n3657 .

P. Qual é o objetivo de tornar um comparador "transparente"?

A. As funções de pesquisa de contêiner associativo (find, lower_bound, upper_bound, equal_range) só aceitam um argumento de key_type, exigindo que os usuários construam (implícita ou explicitamente) um objeto de key_type para fazer a pesquisa. Isso pode ser caro, por exemplo, construir um objeto grande para pesquisar em um conjunto quando a função comparadora olha apenas para um campo do objeto. Há um grande desejo entre os usuários de poder pesquisar usando outros tipos que sejam comparáveis ​​ao key_type.

P. Que problema isso resolve

A. O LWG tinha preocupações sobre códigos como o seguinte:

std::set<std::string> s = /* ... */;
s.find("key");

No C ++ 11, isso construirá uma única std :: string temporária e a comparará com os elementos para encontrar a chave.

Com a mudança proposta por N3465, a função std :: set :: find () seria um modelo irrestrito que passaria o const char * através da função comparadora, std :: less, que construiria uma std :: string temporária para cada comparação. O LWG considerou esse problema de desempenho um problema sério. A função find () do template também evita encontrar NULL em um contêiner de ponteiros, o que faz com que o código anteriormente válido não seja mais compilado, mas isso foi visto como um problema menos sério do que a regressão silenciosa de desempenho

P. isso muda como os contêineres padrão funcionam

A. Esta proposta modifica os contêineres associativos e sobrecarregando as funções de membro de pesquisa com modelos de função de membro. Não há mudanças de idioma.

Q. assim, o conjunto padrão perde seus membros find, count, etc.

R. Quase todo o código C ++ 11 existente não é afetado porque as funções de membro não estão presentes, a menos que novos recursos da biblioteca C ++ 14 sejam usados ​​como funções de comparação.

Para citar Yakk ,

Em C ++ 14, std :: set :: find é uma função de template se Compare :: is_transparent existir. O tipo que você passa não precisa ser chave, apenas equivalente no seu comparador.

e n3657,

Adicione o parágrafo 13 em 23.2.4 [associative.reqmts]: Os modelos de função de membro find, lower_bound, upper_bound e equal_range não devem participar da resolução de sobrecarga, a menos que o tipo Compare :: is_transparent não existe exista.

n3421 fornece um exemplo de " Funções de operador transparentes" .

O código completo está aqui .

Comunidade
fonte
1
Será que std::set<std::string>realmente beneficiar de "passar o char const *meio", ou que você precisa para fazer um std::set<std::string, std::less<>>?
Kerrek SB
@Kerrek Acho que "passar o char const *" era o problema que eles estavam tentando evitar, se não me engano. Observe o texto:With the change proposed by N3465 the std::set::find() function would be an unconstrained template which would pass the const char* through to the comparator function, std::less<std::string>, which would construct a std::string temporary for every comparison. The LWG considered this performance problem to be a serious issue.
A sua citação e a minha do parágrafo 13 dizem o contrário: "a menos que o tipo exista / não exista" ...?!
Kerrek SB
4
@KerrekSB, isso é minha culpa, N3657 deveria dizer "existe", mas eu escrevi "não existe" ... foi um artigo recente escrito no último minuto. O rascunho da norma está correto.
Jonathan Wakely
3
Sim, pode ser mais claro citar o que eu quis dizer, não o que eu realmente disse na época :)
Jonathan Wakely
7

Stephan T Lavavej fala sobre problemas em que o compilador continua criando temporários, e como sua proposta de functores de operador transparentes resolverá isso em c ++ 1y

GoingNative 2013 - Não ajude o compilador (por volta da marca de uma hora)

Woolstar
fonte