What is a C++ container with a "contains" operation?

Question

I want to use a structure in which I insert integers, and then can ask

if (container.contains(3)) { /**/ }

There has to be something like this.

Solution 1

You can use std::vector.

std::vector<int> myVec;
myVec.push_back(3);
if (std::find(myVec.begin(), myVec.end(), 3) != myVec.end())
{
    // do your stuff
}

You can even make a little helper function:

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

Here is how you would use it:

if (contains(myVec, 3)) { /*...*/ }

Solution 2

Simple algorithm:

template <typename Container>
bool contains(Container const& c, typename Container::const_reference v) {
  return std::find(c.begin(), c.end(), v) != c.end();
}

You can customize it for more efficient search on some known containers:

template <typename Key, typename Cmp, typename Alloc>
bool contains(std::set<Key,Cmp,Alloc> const& s, Key const& k) {
  return s.find(k) != s.end();
}

template <typename Key, typename Value, typename Cmp, typename Alloc>
bool contains(std::map<Key,Value,Cmp,Alloc> const& m, Key const& k) {
  return m.find(k) != m.end();
}

And this way you obtain a single algorithm that performs the search on any container type, and is special cased to be faster on those containers which are ordered.

Solution 3

find on an unsorted vector is O(n).

std::set supports O(log n) insertions and lookups and is a good choice.

std::tr1::unordered_set provides a similar interface but supports near-constant-time lookups. It is the best choice if you have TR1 (or C++0x) and do not need to enumerate the elements in order.

Solution 4

What you want is the find_first_of method from the algorithms library. (or binary search, or anything along those lines)

http://www.cplusplus.com/reference/algorithm/find_first_of/

View more solutions

Comments

[Jesse Emond]

@Nemo: The OP never asked for a fast-execution method, but only for a working method. I offered a general solution to a general problem. If the OP asks for a specific problem where speed is important, then an other solution would be better. Picking a std::set right away just to save a linear-time search implies other design consequences and I would consider this as premature optimization (when in fact the search could not even be in a performance bottleneck). Premature optimization is the root of all evil. A different solution to a problem is not worth a down-vote, IMO.

[Blastfurnace]

@Nemo: A correct linear-time solution is fine unless measurement proves it is a significant bottleneck.

[DarkWanderer]

Now that's what I was looking for. Thank you

[Jonathan Baldwin]

Linear time is the best you can do if you can't use a sorted list or a hash table for some reason (eg. you want to preserve order of insertion.)

[Steven Sudit]

For small n's, an unsorted vector is perfectly fine, perhaps even faster.

[helmesjo]

What we all should know: Linear iteration over collections linear in memory (as vector if homogeneous) is (if repeated) fast as lightning! Keep shades close by!

[Dwayne Robinson]

std::find_first_of searches for subsequences in a larger sequence, but 'contains(3)' has only a single scalar, with no begin/end range. So std::find is a better fit here.