How to check that an element is in a std::set?

Question

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

Bloodcurdling

The only way to get simpler than that would be a boolean predicate: template <typename T> bool member(T const &item). And that would be implemented (under the covers) in terms of the line you are asking about. – Superfuse

Answer 1

Starting with C++20 you can use contains to check for existence in many STL containers such as std::map, std::set, ...:

const bool is_in = container.contains(element);

Pre C++20 the typical way was:

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

Rora

this is specific for sets and maps. vectors, lists etc. don't have a find member function. – Shipworm

@Shipworm Yea, you're right. Because looking for element in vector or list is inefficient O(N), there is no member function of find() implemented in vector or list. – Decompensation

IMO using count() is better because it is simply shorter and it converts to bool as noted in the answer by Pieter. I don't understand why this answer got accepted and so many points... – Mouthpiece

I had a code review comment where someone had used if (container.insert(foo).second == true) { //do something as this is the first time we've seen foo } I changed it to if (container.find(foo) == container.end) { //do something as this is the first time we've seen foo container.insert(foo); } The reviewer didn't like my change, but it seems more obvious to me what the intent is. – Pledget

For the sake of completeness: vectors/lists can use std::find: std::find(container.begin(), container.end(), element) != container.end(); O(N) problem remains, of course... – Runck

@MichaelMathews With your variant: 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... – Runck

@Огњен Шобајић count() is inefficient because it requires traversing the entire data structure. The find() stops when it finds one. If all you care about is whether the item is in the list or not, or you know there is only one copy in the list, never use count(). – Compact

@Compact you should check implementation of count. it does exactly the same as find, because the only thing it does is calling find and return value: return _M_t.find(__x) == _M_t.end() ? 0 : 1; – Eudoxia

@Eudoxia not on vector, which was the context of the comments trying to pick one mechanism for all the containers. – Compact

@Runck thank you for pointing about that important issue. – Pledget

there is a 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. – Bruce

@Bruce can't agree more. C++ STL has been totally outdated because of the lacking of semantic meaning. – Gadgetry

Answer 2

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://mcmap.net/q/80002/-how-to-check-that-an-element-is-in-a-std-set

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

Lisette

@Frerich that's only relevant for multiset and multimap I thought? Still good to point out though :) – Lisette

std::set is typically implemented with an ordered tree structure, so count() and find() will both have O(logn). Neither will iterate over all elements in the set. – Dropout

@FrerichRaabe - Are you certain? Since it's only possible for 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! – Giuliana

@DanNissenbaum Yes, you're exactly right (and so are +Peter and +Alan): for std::set, the two functions are equivalent in terms of performance. So even though the first part of my comment (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. – Weevily

I'd prefer find() even count() has same performance and more concise, because other developers might confuse why you're using count() when just checking if it is in the container. – Dunleavy

In GCC .count for set uses find: count(const key_type& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }. – Zamindar

Another argument on favor to find(): If the container type change all code using count() need to be fixed. But all find() code still work fine. – Tragus

why does std::set have count ? Can a set have the same element twice? – Dachau

I do somewhat agree Frerich in one sense - has() or contains() is far more self-documenting. Good thing we have that in C++20 :) – Misguidance

Wouldn't find() have an extra overhead of creating an iterator compared to count()? – Anoa

Answer 3

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++... ;)

Svend

What about sets? Usually you already have the element, but just want to check if it's in. – Keelykeen

Do you have any reference to whether this is the actual reason such a method/function is not included in the stl, or is it just your educated guess? – Auxochrome

@FabioA. It's my educated guess. – Svend

@ElazarLeibovich True, for std::set it's probably just done for consistency. – Svend

@Adhemar, consistency isn't exactly the strong side of STL... (list::remove, remove(makes_sense_only_for_vector, iterators)...) – Keelykeen

@ElazarLeibovich I totally disagree, std::remove algorithm works with any STL-like container, but does not physically remove the elements (because it doesn't know the internal structure of the container, i.e. a std::list is different from a std::vector). That's why the member erase (erase_after for forward_list) is used in conjunction with std::remove. Associative containers define their own versions of some algorithms (like remove, find etc) for reasons of efficiency: i.e., in a list, you just re-link the internal pointers, without performing the generic remove algorithm. – Perce

@Perce it'll sort-of work. But it doesn't make sense. For example, try using it on a list or slist. What would be the result? Is that ever desirable? – Keelykeen

@Perce and my point still stands. Only some containers have remove member. Consistency isn't the strong side of STL... – Keelykeen

@ElazarLeibovich I agree that some containers introduce member functions that specialize the algorithms (as algorithms are decoupled from containers don't know their structure, so cannot make use of the internal structure since the access is done only via iterators). And I agree that this may be inconsistent, however the std::algorithms work with all containers (restrictions on iterators, you cannot use sort for iterators that are not random). std::remove on list works, it does what it does on a std::vector, moves the end iterator basically. Do you have an example of strange behaviour? – Perce

@Perce when is std::remove(a_list.begin(), a_list.end()) useful? What does it actually do to the linked list? – Keelykeen

@ElazarLeibovich maybe I do not understand what you mean, sorry for the back and forth comments. Here is a live code comparing std::remove for both std::vector and std::list, and in my opinion it behaves identically in both cases ideone.com/Psbepy – Perce

It does not make sense to me not to include a feature because someone might use it incorrectly if they did not know what they were doing. Programming is for people that can think for themselves and are responsible for their code and its performance – Ignore

Note that C++20 introduces 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. – Misguidance

I disagree that "in most cases" you'd want to do something with the element. For sets, it is very common to simply check if a value is present. With maps, it is more likely that you'll want the corresponding value. – Unbridled

This answer does not make sense. The lack of contains() is because of poor STL design which used to emphasize too much on uniform interfaces rather than usability. C++20 fixes this. Please note that clear source code with clear semantics also contributes to efficiency. – Rushing

Nonsense. This question was specifically about std:;set and then there is no element associated to the key. – Holsinger

Answer 4

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";
    }
}

Ambert

Answer 5

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

Edit:

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

}

Parol

@Adhemar, it actually was inefficient, but not at all for the reason you mentioned. – Parol

@Paul: Make sure that you include the specialization for std::set, and remember that it's only appropriate if the only thing you need to know is existence. – Parol

@280Z28: std::begin(container)? What STL standard is that? It doesn't compile on my gcc. – Perversity

@stefannv: heh, it's new for C++0x. I added the implementation from my compiler above. – Parol

what about container.begin()? – Bloodcurdling

@Paul: That doesn't work for fixed length arrays. You'll have to either 1) change std::begin(container) to container.begin() (same for end) or 2) include the new utility functions at the bottom. – Parol

You may use boost::begin() and boost::end() from Boost range library. – Wirehaired

@280Z28, it's still inefficient for the reasons I did mention. – Svend

@Adhemar: If you know the set contains a value, then you already the value. The only reason you'd need the iterator is to erase the element from the set. If all you need is to know whether or not a collection contains a value, then this solution is no less efficient than any other solution. – Parol

@280Z28: That's a lot of ifs. I'm talking about the general case and explaining why this method is not provided by the STL. In many cases all you have is a key, and you're finding the associated value, or as you say you need the iterator to delete the element. – Svend

Answer 6

Since C++20, there is simply (and at last!) bool std::contains(const K&) https://en.cppreference.com/w/cpp/container/set/contains

Airel

Answer 7

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.

Tiffanitiffanie

Answer 8

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.

Parthenia

Yes, 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. – Servais

Answer 9

Write your own:

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

Perversity

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

@paul don't create static global functions. put your function in an anonymous namespace instead: that's the C++ way of creating functions that won't link into other compilation units. also, your T parameter should be a const reference, for const-correctness and for efficiency. – Shipworm

-1: Not templated and not at all in STL style. This is fine if you aren't using STL, but if you are using STL you should at least attempt to follow its standards. – Parol

@Shipworm but what if I want it inline? – Bloodcurdling

@280Z28 Could you give us your version? I'm not really familiar with STL style... – Bloodcurdling

@280Z28: I'm sorry that my code is not to your standards, I was just showing that if you don't like STL's interface, you can write your own. Jeez, not templated? How templated does it have to be? Your example looks fine, that doesn't mean that mine is bad. It is just more focused on the set as was asked by the OP. – Perversity

@stefannv: I know I'm picky on things other people aren't. I just hate downvotes without an explanation, so I gave mine. For what it's worth, if you gave that solution in an interview, it'd be a serious step towards the "hire" side. It's practical, succinct, and efficient, I just think the name is not as intuitive as it could be, it could apply to more containers, and the parameters are in the opposite order of several other functions. – Parol

@280Z28: I was just making a point. I thought that people would be intelligent enough to get the picture. – Perversity

Answer 10

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.

Oleaster

Sorry I can't really write block code in comment but what about template<typename CONTAINER, typename CONTAINEE> bool contains(const CONTAINER& container, const CONTAINEE& needle) { return find(container.begin(), container.end(), needle) != container.end(); – Bloodcurdling

It's not working, because std::vector needs an additional allocator as template argument and std::set needs an allocator and a less template argument. These lines woulkd work: template<template<class,class> class STLContainer, class T, class A> bool contains( STLContainer<T,A> container, T elt ) { return find( container.begin(), container.end(), elt ) != container.end() ; } template<template<class,class,class> class STLContainer, class T, class L, class A> bool contains( STLContainer<T,A,L> container, T elt ) { return find( container.begin(), container.end(), elt ) != container.end() ; } – Commines

Answer 11

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

Trussell

Answer 12

//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.
 }

Blakemore