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?

There's [`std::find()`, `std::find_if()`](http://en.cppreference.com/w/cpp/algorithm/find) don't these fit your needs on these purposes? — πάντα ῥεῖ, Nov 12 '14 at 12:05
Why don't you use `std::find` right away (in the first function)? — SingerOfTheFall, Nov 12 '14 at 12:07
@πάνταῥεῖ I find find very ugly `std::find(std::begin(v), std::end(v), n1)`, what the hell is that. Why there is no simple version. — Andrey, Nov 12 '14 at 12:07
@SingerOfTheFall: Because, for an associative container, that's much less efficient. — Mike Seymour, Nov 12 '14 at 12:10
@Andrey I guess the Stl settled for the general case, where you might want to restrict your search to a "subset" of a container. Writing the most occurring case (which you find ugly) is trivial, so I guess they didn't feel the need to provide a shortcut for it. — didierc, Nov 12 '14 at 12:15
It's a fairly easy exercise in metaprogramming to create a version which uses the member function `find` if it exists, and reverts to the `std::find` if it doesn't. The only issue is that with sequence containers, it's likely to be slow, as it does a linear search. (On the other hand, I often have cases where I'm searching in a vector of five or ten elements, and a linear search on a vector like that is generally faster than a direct lookup in a map.) — James Kanze, Nov 12 '14 at 12:16
You can change your contains function to just `const T& container`, then it works for any container. You can also remove `E` type and use `typename T::value_type` which will work for standard containers. — Neil Kirk, Nov 12 '14 at 12:26
`contains()` == [`std::any_of`](http://en.cppreference.com/w/cpp/algorithm/all_any_none_of) — edmz, Nov 12 '14 at 12:43
@MikeSeymour: Isn't the default implementation of std::find overridden by different containers for better performance? — einpoklum, Nov 12 '14 at 13:19
@black: Doesn't `std::any_of` necessarily have linear complexity in the number of elements? It uses unary predicates, and can't make any useful assumptions about the predicate which would allow something like binary searching or other optimizations. — einpoklum, Nov 12 '14 at 13:23
@einpoklum: That's unlikely, since `std::find` works with general iterator ranges not containers, and not done by the one I use (GCC). In any case, it does something different to the `find` member, searching for equal `value_type` not equivalent `key_type`. — Mike Seymour, Nov 12 '14 at 13:41
@MikeSeymour: ... and container begin()/end() iterators don't 'carry' enough traits of their containers to allow for such optimization? Also, you say "it does something different to `find`", but 'it' _is_ `find`... — einpoklum, Nov 12 '14 at 13:43
@einpoklum: It might or might not carry enough information to identify the container it came from, which might or might not have an extra runtime cost - I can't comment about the details since I don't write library implementations, I'm just observing that at least one popular library doesn't do the optimisation. `std::find` and `::find` **do** have different behaviour; as I said, one compares `value_type` for equality, the other compares `key_type` for equivalence (for ordered containers) or equality (for hashed containers). — Mike Seymour, Nov 12 '14 at 13:57
@MikeSeymour A related discussion for the `std::lower_bound` case can be found here: http://stackoverflow.com/q/20934717 — dyp, Nov 12 '14 at 14:21

score 7 · Answer 1 · edited Dec 26 '14 at 22:53

7

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 
}

edited Dec 26 '14 at 22:53

dyp

38,334
13
112
177

answered Nov 12 '14 at 12:10

TemplateRex

69,038
19
164
304

But (1) : Your idiom requires 2 lines and about 80 characters, while `if contains(my_container,some_element)` is half the number of lines and less than half the characters. – einpoklum Nov 12 '14 at 13:30
3

But (2): The semantics are off. I want my program to read like "If my_container contains element some_element then do something." - I don't want it to read "Find the position of some_element in my_container; now, if you haven't found it to be an an invalid position, it must be the case that it's present, so let's do something." – einpoklum Nov 12 '14 at 13:33
1

@einpoklum Re your Buts: you can write everything inside the conditional: `if (auto opt = contains(my_container, some_element)) { /* process *opt */ }` if you want is as a one-liner – TemplateRex Nov 12 '14 at 15:24

score 1 · Accepted Answer · edited May 23 '17 at 10:28

1

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.

edited May 23 '17 at 10:28

Community

1
1

answered Nov 12 '14 at 13:31

davidhigh

14,652
2
44
75

1

One downside is that this `contains` has strange requirements and complexity guarantees. For example, associative containers's `find` requires `<` and a conversion from the needle to the key type if they're not transparent (heterogeneous lookup), unordered associative containers also require a conversion, `std::find` requires `==` between the needle and the haystack types etc. It's essentially a bunch of different algorithms all with the same name. – dyp Nov 12 '14 at 13:55
@dyp: A conversion from the needle's type to the 'key type' sounds like a pretty reasonable requirement... also, in an ordered container, can't you assume you would need a `<` operator to look for things? – einpoklum Nov 12 '14 at 14:02
@einpoklum True, a conversion is sufficient if you already have the container. But a conversion isn't necessarily efficient, for example, to search for a string literal in a container that uses `std::string`s. That's one reason why heterogeneous lookup has been introduced in C++14. It has always been supported by `std::find`. You could try restricting the needle via `contains(C const& container, C::value_type const& needle)`. The strange complexity guarantees remain ("at most O(N)"). – dyp Nov 12 '14 at 14:08
@einpoklum The semantics are strange, too: associative and unordered associative containers supply their own comparison function object, while all other containers and ranges use the default `operator==`. You might get the result `true` if there's an object that's not equal to the needle (e.g. if the comparison function object only takes a part of the object into account). – dyp Nov 12 '14 at 14:13
1

@dyp: this is true, but to me it seems unavoidable for the kind of algorithm the OP asked for. And, in practice, these restrictions doesn't seem so severe to me: for example, you already have `<` when you set up a map. You only search for values which can be implicitly converted (you do not search for a `string` in a vector of `int`s, and if you do, the compiler will complain). And you get the best complexity guarantee there is for the kind of container. EDIT: a bit late, I see you're already discussing these things... – davidhigh Nov 12 '14 at 14:13
@davidhigh Yes, the criticism applies to the algorithm, not you particular implementation. However, the OP asked "how to proceed", and I think a possible answer is "don't, because of reasons A,B,C,D". – dyp Nov 12 '14 at 14:16
@einpoklum Oops, that "`<` and a conversion" in my first comment should have been a "`<` OR a conversion" (`<` in case of heterogeneous lookup, and a conversion otherwise). – dyp Nov 12 '14 at 14:17
@dyp: If you restrict to value_type, in a map you would be searching using the wrong type... – einpoklum Nov 12 '14 at 14:40

A general-purpose STLish contains()

2 Answers2