Why doesn't std :: set have a contain function?

Question

I use std::set<int> heavily, and often I just need to check if such a set contains a number or not.

I would find it natural to write:

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

But due to the lack of the contains member, I need to write cumbersome:

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

or not so obvious:

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

Is there a reason for this design decision?

Answer 1

I think this is probably because they tried to make std::set and std::multiset as similar as possible. (And obviously count makes perfect sense for std::multiset .)

Personally, I think it was a mistake.

It doesn’t look so bad if you pretend that count is just the contains spelling error and write the test as:

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

However, this is a shame.

Answer 2

To be able to write if (s.contains()) , contains() must return bool (or a type convertible to bool , which is another story), for example binary_search .

the fundamental reason behind the design decision not to do it this way is that contains() , which returns a bool , will lose valuable information about where the item is in the collection . find() saves and returns this information in the form of an iterator, so it is the best choice for a shared library such as STL. This has always been a guiding principle for Alex Stepanov, as he often explained (for example, here ).

As for the count() approach in general, although it is often a workaround, the problem is that it works more than it should contains() .

This is not to say that bool contains() not very nice or even necessary. Some time ago, we had a long discussion about the same problem in the ISO C ++ Standard - a group of future proposals.

Answer 3

This is missing because no one added it. No one added it, because the containers are from the STL, into which the std library is built, where they were minimal in the interface. (Note that std::string did not come from STL in the same way).

If you don't mind some weird syntax, you can fake it:

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

using:

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

Basically, you can write extension methods for most types of C ++ std using this technique.

There is much more sense for this:

 if (some_set.count(some_element)) { } 

but the extension method method surprises me.

The sad thing is that writing effective contains can be faster on multimap or multiset , because they just have to find one element, and count must find each of them and count them.

A multiset containing 1 billion instances of 7 (you know, in case you are done) can have a very slow .count(7) , but it can have a very fast contains(7) .

Using the aforementioned extension method, we could do it faster for this case, using lower_bound , compared to end , and then comparing it to the element. For this, disordered meow as well as ordered meow will require fantastic SFINAE or container-specific overloads.

Answer 4

You look at a specific case and do not see a large picture. As stated in the documentation, std::set meets the requirements of the AssociativeContainer concept. For this concept, it makes no sense to have a contains method, since it is almost useless for std::multiset and std::multimap , but count works fine for all of them. Although the contains method can be added as an alias for count for std::set , std::map and their hashed versions (for example, length for size() in std::string ), but it looks like the creators of the library did not see the real need in him.

Answer 5

Although I don’t know why std::set does not have contains , but count , which only returns 0 or 1 , you can write the template helper function contains as follows:

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

And use it as follows:

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

Answer 6

The true reason for set is a mystery to me, but one possible explanation for the same construction in map might be to prevent people from accidentally accessing inefficient code:

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

This will result in two map searches.

Instead, you need to get an iterator. This gives you a mental hint that you should reuse the iterator:

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

which consumes only one map search.

When we understand that set and map are made of the same flesh, we can apply this principle also to set . That is, if we want to act on an element in set only if it is present in set , this project may prevent us from writing code as follows:

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

Of course, all this is just an assumption.

Answer 7

Another reason is that it will give the programmer a false impression that std :: set is a set in the sense of mathematical set theory. If they implement this, then many other questions will follow: if std :: set contains () for the value, why doesn't it have it for another set? Where are union (), intersection (), and other given operations and predicates?

Of course, the answer is that some of the given operations are already implemented as functions in (std :: set_union (), etc.), while others are implemented as trivially as contains (). Functions and function objects work better with mathematical abstractions than elements of an object, and they are not limited to a specific type of container.

If you want to implement full functionality with a mathematical set, he not only has a choice of the base container, but also has a choice of implementation details, for example, whether his theory_union () function will work with immutable objects, is better suited for functional programming, or he will change his operands and save memory? Will it be implemented as a function object from the very beginning or is it better to implement a C-function and use std :: function <> if necessary?

As now, std :: set is just a container that is well suited to implement the set in the mathematical sense, but it is almost not a theoretical set, like std :: vector, from a theoretical vector.