什么是带有"包含"操作的C++容器？

Question

我想使用一个结构,我插入整数,然后可以问

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

必须有类似的东西.

Answer 1

你可以用std::vector.

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

你甚至可以做一个小帮手功能:

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

以下是如何使用它:

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

Answer 2

简单的算法:

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

您可以对其进行自定义,以便更有效地搜索某些已知容器:

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();
}

通过这种方式,您可以获得一个对任何容器类型执行搜索的算法,并且特别可以在订购的容器上加快速度.

Answer 3

find未排序向量的复杂度为 O(n)。

std::set支持 O(log n) 插入和查找，是一个不错的选择。

std::tr1::unordered_set提供类似的界面，但支持近乎恒定时间的查找。如果您有 TR1（或 C++0x）并且不需要按顺序枚举元素，那么它是最佳选择。