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

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?

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.

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.

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.

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.

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)) ...

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.

Desde c ++ 20,

bool contains( const Key& key ) const

está disponível.

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;

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
}

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.