Why is :: find not a template set?

Question

Using template functions from <algorithm> you can do such things

 struct foo { int bar, baz; }; struct bar_less { // compare foo with foo bool operator()(const foo& lh, const foo& rh) const { return lh.bar < rh.bar; } template<typename T> // compare some T with foo bool operator()(T lh, const foo& rh) const { return lh < rh.bar; } template<typename T> // compare foo with some T bool operator()(const foo& lh, T rh) const { return lh.bar < rh; } }; int main() { foo foos[] = { {1, 2}, {2, 3}, {4, 5} }; bar_less cmp; int bar_value = 2; // find element {2, 3} using an int auto it = std::lower_bound(begin(foos), end(foos), bar_value, cmp); std::cout << it->baz; } 

In std::set methods like find , you must pass an object of type set::key_type , which often forces you to create a dummy object.

 set<foo> foos; foo search_dummy = {2,3}; // don't need a full foo object; auto it = foos.find(search_dummy); 

It would be helpful if you could just foos.find(2) . Is there a reason why find cannot be a pattern, accepting anything that can be passed to a less predicate. And if it's just missing, why not in C ++ 11 (I think it's not).

Edit

The main question: WHY it is impossible, and if it were possible, WHY decided that the standard should not provide it. The second question you can suggest workarounds :-) ( boost::multi_index_container now sorting through my mind, which provides key extraction from value types)

Another example with more expensive value type construction. The name key is part of this type and should not be used as a copy in the map file;

 struct Person { std::string name; std::string adress; std::string phone, email, fax, stackoferflowNickname; int age; std::vector<Person*> friends; std::vector<Relation> relations; }; struct PersonOrder { // assume that the full name is an unique identifier bool operator()(const Person& lh, const Person& rh) const { return lh.name < rh.name; } }; class PersonRepository { public: const Person& FindPerson(const std::string& name) const { Person searchDummy; // ouch searchDummy.name = name; return FindPerson(searchDummy); } const Person& FindPerson(const Person& person) const; private: std::set<Person, PersonOrder> persons_; // what i want to avoid // std::map<std::string, Person> persons_; // Person searchDummyForReuseButNotThreadSafe; }; 

Answer 1

std::find_if works in an unsorted range. This way you can pass any predicate you want.

std::set<T> always uses the Comparator template argument ( std::less<T> by default) to preserve the order of the collection, and also to find the elements again.

So, if std::set::find was obscured by a pattern, it would only require you to pass a predicate that follows the general comparison order.

And again, std::lower_bound , and all other algorithms that work on sorted ranges, already require just that, so this will not be a new or unexpected requirement.

So, I guess this is just an oversight that there is no find_if() (say) on std::set . Suggest it for C ++ 17 :) ( EDIT:: EASTL already has this , and they used a much better name that I made: find_as ).

However, you know that you should not use std::set , right? In most cases, the sorted vector will be faster, and you will get the flexibility that std::set lacks.

EDIT: As Nicole noted, there are implementations of this concept in Boost and Loki (as in other places, I'm sure), but seeing that you can’t take advantage of them (built-in find() ), you won’t lose a lot by using bare std::vector .

Answer 2

The standard states that std::set::find has a logarithmic time complexity. In practice, this is achieved by implementing std::set as a binary search tree with strict weak ordering matching used as sort criteria. Any search that does not satisfy the same strict criteria of weak ordering will not satisfy the logarithmic complexity. So this is a design decision: if you want logarithmic complexity, use std::set::find . If you can trade complexity for flexibility, use std :: find_if in the set.

Answer 3

They provided what you want, but in a different way than you think.

Actually, there are two different ways: one - to build a constructor for the contained class, which 1) can be used implicitly, and 2) requires only a subset of the elements that you really need to compare. Using this location, you can search for foods.find(2); . As a result, you will create a temporary object from 2 , and then find this temporary object, but it will be temporary. Your code will not deal with it explicitly (anywhere).

Edit: what I'm talking about will create an instance of the same type as on the map, but (possibly) leaving any field that you don't use as a “key” not initialized (or initialized with something, saying no ) For instance:

 struct X { int a; // will be treated as the key std:::string data; std::vector<int> more_data; public: X(int a) : a(a) {} // the "key-only" ctor X(int a, std::string const &d, std::vector<int> const &m); // the normal ctor }; std::set<X> s; if (s.find(2)) { // will use X::X(int) to construct an `X` // we've found what we were looking for } 

Yes, when you create your X (or what I called X, one way or another) with a constructor with one argument, most likely, what you are building will not be used for anything other than search.

end edit]

The second, for which the library provides more direct support, is often a little simpler: if you really use only a subset of the elements (perhaps only one) to search, then you can create std::map instead of std::set . Using std::map searching for an instance of what you specify as the key type is supported explicitly / directly.

Answer 4

key_type is the type of member defined in the installation containers as the alias of the key, which is the first parameter of the template and the type of elements stored in the container.

See the documentation .

For custom types, the library does not know what the key type is. It so happened that for your specific use case, the key type is int . If you use set< int > s; , you can call s.find( 2 ); . However, you will need to help the compiler if you want to search for set< foo > and want to pass only an integer (think about how the ordering of set between foo and int will be performed).

Answer 5

Because if you want to do std::find(2) , you will need to determine how int will compare with foo in addition to comparing between two foo s. But since int and foo are different types, you will need two additional functions:

 bool operator<(int, foo); bool operator<(foo, int); 

(or other logical equivalent pair).

Now, if you do this, you are actually defining a bijective function between int and foo , and you could just use std::map<int, foo> and do it.

If you still don't want std::map , but you want to take advantage of the sorted search, then a dummy object is actually the easiest way.

Of course, the standard std::set can provide a member function to which you pass a function that gets foo and returns -1, 0, 1 if it is less, equal to or greater than normal. but it is not C ++. Note that even bsearch() accepts two arguments of the same type!