How do you check that an element is in a set?
Is there a simpler equivalent of the following code:
myset.find(x) != myset.end()
How do you check that an element is in a set?
Is there a simpler equivalent of the following code:
myset.find(x) != myset.end()
The typical way to check for existence in many STL containers such as std::map
, std::set
, ... is:
const bool is_in = container.find(element) != container.end();
std::find(container.begin(), container.end(), element) != container.end()
; O(N) problem remains, of course...
Dec 1, 2016 at 14:15
if(container.find(foo) == container.end())
needs to do a tree lookup to find the element first - if not found, then you need to do a second tree lookup to find the correct insertion location. The original variant if(container.insert(foo).second) {...}
has the charm that it needs just one single tree lookup...
Dec 1, 2016 at 14:20
set.contains(x)
that returns a bool in the C++ 20 standard. I don't know why it's taken us until 2020 to get that in.
Another way of simply telling if an element exists is to check the count()
if (myset.count(x)) {
// x is in the set, count is 1
} else {
// count zero, i.e. x not in the set
}
Most of the times, however, I find myself needing access to the element wherever I check for its existence.
So I'd have to find the iterator anyway. Then, of course, it's better to simply compare it to end
too.
set< X >::iterator it = myset.find(x);
if (it != myset.end()) {
// do something with *it
}
C++ 20
In C++20 set gets a contains
function, so the following becomes possible as mentioned at: https://stackoverflow.com/a/54197839/895245
if (myset.contains(x)) {
// x is in the set
} else {
// no x
}
multiset
and multimap
I thought? Still good to point out though :)
set
to contain one member that matches, wouldn't the function be implemented in such as way as to stop after locating the first element, in this case, as Pieter points out? Useful answer in any case!
Mar 27, 2014 at 7:19
count()
never being faster than find()
) still holds, the second part is indeed not applicable to std::set
. However, I guess another argument can be made in favor of find()
: it's more expressive, i.e. emphasizes that you're trying to find an element instead of counting the number of occurrances.
Mar 27, 2014 at 8:19
.count
for set
uses find
: count(const key_type& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
.
Oct 24, 2017 at 11:43
Just to clarify, the reason why there is no member like contains()
in these container types is because it would open you up to writing inefficient code. Such a method would probably just do a this->find(key) != this->end()
internally, but consider what you do when the key is indeed present; in most cases you'll then want to get the element and do something with it. This means you'd have to do a second find()
, which is inefficient. It's better to use find directly, so you can cache your result, like so:
auto it = myContainer.find(key);
if (it != myContainer.end())
{
// Do something with it, no more lookup needed.
}
else
{
// Key was not present.
}
Of course, if you don't care about efficiency, you can always roll your own, but in that case you probably shouldn't be using C++... ;)
contains()
. Indeed there are plenty of reasons you might want to see whether something is in a set without actually obtaining an iterator to it. In fact, with a set, you can't do much with that iterator other than removing the element, which you can already do without a prior lookup anyway.
Jan 15, 2019 at 13:05
In C++20 we'll finally get std::set::contains
method.
#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";
}
}
If you were going to add a contains
function, it might look like this:
#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();
}
This works with std::set
, other STL containers, and even fixed-length arrays:
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));
}
As pointed out in the comments, I unintentionally used a function new to C++0x (std::begin
and std::end
). Here is the near-trivial implementation from 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);
}
}
std::set
, and remember that it's only appropriate if the only thing you need to know is existence.
Nov 9, 2009 at 17:00
Since C++20, there is simply (and at last!) bool std::contains(const K&)
https://en.cppreference.com/w/cpp/container/set/contains
You can also check whether an element is in set or not while inserting the element. The single element version return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the equivalent element already in the set. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent element already existed.
For example: Suppose the set already has 20 as an element.
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.
If the element is newly inserted than pair::first will point to the position of new element in set.
I use
if(!my_set.count(that_element)) //Element is present...
;
But it is not as efficient as
if(my_set.find(that_element)!=my_set.end()) ....;
My version only saves my time in writing the code. I prefer it this way for competitive coding.
count()
. Anybody unable to grasp that an integer-returning function used in a Boolean expression is testing for non-zero is going to have many, many other travails in the great sea of C/C++ idioms. And, as noted above, really should be as efficient for sets, which was the question.
Write your own:
template<class T>
bool checkElementIsInSet(const T& elem, const std::set<T>& container)
{
return container.find(elem) != container.end();
}
I was able to write a general contains
function for std::list
and std::vector
,
template<typename T>
bool contains( const list<T>& container, const T& elt )
{
return find( container.begin(), container.end(), elt ) != container.end() ;
}
template<typename T>
bool contains( const vector<T>& container, const T& elt )
{
return find( container.begin(), container.end(), elt ) != container.end() ;
}
// use:
if( contains( yourList, itemInList ) ) // then do something
This cleans up the syntax a bit.
But I could not use template template parameter magic to make this work arbitrary stl containers.
// NOT WORKING:
template<template<class> class STLContainer, class T>
bool contains( STLContainer<T> container, T elt )
{
return find( container.begin(), container.end(), elt ) != container.end() ;
}
Any comments about improving the last answer would be nice.
template<typename CONTAINER, typename CONTAINEE> bool contains(const CONTAINER& container, const CONTAINEE& needle) { return find(container.begin(), container.end(), needle) != container.end();
May 4, 2013 at 23:10
It's this, by a mile.
bool once(uintptr_t val) {
return visited.emplace(val).second;
}
How could it be otherwise?
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
//general Syntax
set<int>::iterator ii = find(set1.begin(),set1.end(),"element to be searched");
/* in below code i am trying to find element 4 in and int set if it is present or not*/
set<int>::iterator ii = find(set1.begin(),set1.end(),4);
if(ii!=set1.end())
{
cout<<"element found";
set1.erase(ii);// in case you want to erase that element from set.
}