C++ std :: set用自定义lower_bound

Question

我该如何执行一个find()或lower_bound()功能std::set使用比较函数是独立于它的关键，使它仍然运行在O（log N）时间？

假设我定义数据类型foo两个变量x和y和具有使用x作为密钥值的std::set<foo>。

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内进行排序。

例如，给定3个foo(x,y)值内fooSet（2,5），（3,9）和（5,10），一个lower_bound()这需要y = 7作为搜索项将返回一个迭代指向（3,9 ）。

目前，我解决这个问题的方法是有两个std::set<foo> s，分别按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 - 你需要将它传递给类模板本身，因为它会在内部使用，以保持对象的顺序（因而使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是只有订购定制点，使您可以提供一个函数对象根据需要代替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

不符合std :: set，因为@Vittorio Romeo在他的回答中指出。

有一个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);