16
\$\begingroup\$

I wrote the following function for the purpose of reusability:

template<typename T>
bool contains(vector<T> v, T x)
{
      if (v.empty())
           return false;
      if (find(v.begin(), v.end(), x) != v.end())
           return true;
      else
           return false;
}

Is this the correct way to do, oor is there any better (or more efficient) way?

\$\endgroup\$
2
  • 12
    \$\begingroup\$ Too verbose. I would simply say return find(v.begin(), v.end(), x) != v.end();. I would pass the parameters by const reference too. You don't need copies. \$\endgroup\$ Aug 10, 2014 at 8:23
  • \$\begingroup\$ The contains function here can't be too generic for each STL Container since the arguments to find algorithm varies differently. \$\endgroup\$
    – krishna
    Oct 29, 2015 at 10:34

3 Answers 3

35
\$\begingroup\$
template<class C, class T>
auto contains(const C& v, const T& x)
-> decltype(end(v), true)
{
    return end(v) != std::find(begin(v), end(v), x);
}

Changes:

  • Removed the superfluous check for emptyness.
  • Parameterized on the container too, so all containers possible.
    • Removed from consideration if v is not a container of some sort.
  • Return the condition directly, no need for sticking it into a condition.

Of course, if you do many containment-tests on big containers, using an optimized container with optimized algorithms instead of vector might be a good idea, though measure it.

A bit more complicated, but using the container-provided find() for best performance where applicable:

#include <algorithm>

template<class C, class T>
inline auto contains_impl(const C& c, const T& x, int)
-> decltype(c.find(x), true)
{ return end(c) != c.find(x); }

template<class C, class T>
inline bool contains_impl(const C& v, const T& x, long)
{ return end(v) != std::find(begin(v), end(v), x); }

template<class C, class T>
auto contains(const C& c, const T& x)
-> decltype(end(c), true)
{ return contains_impl(c, x, 0); }
\$\endgroup\$
10
  • \$\begingroup\$ I wonder if this could be improved to not match if C is not really a container (i.e. begin(v) fails to compile). \$\endgroup\$
    – M.M
    Aug 14, 2014 at 11:05
  • 1
    \$\begingroup\$ The use of auto and decltype everywhere is a bit OTT. \$\endgroup\$
    – James
    Aug 14, 2014 at 11:52
  • 1
    \$\begingroup\$ @James: using both makes SFINAE easier there though... \$\endgroup\$ Aug 14, 2014 at 12:12
  • 2
    \$\begingroup\$ @MattMcNabb: It already is removed from consideration for non-containers, because I used end(c) in the return-type deduction decltype. \$\endgroup\$ Aug 14, 2014 at 12:15
  • 2
    \$\begingroup\$ @Deduplicator the only argument for having a contains algorithm is to provide a more ergonomic interface than find (we don't really need contains since we already have find). Returning an optional allows contains to be used in the same way as if it were returning a bool, but it also allows things that cannot be done with find, like: if(auto p = contains(range, value)) { ... use p here if you want ... } else { ... value is not in rage... }. In particular with find one cannot branch on the value being in the sequence and have the iterator have local scope within the branch. \$\endgroup\$
    – gnzlbg
    Jun 16, 2015 at 15:54
8
\$\begingroup\$

One alternative possibility would be something like:

template <class T>
bool contains(std::vector<T> const &v, T const &x) { 
    return ! (v.empty() ||
              std::find(v.begin(), v.end(), x) == v.end());
}

As far as more efficient goes, there are a couple of possibilities. If you're doing this very often, you might want to consider using std::set or std::unordered_set instead. They support what you're asking for much more directly. Another obvious possibility would be to continue to store the data in a vector, but keep the vector sorted so you can do the search with std::binary_search.

Right now this is O(N). Using std::set or a sorted vector with std::binary_search will reduce that to O(log N). std::unordered_set can reduce the (expected) complexity to O(1).

Big-O can be deceiving though. Especially if the number of elements involved is small, such things as contiguous allocation can make more difference than the theoretical complexity. For a large enough number of elements, std::unordered_set will almost certainly be the fastest of these--but that number of elements may be quite a bit larger than you ever actually use.

Personally, I can't say I really favor parameterizing the container type either. The problem is fairly simple: if (for example) somebody stores the data in an std::set, it will still work, but it'll give truly terrible performance. If you're going to support associative containers at all, you want to provide code that does so at least reasonably efficiently (which, in those cases means not using std::find).

\$\endgroup\$
6
  • 3
    \$\begingroup\$ No need to check if it's empty. std::find will return end if begin == end. \$\endgroup\$
    – Rapptz
    Aug 10, 2014 at 8:35
  • 1
    \$\begingroup\$ @Rapptz: true. I'm assuming (perhaps prematurely) that it was intended as an optimization--if the vector is empty a substantial part of the time, checking for empty first can avoid pushing the parameters to call find. \$\endgroup\$ Aug 10, 2014 at 8:37
  • \$\begingroup\$ Also, using std::set or its unordered counterpart should be done after careful profiling (trading continuous data blocks with small numbers of allocations for node-based ones with many more allocations and indirections.) \$\endgroup\$ Aug 10, 2014 at 8:37
  • \$\begingroup\$ @JerryCoffin: Added an alternative using container.find to my solution, that should remove your objection to full generalization. \$\endgroup\$ Aug 10, 2014 at 10:29
  • \$\begingroup\$ @JerryCoffin I'd expect find to be inlined anyway and the first thing it will do is check begin != end \$\endgroup\$
    – M.M
    Aug 14, 2014 at 11:06
2
\$\begingroup\$

Creating a new algorithm contains() is just too superfluous. The find() algorithm is sufficient and as generic as you can get. The code should just look like this:

bool contains = find(anycontainer.begin(), anycontainer.end(), testvalue) != anycontainer.end());
\$\endgroup\$
3
  • 5
    \$\begingroup\$ That code sample repeats the container name 3 times. Do you think the following interface looks simpler? "bool exists = contains(anycontainer, testValue);" \$\endgroup\$
    – Jon
    Aug 13, 2015 at 6:10
  • \$\begingroup\$ 97 characters to now if an element is present in a container. I refuse to get used to this. \$\endgroup\$
    – tssch
    Jul 8, 2016 at 6:49
  • \$\begingroup\$ This is another reason why I prefer C# over C++. :P \$\endgroup\$
    – Xam
    Mar 8, 2018 at 0:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.