Por que std :: set não tem uma função de membro “contém”?

103

Estou usando muito std::set<int>e, frequentemente, só preciso verificar se esse conjunto contém um número ou não.

Acho natural escrever:

if (myset.contains(number))
   ...

Mas, devido à falta de um containsmembro, preciso escrever o incômodo:

if (myset.find(number) != myset.end())
  ..

ou não tão óbvio:

if (myset.count(element) > 0) 
  ..

Existe uma razão para esta decisão de design?

Jabberwocky
fonte
7
A maioria da biblioteca padrão trabalha com iteradores, portanto, normalmente as funções que retornam iteradores são o que você espera. Não é muito difícil escrever uma função para abstrair isso. Muito provavelmente o compilador irá embuti-lo, pois deve ser apenas uma linha ou 2 de código e você obterá o mesmo desempenho.
NathanOliver
3
Outro problema (mais fundamental) com a count()abordagem é que ela faz mais trabalho do que countains()deveria.
Leo Heinsaar
11
A razão fundamental por trás dessa decisão de projeto é que contains()que retorna um booliria perder informações valiosas sobre onde o elemento está na coleção . find()preserva e retorna essas informações na forma de um iterador, portanto, é a melhor escolha para uma biblioteca genérica como a STL. (Isso não quer dizer que um bool contains()não seja muito bom de se ter ou mesmo necessário.)
Leo Heinsaar
3
É fácil escrever uma contains(set, element)função gratuita usando a interface pública do conjunto. Portanto, a interface do conjunto é funcionalmente completa; adicionar um método de conveniência apenas aumenta a interface sem habilitar nenhuma função adicional, o que não é o método C ++.
Toby Speight,
3
Estamos fechando tudo esses dias? Como essa pergunta é "baseada principalmente em opinião" de alguma forma?
Sr. Alien

Respostas:

148

Acho que provavelmente foi porque eles estavam tentando fazer std::sete o std::multisetmais parecido possível. (E, obviamente, counttem um significado perfeitamente sensato para std::multiset.)

Pessoalmente, acho que isso foi um erro.

Não parece tão ruim se você fingir que counté apenas um erro de ortografia containse escrever o teste como:

if (myset.count(element)) 
   ...

Ainda é uma pena.

Martin Bonner apoia Monica
fonte
5
Aliás, é exatamente a mesma coisa com mapas e multimaps (que é igualmente feio, mas menos feio do que todas essas comparações com .end()).
Matteo Italia
8
Alternativamente, eles podem não ter visto necessidade de um membro adicional contains(), com o fundamento de que seria redundante porque para qualquer std::set<T> se T t, o resultado de s.contains(t)é exatamente idêntico ao resultado de static_cast<bool>(s.count(t)). Visto que usar o valor em uma expressão condicional implicitamente o converteria em bool, eles podem ter achado que count()serviu ao propósito muito bem.
Justin Time - Reintegrar Monica
2
Erro ortográfico? if (myset.ICanHaz(element)) ...: D
Stéphane Gourichon
3
@MartinBonner Realmente não importa se os motivos para deixá-lo de fora foram idiotas. Também não importa realmente se a conversa não foi o fundamento 100% final. Sua resposta aqui é apenas um palpite razoável sobre como você acha que deveria ser. A conversa e a resposta de alguém não apenas envolvido nela, mas com a tarefa de propô-la (embora não o tenham feito) está indiscutivelmente mais perto da verdade do que essa suposição, não importa como você olhe para ela. No mínimo, você deve pelo menos mencioná-lo nesta resposta, isso seria uma grande melhoria e seria a coisa responsável a fazer.
Jason C
2
@JasonC: Você poderia prosseguir e editar uma seção na parte inferior, por favor? Eu realmente não entendo o que você está tentando fazer, e comentários provavelmente não são a melhor maneira de esclarecer isso. Obrigado!
Martin Bonner apoia Monica
44

Para ser capaz de escrever if (s.contains()), contains()deve retornar um bool(ou um tipo conversível parabool , que é outra história), como binary_searchfaz.

A razão fundamental por trás da decisão de design de não fazer isso dessa forma é que, se contains()retornasse um bool, perderia informações valiosas sobre onde o elemento está na coleção . find()preserva e retorna essas informações na forma de um iterador, portanto, é a melhor escolha para uma biblioteca genérica como a STL. Esse sempre foi o princípio orientador de Alex Stepanov, como ele sempre explicou (por exemplo, aqui ).

Quanto à count()abordagem em geral, embora geralmente seja uma solução alternativa adequada, o problema é que ela funciona mais do contains() que o necessário .

Isso não quer dizer que um bool contains()não seja muito bom ou mesmo necessário. Há algum tempo, tivemos uma longa discussão sobre esse mesmo problema no grupo ISO C ++ Standard - Future Proposals.

Leo Heinsaar
fonte
5
E é interessante notar que essa discussão terminou com quase um consenso sobre isso ser desejável e você foi convidado a escrever uma proposta para isso.
PJTraill
@PJTraill True, e o motivo pelo qual não fui em frente é que contains(), obviamente, interagiria fortemente com os contêineres e algoritmos existentes, que seriam fortemente impactados por conceitos e intervalos - na época esperada para chegar ao C ++ 17 - e Eu estava convencido (como resultado da discussão e também de algumas trocas de e-mail privadas) que seria uma ideia melhor esperar por eles primeiro. Claro, em 2015 não estava claro se nem os conceitos nem as faixas não iriam para o C ++ 17 (na verdade, havia grandes esperanças de que isso acontecesse). Não tenho certeza se vale a pena perseguir agora, no entanto.
Leo Heinsaar
1
Pois std::set(que é sobre o que a pergunta pergunta), não vejo como countfunciona mais do que containsdeveria. A implementação glibc de countis (aproximadamente) return find(value) == end() ? 0 : 1;. Além dos detalhes sobre o operador ternário vs. apenas retornar != end()(que eu esperaria que o otimizador removesse), não consigo ver como há mais trabalho.
Martin Bonner torce para Monica
4
"... contains () que retorna um bool perderia informações valiosas sobre onde o elemento está na coleção " - Se o usuário chamar myset.contains()(se existisse), isso seria uma indicação muito forte de que essa informação não é valiosa ( para o usuário nesse contexto).
Keith Thompson
1
Por que count()faz mais trabalho do que contains()deveria std::set? É único, então count()poderia ser return contains(x) ? 1 : 0;exatamente o mesmo.
Timmmm
22

Falta porque ninguém o adicionou. Ninguém o adicionou porque os contêineres do STL que a stdbiblioteca incorporou foram projetados para serem mínimos na interface. (Observe questd::string não veio do STL da mesma forma).

Se você não se importa com alguma sintaxe estranha, você pode fingir:

template<class K>
struct contains_t {
  K&& k;
  template<class C>
  friend bool operator->*( C&& c, contains_t&& ) {
    auto range = std::forward<C>(c).equal_range(std::forward<K>(k));
    return range.first != range.second;
    // faster than:
    // return std::forward<C>(c).count( std::forward<K>(k) ) != 0;
    // for multi-meows with lots of duplicates
  }
};
template<class K>
containts_t<K> contains( K&& k ) {
  return {std::forward<K>(k)};
}

usar:

if (some_set->*contains(some_element)) {
}

Basicamente, você pode escrever métodos de extensão para a maioria dos C ++ std tipos usando esta técnica.

Faz muito mais sentido apenas fazer isso:

if (some_set.count(some_element)) {
}

mas me divirto com o método do método de extensão.

O que é realmente triste é que escrever um eficiente containspode ser mais rápido em um multimapou multiset, já que eles só precisam encontrar um elemento, enquanto counttem que encontrar cada um deles e contá-los .

Um multiset contendo 1 bilhão de cópias de 7 (você sabe, no caso de você acabar) pode ter um muito lento .count(7), mas poderia ter um muito rápidocontains(7) .

Com o método de extensão acima, poderíamos torná-lo mais rápido para este caso usando lower_bound, comparando e end, em seguida, comparando com o elemento. Fazer isso para um miado não ordenado, bem como um miado ordenado, exigiria SFINAE sofisticado ou sobrecargas específicas do contêiner.

Yakk - Adam Nevraumont
fonte
2
1 bilhão de cópias de 7? E aqui eu pensei std::setque não pode conter duplicatas e, portanto std::set::count, sempre retornará 0ou 1.
nwp
5
@nwp std::multiset::countcan
milleniumbug
2
@nwp Minha falta de backtickspalavra "set" é porque não estou me referindo std::setespecificamente. Para fazer você se sentir melhor, adicionarei multi
Yakk - Adam Nevraumont
3
Parece que estou perdendo a piada para o que quer que "miau" deveria ser uma referência.
user2357112 suporta Monica
2
@ user2357112 meow é um espaço reservado para "conjunto ou mapa". Pergunte ao STL por quê.
Yakk - Adam Nevraumont
12

Você está olhando para um caso específico e não vendo o quadro geral. Conforme declarado na documentação, std::set atende aos requisitos do conceito AssociativeContainer . Para esse conceito não faz sentido ter containsmétodo, pois é praticamente inútil para std::multisete std::multimap, mas countfunciona bem para todos eles. Embora método containspode ser adicionado como um alias para countpara std::set, std::mape suas versões hash (como lengthpor size()em std::string), mas parece que os criadores da biblioteca não viu necessidade real para isso.

Slava
fonte
8
Observe que stringé um monstro: ele existia antes da STL, onde tinha lengthe todos aqueles métodos que são baseados em índice, e então foi "contentorizado" para caber no modelo STL ... sem remover os métodos existentes por razões de compatibilidade com versões anteriores . Veja GotW # 84: Monoliths Unstrung => stringrealmente viola o princípio de design da "quantidade mínima de funções membro".
Matthieu M.
5
Mas então a questão se torna "Por que vale a pena ter um conceito AssociativeContainer como esse?" - e não tenho certeza se foi.
Martin Bonner apoia Monica de
24
Perguntar se um multiset, um multimapa ou mapa contém algo faz todo o sentido para mim. Na verdade, containsé igual em esforço em um conjunto / mapa, mas pode ser feito mais rápido do que countem um multiset / multimapa.
Yakk - Adam Nevraumont
5
AssociativeContainer não exige que as classes não tenham um containsmétodo.
usuário2357112 suporta Monica
6
@Slava Isso é como dizer size()e empty()são duplicatas, mas muitos contêineres têm os dois.
Barry
10

Embora eu não saiba por std::setque não tem, containsmas countque sempre retorna 0ou 1, você pode escrever uma containsfunção auxiliar modelada como esta:

template<class Container, class T>
auto contains(const Container& v, const T& x)
-> decltype(v.find(x) != v.end())
{
    return v.find(x) != v.end();
}

E use-o assim:

    if (contains(myset, element)) ...
enferrujado
fonte
3
-1, porque isso é diretamente contradito pelo fato de que de fato o containsmétodo existe, ele é apenas nomeado de maneira estúpida.
Matteo Italia
4
"Os esforça STL para oferecer uma interface mínima" chough std::string tosse
bolov
6
@bolov: qual é o seu ponto? std.::stringNÃO faz parte do STL! Faz parte da biblioteca padrão e foi modelado retroativamente ...
MFH
3
@MatteoItalia countpode ser mais lento, pois efetivamente precisa fazer dois finds para obter o início e o fim do intervalo se o código for compartilhado com multiset.
Mark Ransom
2
O OP já sabe que é redundante, mas aparentemente deseja que o código seja lido explicitamente contains. Não vejo nada de errado nisso. @MarkRansom o pequeno SFINAE é para evitar que este template se vincule a coisas que não deveria.
rustyx 01 de
7

O verdadeiro motivo de seté um mistério para mim, mas uma possível explicação para esse mesmo design no mappoderia ser evitar que as pessoas escrevam códigos ineficientes por acidente:

if (myMap.contains("Meaning of universe"))
{
    myMap["Meaning of universe"] = 42;
}

O que resultaria em duas mappesquisas.

Em vez disso, você é forçado a obter um iterador. Isso dá uma dica mental de que você deve reutilizar o iterador:

auto position = myMap.find("Meaning of universe");
if (position != myMap.cend())
{
    position->second = 42;
}

que consome apenas uma mappesquisa.

Quando percebemos isso sete mapsomos feitos da mesma carne, podemos aplicar esse princípio também para set. Ou seja, se quisermos atuar em um item no setsomente se ele estiver presente no set, esse design pode nos impedir de escrever código como este:

struct Dog
{
    std::string name;
    void bark();
}

operator <(Dog left, Dog right)
{
    return left.name < right.name;
}

std::set<Dog> dogs;
...
if (dogs.contain("Husky"))
{
    dogs.find("Husky")->bark();
}

Claro que tudo isso é mera especulação.

Martin Drozdik
fonte
1
Sim, mas para conjuntos de ints isso não se aplica.
Jabberwocky
7
Exceto que as pessoas podem escrever if (myMap.count("Meaning of universe"))muito bem, então ...?
Barry
@MichaelWalz Oops, você está certo. Modifiquei minha resposta para incluir também o exemplo definido. No entanto, o raciocínio para um conjunto de ints é um mistério para mim.
Martin Drozdik 01 de
2
Isso não pode estar certo. Eles podem escrever seu código ineficiente com a mesma facilidade containscom count.
Martin Bonner apoia Monica de
2

Desde c ++ 20,

bool contains( const Key& key ) const

está disponível.

Andy
fonte
0

E sobre binary_search?

 set <int> set1;
 set1.insert(10);
 set1.insert(40);
 set1.insert(30);
 if(std::binary_search(set1.begin(),set1.end(),30))
     bool found=true;
Massimiliano Di Cavio
fonte
Não funcionaria para std::unordered_set, mas funcionaria std::set.
Jabberwocky
É normal, binary_search funciona apenas para árvores binárias.
Massimiliano Di Cavio
0

contains () deve retornar um bool. Usando o compilador C ++ 20, obtenho a seguinte saída para o código:

#include<iostream>
#include<map>
using namespace std;

int main()
{
    multimap<char,int>mulmap;
    mulmap.insert(make_pair('a', 1)); //multiple similar key
    mulmap.insert(make_pair('a', 2)); //multiple similar key
    mulmap.insert(make_pair('a', 3)); //multiple similar key
    mulmap.insert(make_pair('b', 3));
    mulmap.insert({'a',4});
    mulmap.insert(pair<char,int>('a', 4));
    
    cout<<mulmap.contains('c')<<endl;  //Output:0 as it doesn't exist
    cout<<mulmap.contains('b')<<endl;  //Output:1 as it exist
}
bashar
fonte
-1

Outra razão é que isso daria a um programador a falsa impressão de que std :: set é um conjunto no sentido da teoria matemática dos conjuntos. Se eles implementassem isso, então muitas outras questões se seguiriam: se um std :: set tem contains () para um valor, por que não tem para outro conjunto? Onde estão union (), intersection () e outras operações de conjunto e predicados?

A resposta é, obviamente, que algumas das operações de conjunto já estão implementadas como funções em (std :: set_union () etc.) e outras são tão trivialmente implementadas como contains (). Funções e objetos de função funcionam melhor com abstrações matemáticas do que membros de objeto e não estão limitados ao tipo de contêiner específico.

Se alguém precisa implementar uma funcionalidade de conjunto matemático completo, ele não tem apenas uma escolha de contêiner subjacente, mas também uma escolha de detalhes de implementação, por exemplo, sua função teoria_union () funcionaria com objetos imutáveis, mais adequados para programação funcional , ou modificaria seus operandos e economizaria memória? Seria implementado como objeto de função desde o início ou seria melhor implementar uma função C e usar std :: function <> se necessário?

Como está agora, std :: set é apenas um contêiner, bem adequado para a implementação de set no sentido matemático, mas está quase tão longe de ser um conjunto teórico quanto std :: vector de ser um vetor teórico.

Mike Tyukanov
fonte