在C++中定義和搜索關聯訂單中的集合

我有一個n對象的集合。每個對象都有兩個數字屬性A和B。我知道A和B上的訂單是完全相關的：obj1.A > obj2.A當且僅當obj1.B > obj2.B。在C++中定義和搜索關聯訂單中的集合

如果我執行的收集由A整理一組，我可以在O(log n)支持以下操作：

插入
刪除
LOWER_BOUND上A

但屬性B的搜索std::lower_bound將是線性的，因爲集合不是s支持RandomAccessIterators。我知道我可以定義自己的二叉樹實現（例如：紅黑色或AVL），這些二叉樹可以在每個節點中存儲A和B值。通過這種方式，我可以在所有4項操作中使用O(log n)。

是否有一個更簡單（更高級別）的方法來有效地支持4個操作（搜索屬性，插入和刪除）？

來源

2016-11-15 Joseph Stack

你有權訪問C++ 14嗎？ – StoryTeller

是的。 C++ 14解決方案對我來說很好。 –

看看['std :: set :: lower_bound']（http://en.cppreference.com/w/cpp/container/set/lower_bound）如果你讓你的類與'B'比較，你可能能夠得到你想要的。它可能會需要一個小的幫助類（一個包裝你將比較'B'的整數）。 – StoryTeller

什麼，我在我的意見漫步約一個例子：

#include <set> 
#include <iostream> 

namespace test { 
    struct test { 
     int A; 
     int B; 
    }; 

    bool operator< (test const& lhs, test const& rhs) { 
     return lhs.A < rhs.A; 
    } 

    struct test_B { double B; }; 

    bool operator< (test const& lhs, test_B const& rhs) { 
     return lhs.B < rhs.B; 
    } 

    bool operator< (test_B const& lhs, test const& rhs) { 
     return lhs.B < rhs.B; 
    } 
} 

int main() { 

    std::set<test::test, std::less<void>> example { 
    {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6} 
    }; 

    std::cout << example.lower_bound<test::test_B>({3.5})->B; 

    return 0; 
}

C++ 14允許套到任何他們可以比較他們的關鍵撥打lower_bound。現在，我所做的只是創建一個類似於我的原始結構的包裝類型，但它看起來爲B值。實際上，我使set::lower_bound看起來像B而不是A，因爲它默認爲。

由於您的數字鍵是相關的，我懷疑你會得到承諾集性能lower_bound。

你可以看看它here

來源

2016-11-15 10:14:23 StoryTeller

@JosephStack，一定要打開-std = C++ 14，並且你用'std :: less ' – StoryTeller

定義你的集合Ok只是一個eclipse pb。現在，對'set :: lower_bound'和底層的'set'使用不同的模板參數的技巧在我的計算機上實際運行。但是，你知道這種行爲是否由標準保證？ –

@JosephStack [自C++ 14]（http://en.cppreference.com/w/cpp/container/set/lower_bound）。這些都在添加的函數模板中。如果您的密鑰只是一個字段，則此添加的目的是避免創建臨時對象。但是......只要可以進行比較，它允許在比較中使用任何類型。一個警告是，它必須是相同的訂單類型（從數學的角度來看），我相信這是你的情況。 – StoryTeller

我建議使用升壓多指標有在容器多個索引。

請參閱Multiple sorts on a single set教程。

來源

2016-11-15 10:33:58

在C++中定義和搜索關聯訂單中的集合

回答

相關問題