在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++中定义和搜索关联订单中的集合

回答

相关问题