What is a C++ container with a “contains” operatio

问题:

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.

回答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)) { /*...*/ }

回答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.

回答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.

回答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/

回答5:

If you want to use a C++ standard container, due to its design, the containers themselves do not necessarily have "contains", but you can always use the find algorithm.

You should choose your container according to the characteristics of your dataset and the access "workload".

For a good reference of the containers and algorithms on the C++ standard library check http://www.cplusplus.com

Containers, Algorithms

If as it seems, your data is made of unique items, for which you want to associate a value, you probably will be well served by the map container. If all you care about is "membership", then set is a better choice.