C++ std::set 自定义 lower_bound

Question

我如何使用独立于其键的比较器函数在 std::set 上执行 find() 或 lower_bound() 函数，以便它仍然在 O(log N) 中运行时间？

假设我用两个变量 x 和 y 定义了一个数据类型 foo 并且有一个 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。这意味着我无法将 y 表示为 x 的函数，但在 fooSetX.

中也按 y 排序

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

目前，我解决这个问题的方法是使用两个 std::set<foo>，分别按 x 和 y 排序。每当我需要按 y 搜索时，我都会使用第二个 std::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)

Answer 1

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

这是 std::set template is defined:

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

Compare 是 only 排序自定义点，它允许您提供一个 函数对象 来比较您的对象希望代替 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)); }
};

Answer 2

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

有一个boost datastructure可以被不相关的成员查找，你可以这样定义

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

C++ std::set 自定义 lower_bound

C++ std::set with a custom lower_bound

c++

set

lower-bound

stdset