C++

Forum

 
Why does std::set provide a .find() method that takes a reference to an item to be found?

ElusiveTau (152)
If you have the item you want to look for, what's the point of searching for it in a container?

Taking a shot at answering my own question:

The object itself isn't important but the state of std::set (i.e., what items are inside) is what matters.

For example, if you have some GUI code that displays a list of unread emails to the user, and the GUI reads from a std::set<Email> to determine what needs to be displayed in list view, then some other code that manages the lifetime of Email objects mind need to find and delete them from the set to update the user's view.

Is that it?
kigar64551 (814)
Why does std::set provide a .find() method that takes a reference to an item to be found?
std::set::find(const Key& key) takes a const reference to the Key object to be searched, because there is no point in passing the Key object by-value. Passing the Key object by-value (rather than by-reference) would effectively create and pass a copy of that object into the function – which is an unnecessary overhead here!

Or, in other words: In order to search a key in the set, it is perfectly sufficient to have a const reference to the Key object that is to be found. Why would you need a "full" local copy of that object?

For "simple" types, like int or long, it probably doesn't make much of a difference, in terms of performance, whether we pass a reference or a copy. But for "large" classes (objects) it can make a significant difference!

_____

If you have the item you want to look for, what's the point of searching for it in a container?

For example, because you want to know whether the set contains a given item? Suppose that you have a "whitelist" which is stored as a std::set<std::string>. Now, when you get some std::string as input, you have to check whether that given string is in the "whitelist" or not. std::set::find() does exactly that.

Note: std::set::find() does not find "the" Key object that you pass. It finds any Key object in the set that compares "equal" to the given Key object! So, for example, if we are searching for an std::string, then we will find any std::string object in the set whose text is "equal" to the given std::string object's text.

💡 Precisely, two objects (keys) are considered "equivalent", if neither object compares less than the other.
Last edited on
JLBorges (13770)
> If you have the item you want to look for, what's the point of searching for it in a container?

You have answered that question with the Email example.

Often, we want to look for an object, for which we do not have complete information. In this case, it is more convenient (and more efficient) to do a generic lookup based on an equivalent key.
https://en.cppreference.com/w/cpp/container/set/find overloads (3), (4)

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <iostream>
#include <set>
#include <string>
#include <string_view>

static_assert( __cpp_lib_generic_associative_lookup	== 201304L, // feature-test macro
               "this program expects std::set to support lookup with generic equivalent keys (C++14 or later)" ) ;

struct book
{
    std::string isbn ; // key
    std::string title ;
    std::string author ;
    // etc ...

    // two books are equivalent if their isbns are equivalent 
    friend auto operator <=> ( const book& a, const book& b ) noexcept { return a.isbn <=> b.isbn ; }

    // also support lookup with the generic key std::string_view (isbn) 
    friend auto operator <=> ( const book& bk, std::string_view key ) noexcept { return bk.isbn <=> key ; }
    friend auto operator <=> ( std::string_view key, const book& bk ) noexcept { return key <=> bk.isbn ; }
};

int main()
{
    // note: the set uses a transparent comparator (std::less<>). this is required
    // see: https://en.cppreference.com/w/cpp/utility/functional/less_void#Notes
    const std::set< book, std::less<> > set { { "1234", "abcd", "efgh" }, { "5678", "ijkl", "mnop" }, { "9999", "qqqq", "rrrr" } } ;

    if( const auto iter = set.find( "5678" ) ; iter != set.end() ) // C++14: find with a generic equivalent key
        std::cout << "found book with isbn == '5678'; title == '" << iter->title << "'\n" ;
}

http://coliru.stacked-crooked.com/a/697b09984e1afd5e
Peter87 (11235)
Finding out whether a value is present in a set is indeed a common operation. C++20 added a contains member functions to make this even easier.

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

But there are still reasons for find to exist.

- For consistency with other containers (std::set is essentially a std::map with only "keys" and no "values").

- To be able to remove or extract the element without having to search again.

- To be able to access the element that you found (It's possible to specify how you want the elements to be compared so the value you search with isn't necessarily equal to the element that you found).

- You could use the returned iterator to jump to the next or previous element (in sorted order) although this is probably much more common when using the lower_bound and upper_bound member functions.
Last edited on
Topic archived. No new replies allowed.