ejemplo - set c++ example

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

Question

Estoy usando 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 miembro contains , necesito escribir el engorroso:

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

o el no tan obvio:

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

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

Answer 1

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

Answer 2

Aunque no sé por qué std::set no contains pero count que solo devuelve 0 o 1 , puede escribir una función auxiliar de 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 úsalo así:

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

Answer 3

Creo que probablemente fue porque estaban tratando de hacer std::set y std::multiset más similar posible. (Y obviamente, count tiene un significado perfectamente sensato para std::multiset ).

Personalmente creo que esto fue un error.

No se ve tan mal si finges que el count es solo una falta de ortografía de contains y escribe la prueba como:

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

Sin embargo, sigue siendo una pena.

Answer 4

Estás buscando un caso particular y no ves una imagen más grande. Como se indica en la documentation std::set cumple con los requisitos del concepto AssociativeContainer . Para ese concepto, no tiene ningún sentido tener un método contains , ya que es bastante inútil para std::multiset y std::multimap , pero count funciona bien para todos ellos. Aunque el método contains podría agregar como un alias para el count de std::set , std::map y sus versiones hash (como length for size() en std::string ), pero parece que los creadores de la biblioteca no vieron la necesidad real de eso.

Answer 5

La verdadera razón para set es un misterio para mí, pero una posible explicación para este mismo diseño en el map podrí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 búsquedas de map .

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 búsqueda en el map .

Cuando nos damos cuenta de que el set y el map están hechos de la misma carne, podemos aplicar este principio también al set . Es decir, si queremos actuar sobre un elemento del set solo si está presente en el set , este diseño puede evitar que escribamos 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.

Answer 6

Le falta porque nadie lo agregó. Nadie lo agregó porque los contenedores del STL que incorporó la biblioteca estándar estaban diseñados para tener una interfaz mínima. (Tenga en cuenta que std::string no provenía del STL de la misma manera).

Si no le importa alguna sintaxis extraña, puede simularla:

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 tipos estándar 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 contenido eficiente podría ser más rápido en un multimap o en un conjunto multimap , ya que solo tienen que encontrar un elemento, mientras que count tiene que encontrar cada uno de ellos y contarlos .

Un conjunto múltiple que contiene mil millones de copias de 7 (ya sabe, en caso de que se agote) puede tener un .count(7) muy lento .count(7) , pero podría tener un contenido muy rápido contains(7) .

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

Answer 7

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 de conjuntos matemáticos. Si implementan eso, entonces 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 tan trivialmente como contiene (). Las funciones y los objetos de función funcionan mejor con las abstracciones matemáticas que los miembros del objeto, y no se limitan al tipo de contenedor particular.

Si uno necesita implementar una funcionalidad completa de conjunto matemático, no solo tiene una opción de contenedor subyacente, sino que también tiene una opción de detalles de implementación, por ejemplo, su función teoría_unión () funcionaría con objetos inmutables, más adecuados 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 fuera necesario?

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

Answer 8

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

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

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

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