4

我有一个要求，我必须根据某些属性值更新图形前端的颜色。属性值有不同的范围......比如说 -30 到 -45，-60 到 -80 等等...... .所以，我需要一个可以存储这些范围（预填充它们）的数据结构......当我确定点时，我想知道该点在 O(1) 时间或 O 中的范围（logN）时间......所以，我的查询将由一个点组成，输出应该是包含该点的唯一范围......

我对范围树和段树感到困惑......我想在 c++ stl 映射之上构建树。

4

3 回答 3

6

你需要的是所谓的区间树。http://en.wikipedia.org/wiki/Interval_tree。不幸的是，您不能使用std::set<>O(log N) 插入、删除和查询，因为树节点需要包含额外的数据。您可以在此处阅读有关它们的信息http://syedwaqarahmad.webs.com/documents/t。cormen -_introduction_to_algorithms_3rd_edition.pdf 第 14.3 章。

相反，您可以使用提升。它有间隔容器库。

http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

于 2015-01-20T19:56:32.523 回答
1

也许这个库可以帮助你： https ://github.com/ekg/intervaltree

于 2015-01-20T19:57:11.433 回答
1

如果我理解正确，您可以使用 std::set 轻松完成此操作：

#include <iostream>
#include <set>


struct Interval {
    int min;
    int max;
};

struct ComInt {
    bool operator()(const Interval& lhs, const Interval& rhs){
        return lhs.max < rhs.min;
    }
};

std::set<Interval, ComInt> intervals = { { -10, -5 }, { -4, 4 }, { 5, 10 } };


int main() {
    int point = 3;
    Interval tmp = { point, point };

    auto result=intervals.find(tmp);
    if (result != intervals.end()) {

        std::cout << "Min:" << result->min << " - Max:" << result->max << std::endl;
    } else {
        std::cout << "No matching Interval found" << std::endl;
    }
}

当然你应该围绕它构建一个包装类

于 2015-01-20T20:21:00.050 回答