c++ - 为什么 set::find 不是模板？

Question

使用来自 <algorithm> 的模板函数你可以这样做

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

在std::set类似 find 的方法你必须传递一个 set::key_type 类型的对象这通常会迫使您创建一个虚拟对象。

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

如果可以只调用 foos.find(2) 会很有帮助. find有什么原因吗？不能是模板，接受所有可以传递给 less 谓词的东西。如果只是缺少它，为什么它不在 C++11 中(我认为不是)。

编辑

主要问题是为什么不可能，如果可能，为什么决定标准不提供它。第二个问题，你可以提出解决方法:-)(boost::multi_index_container 刚刚在我脑海中闪过，它提供了从值类型中提取键)

另一个构造值类型的例子。关键name是类型的一部分，不应用作映射键中的拷贝；

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适用于未排序的范围。所以您可以传递任何您想要的谓词。

std::set<T>始终使用 Comparator模板参数(默认为 std::less<T>)来维护集合的顺序，以及再次查找元素。

所以如果std::set::find是模板化的，它必须要求您只传递一个观察比较器总顺序的谓词。

然后，std::lower_bound以及适用于排序范围的所有其他算法都已经需要这样的要求，因此这不会是一个新的或令人惊讶的要求。

所以，我想这只是一个疏忽，没有 find_if() (说)std::set .建议为 C++17 :) (EDIT:: EASTL already has this ，他们使用了比我更好的名字:find_as)。

就是说，你知道 you shouldn't use std::set ， 你？在大多数情况下，经过排序的 vector 会更快，并且可以让您获得 std::set 所缺乏的灵 active 。 .

编辑: 正如 Nicol 所指出的，在 Boost 中有这个概念的实现。和 Loki (以及其他地方，我敢肯定)，但看到你不能利用他们的主要优势(内置的 find() 方法)，你不会失去太多通过使用裸体 std::vector .