¿Por qué std :: set no tiene una función miembro "contiene"?

Lo uso mucho std::set<int>y, a menudo, simplemente necesito verificar si dicho conjunto contiene un número o no.

Me resultaría natural escribir:

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

Pero debido a la falta de un containsmiembro, necesito escribir lo engorroso:

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

o lo no tan obvio:

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

¿Hay alguna razón para esta decisión de diseño?

Creo que probablemente fue porque estaban tratando de hacer std::sety lo std::multisetmás similar posible. (Y obviamente counttiene un significado perfectamente sensato para std::multiset).

Personalmente creo que esto fue un error.

No se ve tan mal si finge que countes solo un error ortográfico containsy escribe la prueba como:

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

Sin embargo, sigue siendo una pena.

Para poder escribir if (s.contains()), contains()tiene que devolver un bool(o un tipo convertible a bool, que es otra historia), como binary_searchhace.

La razón fundamental detrás de la decisión de diseño de no hacerlo de esta manera es que, si se contains()devuelve, boolse perdería información valiosa sobre dónde se encuentra el elemento en la colección . find()conserva y devuelve esa información en forma de iterador, por lo que es una mejor opción para una biblioteca genérica como STL. Este ha sido siempre el principio rector de Alex Stepanov, como ha explicado a menudo (por ejemplo, aquí ).

En cuanto al count()enfoque en general, aunque a menudo es una buena solución, el problema es que hace más trabajo del que contains() tendría que hacer .

Eso no quiere decir que bool contains()no sea muy agradable tener o incluso necesario. Hace un tiempo tuvimos una larga discusión sobre este mismo tema en el grupo ISO C ++ Standard - Future Proposals.

Le falta porque nadie lo agregó. Nadie lo agregó porque los contenedores del STL que stdincorporó la biblioteca estaban diseñados para ser mínimos en la interfaz. (Tenga en cuenta que std::stringno provino de la STL de la misma manera).

Si no le importa una sintaxis extraña, puede fingirla:

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

utilizar:

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

Básicamente, puede escribir métodos de extensión para la mayoría de los stdtipos de C ++ utilizando esta técnica.

Tiene mucho más sentido hacer esto:

if (some_set.count(some_element)) {
}

pero me divierte el método del método de extensión.

Lo realmente triste es que escribir un eficiente containspodría ser más rápido en un multimapo multiset, ya que solo tienen que encontrar un elemento, mientras que counttienen que encontrar cada uno de ellos y contarlos .

Un multiset que contenga mil millones de copias de 7 (ya sabes, en caso de que te quedes sin) puede tener una muy lenta .count(7), pero podría tener una muy rápida contains(7).

Con el método de extensión anterior, podríamos hacerlo más rápido para este caso usando lower_bound, comparando endy luego comparando con el elemento. Sin embargo, hacer eso para un maullido desordenado y ordenado requeriría un SFINAE elegante o sobrecargas específicas del contenedor.

Estás mirando un caso particular y no ves un panorama más amplio. Como se indica en la documentación, std::set cumple con los requisitos del concepto AssociativeContainer . Para ese concepto no tiene ningún sentido tener un containsmétodo, ya que es bastante inútil para std::multisety std::multimap, pero countfunciona bien para todos ellos. Aunque el método containspodría añadirse como un alias para countpara std::set, std::mapy sus versiones hash (como lengthpor size()en std::string), pero se parece a los creadores de la biblioteca no vio necesidad real para ello.

Aunque no sé por qué std::setno tiene containspero countque solo regresa 0o 1, puede escribir una containsfunción de ayuda con plantilla 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();
}

Y utilícelo así:

    if (contains(myset, element)) ...

La verdadera razón setes un misterio para mí, pero una posible explicación para este mismo diseño mappodría ser evitar que las personas escriban código ineficiente por accidente:

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

Lo que resultaría en dos mapbúsquedas.

En cambio, se ve obligado a obtener un iterador. Esto le da una pista mental de que debe reutilizar el iterador:

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

que consume solo una mapbúsqueda.

Cuando nos damos cuenta de eso sety mapestamos hechos de la misma carne, podemos aplicar este principio también a set. Es decir, si queremos actuar sobre un elemento setsolo si está presente en el set, este diseño puede impedirnos escribir 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();
}

Por supuesto, todo esto es una mera especulación.

Desde c ++ 20,

bool contains( const Key& key ) const

está disponible.

¿Qué pasa con 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;

contiene () tiene que devolver un bool. Usando el compilador C ++ 20 obtengo el siguiente resultado para el 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
}

Otra razón es que le daría al programador la falsa impresión de que std :: set es un conjunto en el sentido de la teoría matemática de conjuntos. Si implementan eso, seguirían muchas otras preguntas: si un std :: set tiene contiene () para un valor, ¿por qué no lo tiene para otro conjunto? ¿Dónde están union (), intersection () y otras operaciones de conjunto y predicados?

La respuesta es, por supuesto, que algunas de las operaciones de conjunto ya están implementadas como funciones en (std :: set_union (), etc.) y otras están implementadas de manera tan trivial como contains (). Las funciones y los objetos de función funcionan mejor con abstracciones matemáticas que los miembros de objeto, y no se limitan al tipo de contenedor en particular.

Si uno necesita implementar una funcionalidad completa de un conjunto matemático, no solo tiene la opción de un contenedor subyacente, sino que también tiene una opción de detalles de implementación, por ejemplo, ¿funcionaría su función theory_union () con objetos inmutables, más adecuada para la programación funcional? , ¿o modificaría sus operandos y ahorraría memoria? ¿Se implementaría como objeto de función desde el principio o sería mejor implementar una función C y usar std :: function <> si es necesario?

Como está ahora, std :: set es solo un contenedor, muy adecuado para la implementación de set en sentido matemático, pero está tan lejos de ser un conjunto teórico como std :: vector de ser un vector teórico.