Why does std::set not have a "contains" member function?

Question

I'm heavily using std::set<int> and often I simply need to check if such a set contains a number or not.

I'd find it natural to write:

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

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

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

or the not as obvious:

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

Is there a reason for this design decision ?

Answer 1

I think it was probably because they were trying to make std::set and std::multiset as similar as possible. (And obviously count has a perfectly sensible meaning for std::multiset.)

Personally I think this was a mistake.

It doesn't look quite so bad if you pretend that count is just a misspelling of contains and write the test as:

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

It's still a shame though.

Answer 2

To be able to write if (s.contains()), contains() has to return a bool (or a type convertible to bool, which is another story), like binary_search does.

The fundamental reason behind the design decision not to do it this way is that contains() which returns a bool would lose valuable information about where the element is in the collection. find() preserves and returns that information in the form of an iterator, therefore is a better choice for a generic library like STL. This has always been the guiding principle for Alex Stepanov, as he has often explained (for example, here).

As to the count() approach in general, although it's often an okay workaround, the problem with it is that it does more work than a contains() would have to do.

That is not to say that a bool contains() isn't a very nice-to-have or even necessary. A while ago we had a long discussion about this very same issue in the ISO C++ Standard - Future Proposals group.

Answer 3

It lacks it because nobody added it. Nobody added it because the containers from the STL that the std library incorporated where designed to be minimal in interface. (Note that std::string did not come from the STL in the same way).

If you don't mind some strange 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)};
}

use:

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

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

It makes a lot more sense to just do this:

if (some_set.count(some_element)) {
}

but I am amused by the extension method method.

The really sad thing is that writing an efficient contains could be faster on a multimap or multiset, as they just have to find one element, while count has to find each of them and count them.

A multiset containing 1 billion copies of 7 (you know, in case you run out) can have a really slow .count(7), but could have a very fast contains(7).

With the above extension method, we could make it faster for this case by using lower_bound, comparing to end, and then comparing to the element. Doing that for an unordered meow as well as an ordered meow would require fancy SFINAE or container-specific overloads however.

Answer 4

You are looking into particular case and not seeing bigger picture. As stated in documentation std::set meets requirement of AssociativeContainer concept. For that concept it does not make any sense to have contains method, as it is pretty much useless for std::multiset and std::multimap, but count works fine for all of them. Though method contains could be added as an alias for count for std::set, std::map and their hashed versions (like length for size() in std::string ), but looks like library creators did not see real need for it.

Answer 5

Although I don't know why std::set has no contains but count which only ever returns 0 or 1, you can write a templated contains helper function like this:

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 like this:

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

Answer 6

Since c++20,

bool contains( const Key& key ) const

is available.

Answer 7

The true reason for set is a mystery for me, but one possible explanation for this same design in map could be to prevent people from writing inefficient code by accident:

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

Which would result in two map lookups.

Instead, you are forced 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 lookup.

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

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 a mere speculation.

Answer 8

I'd like to point out , as mentioned by Andy, that since C++20 the standard added the contains Member function for maps or set:

bool contains( const Key& key ) const;  (since C++20)

Now I'd like to focus my answer regarding performance vs readability. In term of performance if you compare the two versions:

#include <unordered_map>
#include <string>
using hash_map = std::unordered_map<std::string,std::string>;
hash_map a;

std::string get_cpp20(hash_map& x,std::string str)
{
    if(x.contains(str))
        return x.at(str);
    else
        return "";
};

std::string get_cpp17(hash_map& x,std::string str)
{
    if(const auto it = x.find(str); it !=x.end())
        return it->second;
    else
        return "";
};

You will find that the cpp20 version takes two calls to std::_Hash_find_last_result while the cpp17 takes only one call.

Now I find myself with many data structure with nested unordered_map. So you end up with something like this:

using my_nested_map = std::unordered_map<std::string,std::unordered_map<std::string,std::unordered_map<int,std::string>>>;

std::string get_cpp20_nested(my_nested_map& x,std::string level1,std::string level2,int level3)
{
    if(x.contains(level1) &&
        x.at(level1).contains(level2) &&
        x.at(level1).at(level2).contains(level3))

        return x.at(level1).at(level2).at(level3);
    else
        return "";
};

std::string get_cpp17_nested(my_nested_map& x,std::string level1,std::string level2,int level3)
{
    if(const auto it_level1=x.find(level1); it_level1!=x.end())
        if(const auto it_level2=it_level1->second.find(level2);it_level2!=it_level1->second.end())
            if(const auto it_level3=it_level2->second.find(level3);it_level3!=it_level2->second.end())
                return it_level3->second;

    return "";
};

Now if you have plenty of condition in-between these ifs, using the iterator really is painful, very error prone and unclear, I often find myself looking back at the definition of the map to understand what kind of object was at level 1 or level2, while with the cpp20 version , you see at(level1).at(level2).... and understand immediately what you are dealing with. So in term of code maintenance/review, contains is a very nice addition.

Answer 9

What about 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 10

contains() has to return a bool. Using C++ 20 compiler I get the following output for the code:

#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
}

Answer 11

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

The answer is, of course, that some of the set operations are already implemented as functions in (std::set_union() etc.) and other are as trivially implemented as contains(). Functions and function objects work better with math abstractions than object members, and they are not limited to the particular container type.

If one need to implement a full math-set functionality, he has not only a choice of underlying container, but also he has a choice of implementation details, e.g., would his theory_union() function work with immutable objects, better suited for functional programming, or would it modify its operands and save memory? Would it be implemented as function object from the start or it'd be better to implement is a C-function, and use std::function<> if needed?

As it is now, std::set is just a container, well-suited for the implementation of set in math sense, but it is nearly as far from being a theoretical set as std::vector from being a theoretical vector.