如何检查一个元素是否在std::set中？

Question

如何检查一个元素是否在集合中？

是否有以下代码的更简单等效方式：

myset.find(x) != myset.end()

- fulmicoton

---

比这更简单的方式只有一个布尔谓词：template <typename T> bool member(T const &item)。这将在底层实现，并基于您所询问的行实现。 - Don Wakefield

Answer 1

从C++20开始，您可以使用contains在许多STL容器中检查存在性，例如std::map，std::set等：

const bool is_in = container.contains(element);

在 C++20 之前，典型的方式是：

const bool is_in = container.find(element) != container.end();

- unwind

---

这特指于集合和映射。向量、列表等没有一个名为“find”的成员函数。 - wilhelmtell

在我看来，使用count()更好，因为它更简洁，并且正如Pieter所指出的那样，它会转换为bool值。我不明白为什么这个答案被接受，并获得了这么多分数... - Огњен Шобајић

为了完整起见：向量/列表可以使用std::find函数: std::find(container.begin(), container.end(), element) != container.end()；当然，时间复杂度仍然是O(N)... - Aconcagua

如果采用您的变体：if(container.find(foo) == container.end())，需要进行一次树查找以找到元素 - 如果找不到，则需要进行第二次树查找以找到正确的插入位置。原始变体if(container.insert(foo).second) {...}有一个优点，它只需要进行一次树查找... - Aconcagua

在C++20标准中，有一个名为set.contains(x)的函数，其返回一个布尔值。我不知道为什么直到2020年我们才将其加入标准。 - gremwell

Answer 2

另一种简单判断元素是否存在的方法是检查 count()。

if (myset.count(x)) {
   // x is in the set, count is 1
} else {
   // count zero, i.e. x not in the set
}

大多数情况下，我需要在检查元素是否存在的地方访问该元素。因此，无论如何都必须找到迭代器。然后，当然最好将其与end进行比较。

set< X >::iterator it = myset.find(x);
if (it != myset.end()) {
   // do something with *it
}

C++ 20

在 C++20 中，set容器加入了contains函数，因此以下操作成为可能，如 https://dev59.com/TXI-5IYBdhLWcg3wu7Lv#54197839 所述。

if (myset.contains(x)) {
  // x is in the set
} else {
  // no x 
}

- Pieter

---

@Frerich 我认为这只适用于multiset和multimap，但指出这一点仍然很好 :) - Pieter

std::set 通常使用有序树结构实现，所以 count() 和 find() 的时间复杂度均为 O(logn)。它们都不会迭代集合中的所有元素。 - Alan

你确定吗？因为set只能包含一个匹配的成员，所以该函数是否会被实现为在找到第一个元素之后停止查找，正如Pieter所指出的那样？无论如何都是有用的答案！ - Dan Nissenbaum

@DanNissenbaum，是的，你说得完全正确（+Peter和+Alan也是），对于std::set来说，这两个函数在性能方面是等效的。因此，即使我评论的第一部分（count()永远不会比find()更快）仍然成立，但第二部分确实不适用于std::set。然而，我认为另一个支持find()的论点可以提出：它更加表达清晰，也就是强调了你正在尝试查找一个元素而不是计算出现次数。 - Frerich Raabe

在GCC中，set的.count方法使用了find操作：count(const key_type& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }。该方法用于统计集合中键值为__x的元素个数，如果没有找到则返回0，否则返回1。 - Doncho Gunchev

Answer 3

仅澄清一下，这些容器类型没有像contains()这样的成员是因为它会导致编写低效代码。这样的方法可能只是在内部执行this->find(key) != this->end()，但考虑键确实存在时你要做什么；在大多数情况下，您将想要获取元素并对其进行操作。这意味着您必须进行第二个find()，这是低效的。最好直接使用find，这样可以缓存结果，例如：

auto it = myContainer.find(key);
if (it != myContainer.end())
{
    // Do something with it, no more lookup needed.
}
else
{
    // Key was not present.
}

当然，如果您不关心效率，您总是可以自己编写，但在这种情况下，您可能不应该使用C++... ;)

- Tim

---

集合怎么样？通常你已经有了元素，只是想检查它是否在集合中。 - Elazar Leibovich

你是否有任何参考资料来证明这是STL没有包含该方法或函数的实际原因，还是这只是你的猜测？请注意，我只需要翻译以上内容。 - Fabio A.

@FabioA. 这是我的合理猜测。 - Tim

如果因为担心某人不知道如何正确使用一个功能而不去包含它，这对我来说是没有意义的。编程是为那些能够自主思考并对其代码及其性能负责的人设计的。 - slawekwin

请注意，C++20引入了contains()函数。实际上，你可能有很多原因想要查看一个元素是否在集合中，而不是实际获取它的迭代器。事实上，对于一个集合，你不能做太多关于这个迭代器的操作，除了删除该元素，而无需先进行查找。 - Lightness Races in Orbit

Answer 4

在C++20中，我们终于会得到std::set::contains方法。

#include <iostream>
#include <string>
#include <set>

int main()
{
    std::set<std::string> example = {"Do", "not", "panic", "!!!"};

    if(example.contains("panic")) {
        std::cout << "Found\n";
    } else {
        std::cout << "Not found\n";
    }
}

- Denis Sablukov

Answer 5

如果您要添加一个 contains 函数，代码可能如下所示：

#include <algorithm>
#include <iterator>

template<class TInputIterator, class T> inline
bool contains(TInputIterator first, TInputIterator last, const T& value)
{
    return std::find(first, last, value) != last;
}

template<class TContainer, class T> inline
bool contains(const TContainer& container, const T& value)
{
    // This works with more containers but requires std::begin and std::end
    // from C++0x, which you can get either:
    //  1. By using a C++0x compiler or
    //  2. Including the utility functions below.
    return contains(std::begin(container), std::end(container), value);

    // This works pre-C++0x (and without the utility functions below, but doesn't
    // work for fixed-length arrays.
    //return contains(container.begin(), container.end(), value);
}

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

这适用于 std::set，其他STL容器，甚至是固定长度的数组：

void test()
{
    std::set<int> set;
    set.insert(1);
    set.insert(4);
    assert(!contains(set, 3));

    int set2[] = { 1, 2, 3 };
    assert(contains(set2, 3));
}

编辑：

如评论所指出，我无意中使用了C++0x中的新函数（std::begin和std::end）。这里是来自VS2010的近乎微不足道的实现：

namespace std {

template<class _Container> inline
    typename _Container::iterator begin(_Container& _Cont)
    { // get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::const_iterator begin(const _Container& _Cont)
    { // get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::iterator end(_Container& _Cont)
    { // get end of sequence
    return (_Cont.end());
    }

template<class _Container> inline
    typename _Container::const_iterator end(const _Container& _Cont)
    { // get end of sequence
    return (_Cont.end());
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *begin(_Ty (&_Array)[_Size])
    { // get beginning of array
    return (&_Array[0]);
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *end(_Ty (&_Array)[_Size])
    { // get end of array
    return (&_Array[0] + _Size);
    }

}

- Sam Harwell

---

@Adhemar，实际上它确实是低效的，但不是你提到的原因。 - Sam Harwell

@280Z28：std::begin(container)是什么？这是哪个STL标准？在我的gcc上它无法编译。 - stefaanv

container.begin()是什么意思？ - fulmicoton

你可以使用Boost范围库中的boost::begin()和boost::end()。 - Benoît

@Adhemar：如果你知道集合包含一个值，那么你已经有了这个值。你需要迭代器的唯一原因是从集合中删除元素。如果你只需要知道一个集合是否包含一个值，那么这个解决方案的效率不比其他任何解决方案低。 - Sam Harwell

Answer 6

自从C++20版本开始，简单明了地（最终！）提供std::contains(const K&)布尔函数。

https://en.cppreference.com/w/cpp/container/set/contains

- Philippe

Answer 7

在插入元素时，您还可以检查元素是否在集合中。单个元素版本会返回一个pair，其中其成员pair::first设置为指向新插入的元素或已经存在于集合中的等效元素的迭代器。Pair::second对中的元素设置为true，如果插入了一个新元素，则设置为false，如果已经存在等效元素，则设置为false。

例如：假设集合已经有20作为元素。

 std::set<int> myset;
 std::set<int>::iterator it;
 std::pair<std::set<int>::iterator,bool> ret;

 ret=myset.insert(20);
 if(ret.second==false)
 {
     //do nothing

 }
 else
 {
    //do something
 }

 it=ret.first //points to element 20 already in set.

如果元素是新插入的，则pair::first将指向集合中新元素的位置。

- Prashant Shubham

Answer 8

我使用

if(!my_set.count(that_element)) //Element is present...
;

但它的效率不如

if(my_set.find(that_element)!=my_set.end()) ....;

我的版本只是在编写代码时节省了时间。对于竞技编程，我更喜欢这种方式。

- Manas Bondale

---

是的，count()。任何无法理解在布尔表达式中使用返回整数的函数来测试非零的人，在C/C++习语的大海中将会遇到许多其他的困难。正如上面所提到的，对于集合来说应该是非常高效的，这也是问题的关键。 - Ron Burk

Answer 9

这就是它，远胜过其他。

bool once(uintptr_t val) {
    return visited.emplace(val).second;
}

怎么可能是其他的呢？

https://godbolt.org/z/9zP77jqMc

func5(unsigned long):
        sub     rsp, 24
        mov     QWORD PTR [rsp+8], rdi
        lea     rsi, [rsp+8]
        mov     edi, OFFSET FLAT:visited2
        call    std::pair<std::_Rb_tree_iterator<unsigned long>, bool> std::_Rb_tree<unsigned long, unsigned long, std::_Identity<unsigned long>, std::less<unsigned long>, std::allocator<unsigned long> >::_M_emplace_unique<unsigned long&>(unsigned long&)
        add     rsp, 24
        mov     eax, edx
        ret

- Orwellophile

Answer 10

编写你自己的代码：

template<class T>
bool checkElementIsInSet(const T& elem, const std::set<T>& container)
{
  return container.find(elem) != container.end();
}

- stefaanv

---

template<class T> static inline bool contains(const std::set<T>& S, T x) { return (S.find(x) != S.end()); } - fulmicoton

@Paul 不要创建静态全局函数。相反，将你的函数放在一个匿名命名空间中：这是 C++ 创建不会链接到其他编译单元中的函数的方式。此外，你的 T 参数应该是一个 const 引用，以确保常量正确性和提高效率。 - wilhelmtell

-1：不是模板化的，也完全不符合STL的风格。如果你不使用STL，那么这没问题，但如果你使用STL，你至少应该尝试遵循其标准。 - Sam Harwell

@280Z28：很抱歉我的代码不符合您的标准，我只是想表明如果您不喜欢STL的接口，您可以编写自己的接口。天哪，不用模板？需要多少模板呢？您的示例看起来很好，但这并不意味着我的代码不好。它只是更专注于OP所要求的集合。 - stefaanv

@280Z28：我只是在阐述一个观点。我认为人们足够聪明，可以理解这个意思。 - stefaanv