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

我該如何執行一個find()或lower_bound()功能std::set使用比較函數是獨立於它的關鍵，使它仍然運行在O（log N）時間？C++ std :: set用自定義lower_bound

假設我定義數據類型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)

來源

2017-03-17 Muhammad Irham Rasyidi

你不能直接自定義比較傳遞給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)); } 
};

來源

2017-03-17 11:46:47

哦查找。所以在我的問題中提到的例子中，該集合將如何構建（我的意思是實際代碼）？ –

@MuhammadIrhamRasyidi：哎呀，我誤解了你的問題 - 你已經把一個比較器傳遞給了'std :: set <...>'......好吧，當調用'std :: set時，沒有辦法使用與'yCompare'不同的比較器:: lower_bound'。 –

噢，夥計。我的想法之一是手動遍歷二叉搜索樹從根到葉，但我不知道如何做到這一點。 –

不符合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);

來源

2017-03-17 13:38:47 Caleth

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

回答

相關問題