current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite
2

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?

share|improve this question

migrated from stackoverflow.com Aug 14 '14 at 11:01

This question came from our site for professional and enthusiast programmers.
9  
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. – juanchopanza Aug 10 '14 at 8:23
2  
better go for full genericity and don't insist on vectors. Also, there's no need to first check for emptyness. – Deduplicator Aug 10 '14 at 8:31
    
The contains function here can't be too generic for each STL Container since the arguments to find algorithm varies differently. – Krishna_Oza Oct 29 '15 at 10:34
up vote 12 down vote accepted 
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); }
share|improve this answer
    
I wonder if this could be improved to not match if C is not really a container (i.e. begin(v) fails to compile). – M.M Aug 14 '14 at 11:05
    
The use of auto and decltype everywhere is a bit OTT. – James Aug 14 '14 at 11:52
    
@James: using both makes SFINAE easier there though... – Deduplicator Aug 14 '14 at 12:12
2  
@MattMcNabb: It already is removed from consideration for non-containers, because I used end(c) in the return-type deduction decltype. – Deduplicator Aug 14 '14 at 12:15
2  
@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. – gnzlbg Jun 16 '15 at 15:54
up vote 5 down vote

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).

share|improve this answer
3  
No need to check if it's empty. std::find will return end if begin == end. – Rapptz Aug 10 '14 at 8:35
1  
@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. – Jerry Coffin Aug 10 '14 at 8:37
    
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.) – juanchopanza Aug 10 '14 at 8:37
    
@JerryCoffin: Added an alternative using container.find to my solution, that should remove your objection to full generalization. – Deduplicator Aug 10 '14 at 10:29
    
@JerryCoffin I'd expect find to be inlined anyway and the first thing it will do is check begin != end – M.M Aug 14 '14 at 11:06
up vote 2 down vote

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());
share|improve this answer
    
That code sample repeats the container name 3 times. Do you think the following interface looks simpler? "bool exists = contains(anycontainer, testValue);" – Jon Aug 13 '15 at 6:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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