0

我将如何使用独立于其键的比较器函数对 a执行 a find()or函数，以使其仍以 O(log N) 时间运行？lower_bound()std::set

假设我foo用两个变量定义了一个数据类型x，y并且有一个std::set<foo>用作x键值的数据类型。

struct foo {
    int x, y;
    foo(int x, int y) : x(x), y(y) {}
};

struct xCompare {
    bool operator() (const foo& i, const foo& j) const {
        return i.x < j.x;
    }
};

// Within main()
std::set<foo, xCompare> fooSetX;

lower_bound()是否可以使用比较 的值或其他一些函数来执行二进制搜索y？

为了这个论点，假设x和y是唯一的并且彼此独立，并且给定两个foo变量foo1和foo2，如果foo1.x < foo2.x，那么foo1.y < foo2.y。这意味着 I 不能表达y为 的函数x，但也由ywithin排序fooSetX。

例如，给定 内的三个foo(x,y)值 (2,5)、(3,9) 和 (5,10) fooSet，作为搜索词的 alower_bound()将y = 7返回一个指向 (3,9) 的迭代器。

目前，我解决这个问题的方法是有两个s，分别由和std::set<foo>排序。每当我需要搜索时，我都会使用第二个.xyystd::set

struct yCompare {
    bool operator() (const foo& i, const foo& j) const {
        return i.y < j.y;
    }
};

// Within main()
std::set<foo, yCompare> fooSetY;

// Inserting elements
fooSetX.insert(foo(2,5)); fooSetY.insert(foo(2,5));
fooSetX.insert(foo(3,9)); fooSetY.insert(foo(3,9));
fooSetX.insert(foo(5,10)); fooSetY.insert(foo(5,10));

// lower_bound() with y = 7
std::set<foo>::iterator it = fooSetY.lower_bound(foo(0,7)); // points to (3,9)
4

2 回答 2

3

您不能直接将自定义比较器传递给std::set::lower_bound- 您需要将其传递给类模板本身，因为它将在内部用于维护对象的顺序（从而使std::set::lower_bound工作正常）。

以下是std::set模板的定义方式：

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

Compare是唯一允许您提供一个函数对象的排序定制点，该对象将根据需要比较您的对象，而不是std::less<Key>.

无法向std::set.

如果您想要对您的对象进行额外的排序以实现O(log N)查找，您可以使用另一个与原始结构保持同步的有序结构。指向第一组中使用不同比较器的对象的std::set指针可以工作。例子：

class MySet
{
private:
    std::set<Item, Comparator0> _set0;
    std::set<decltype(_set0.begin()), Comparator1> _set1;

public:
    void insert(Item x) 
    {
        auto res = _set0.insert(x);
        assert(res.second);

        _set1.insert(res.first);
    }

    const auto& lookup0(Key0 x) { return _set0.lower_bound(x); }
    const auto& lookup1(Key1 x) { return *(_set1.lower_bound(x)); }
};
于 2017-03-17T11:46:47.293 回答
1

正如@Vittorio Romeo 在他的回答中指出的那样，不是 std::set 。

有一个boost数据结构可以由不相关的成员查找，您可以定义为

struct foo {
    int x, y;
    foo(int x, int y) : x(x), y(y) {}
};

// helpers
struct x_tag {}; 
struct y_tag {};

boost::multi_index_container<
    foo,
    indexed_by<
        ordered_unique<tag<x_tag>, boost::multi_index::member<foo, int, &foo::x>>, // std::less<int> applied to foo::x
        ordered_unique<tag<y_tag>, boost::multi_index::member<foo, int, &foo::y>> // std::less<int> applied to foo::y
    >
> fooSet;

int an_x, an_y;
// lookup by x
fooSet.get<x_tag>().find(an_x);
fooSet.get<y_tag>().find(an_y);
于 2017-03-17T13:38:47.520 回答