A general-purpose STLish contains()

Question

I'm annoyed that STL containers don't have a, well, contains() method returning true if the container contains an element, false otherwise. So, I sat down and wrote this:

template <typename C, typename E>
inline bool contains(const C& container, const E& element) {
    return container.find(element) != container.end();
}

which works well enough for sets and maps, but not for vectors. Or lists. How should I proceed? Should I write an additional

template <typename T>
inline bool contains(const vector<T>& container, const T& element) {
    std::find(vector.begin(), vector.end(), item) != vector.end()
}

and more specific code for other containers? Should I instead settle on the sub-optimal use of iterators to check element-by-element? I would really much rather not do that... perhaps I'm not noticing some relevant STL functionality?

Answer 1

I think one reason is for the absence of a std::contains returning a bool is that it is too easy for novice programmers to fall into the trap

if (std::contains(my_container, some_element)) {
   auto it = std::find(begin(my_container), end(my_container), some_element);
   // process *it
}

and now you are doing twice the work you need.

It is simply idiomatic to write

auto it = std::find(begin(my_container), end(my_container), some_element);
if (it != end(my_container)) {
   // process *it
}

If you insist on having a contains function, you could aim for the best of both worlds by returning a std::pair<bool, iterator> or a std::optional<iterator> (coming in a library fundamentals Technical Specification, or already present in Boost) that you can query like this:

if (opt = std::contains(my_container, some_element)) {
   // process *opt 
}

Answer 2

If you intend to use this function only on STL containers, and if you further have no need to process the iterator returned by find, then yes, I would suggest you to write specific code for these containers. It is the most effective you can do.

template<typename ... Args> struct has_find {};
template<typename T> struct has_find<std::vector<T> > { static const bool value=false; };
template<typename T> struct has_find<std::deque<T> > { static const bool value=false; };
template<typename T, size_t I> struct has_find<std::array<T, I> > { static const bool value=false; };
template<typename T, typename U> struct has_find<std::map<T, U> > { static const bool value=true; };

//... and so on for the handful remaining containers

template<bool has_find>
struct contains_impl
{
    template <typename C, typename E>
    bool contains(const C& container, E&& element) const
    {
        return container.find(std::forward<E>(element)) != container.end();
    }
};

template<>
struct contains_impl<false>
{
    template <typename C, typename E>
    bool contains(const C& container, E&& element) const
    {
        return std::find(container.cbegin(), container.cend(), std::forward<E>(element)) != container.cend();
    }
};

template <typename C, typename E>
bool contains(const C& container, E&& element)
{
    return contains_impl<has_find<C>::value>().contains(container, std::forward<E>(element));
}

The alternative would be to use metaprogramming and let the compiler determine whether the class contains a specific find function, but that would maybe be a bit overkill... Anyways, if want to go this way, you can read the recipes in this thread.