6

使用模板功能，<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);

如果可以调用 just 会非常有帮助foos.find(2)。有什么理由find不能成为模板，接受可以传递给 less 谓词的所有内容。如果它只是丢失了，为什么不在 C++11 中（我认为不是）。

编辑

主要问题是为什么不可能，如果可行，为什么决定标准不提供它。您可以提出解决方法的第二个问题:-)（boost::multi_index_container我刚刚想到，它提供了从值类型中提取的键）

另一个构造值类型更昂贵的示例。keyname是 type 的一部分，不应该作为 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;

};
4

5 回答 5

3

std::find_if适用于未排序的范围。所以你可以传递任何你想要的谓词。

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

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

再说一遍，std::lower_bound所有其他在排序范围上工作的算法已经完全需要这个，所以这不是一个新的或令人惊讶的要求。

所以，我想这只是一个疏忽，没有find_if()（说）在std::set. 为 C++17 提出它 :) （编辑：： EASTL已经有了这个，而且他们使用的名称比我做的要好得多：） find_as。

也就是说，你知道你不应该使用std::set，对吗？在大多数情况下，排序的向量会更快，并为您提供您发现缺乏的灵活性std::set。

编辑：正如 Nicol 指出的那样，在Boost和Loki（以及其他地方，我敢肯定）中有这个概念的实现，但是看到你不能使用它们的主要优势（内置find()方法），你使用裸机不会损失太多std::vector。

于 2012-06-17T00:13:58.830 回答
2

该标准规定std::set::find具有对数时间复杂度。在实践中，这是通过实现std::set为二叉搜索树来实现的，其中严格的弱排序比较用作排序标准。任何不满足同样严格的弱排序标准的查找都不会满足对数复杂度。所以这是一个设计决策：如果您想要对数复杂度，请使用std::set::find. 如果您可以用复杂性换取灵活性，请在场景中使用std::find_if。

于 2012-06-17T06:13:05.807 回答
1

他们已经提供了您想要的东西，但方式与您正在考虑的方式完全不同。

实际上，有两种不同的方法：一种是为包含的类构建一个构造函数，1）可以隐式使用，2）只需要你真正需要比较的元素子集。有了这个，您可以搜索foods.find(2);. 您最终将创建一个临时对象2，然后找到该临时对象，但这将是一个真正的临时对象。您的代码不必显式（在任何地方）处理它。

编辑：我在这里谈论的是创建一个与您在地图中存储的类型相同的实例，但（可能）将您未使用的任何字段作为未初始化（或已初始化）的“键”说“不存在”的东西）。例如：

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
}

是的，当你X用单参数构造函数构造你的（或者我称之为 X 的东西）时，你构造的东西很可能除了搜索之外不能用于任何事情。

结束编辑]

第二个，库提供了更直接的支持，通常更简单一些：如果你真的只使用元素的一些子集（可能只有一个）进行搜索，那么你可以创建一个std::map而不是std::set. 使用std::map，显式/直接支持搜索您指定为键类型的任何实例。

于 2012-06-16T21:03:12.073 回答
0

key_type 是集合容器中定义的成员类型，作为Key 的别名，它是第一个模板参数，也是容器中存储的元素的类型。

请参阅文档。

对于用户定义的类型，库无法知道键类型是什么。碰巧对于您的特定用例，键类型是int. 如果你使用 aset< int > s;你可以调用s.find( 2 );. 但是，如果您想搜索 aset< foo >并且只想传入一个整数，则需要帮助编译器（想想和 aset之间的排序如何工作）。fooint

于 2012-06-16T20:48:39.193 回答
0

因为如果你想这样做，除了两个s之间的比较之外，std::find(2)你还必须定义如何int进行比较。但由于和是不同的类型，您实际上将需要两个附加功能：foofoointfoo

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

（或其他一些逻辑等效对）。

现在，如果你这样做，你实际上是在and和之间定义一个双射函数，你也可以简单地使用 a and be done。intfoostd::map<int, foo>

如果您仍然不想要std::map但想要排序搜索的好处，那么虚拟对象实际上是最简单的方法。

当然，该标准std::set可以提供一个成员函数，您向该函数传递一个接收 afoo并返回 -1, 0, 1 如果它小于、等于或大于搜索到的函数......但这不是 C++ 方式。请注意，甚至bsearch()需要两个相同类型的参数！

于 2012-06-17T00:33:31.010 回答