Why is set::find not a template?

Question

With template functions from <algorithm> you can do things like this

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 have to 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 so helpful if one can call just foos.find(2). Is there any reason why find can't be a template, accepting everything that can be passed to the less predicate. And if it is just missing, why isn't it in C++11 (I think it isn't).

Edit

The main question is WHY isn't it possible and if it was posiible, WHY decided the standard not to provide it. A a second question you can propose workarounds :-) (boost::multi_index_container crosses my mind just now, which provides key extraction from value types)

Another Example with a more expensive to construct value type. The key name is part of the type and should not be used as a copy in maps key;

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 on an unsorted range. So you can pass any predicate you want.

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

So if std::set::find was templated, it would have to require that you only pass a predicate that observes the comparator's total ordering.

Then again, std::lower_bound and all the other algorithms that work on sorted ranges already require exactly that, so that would not be a new or surprising requirement.

So, I guess it's just an oversight that there's no find_if() (say) on std::set. Propose it for C++17 :) (EDIT:: EASTL already has this, and they used a far better name than I did: find_as).

That said, you know that you shouldn't use std::set, do you? A sorted vector will be faster in most cases and allows you the flexibility you find lacking in std::set.

EDIT: As Nicol pointed out, there're implementations of this concept in Boost and Loki (as well as elsewhere, I'm sure), but seeing as you can't use their main advantage (the built-in find() method), you would not lose much by using a naked std::vector.

Answer 2

The standard states that std::set::find has logarithmic time complexity. In practice this is accomplished by implementing std::set as a binary search tree, with a strict weak ordering comparison used as sorting criteria. Any look-up that didn't satisfy the same strict weak ordering criteria wouldn't satisfy logarithmic complexity. So it is a design decision: if you want logarithmic complexity, use std::set::find. If you can trade complexity for flexibility, use std::find_if on the set.