stl — интервал диапазона дерева данных структуры переполнения стека
У меня есть требование, где я должен обновить цвет графического интерфейса на основе некоторого значения атрибута. Значение атрибута имеет разные диапазоны …. скажем, от -30 до -45, от -60 до -80 и так далее …. Итак, мне нужна была структура данных, в которой я мог бы хранить эти диапазоны (предварительно заполнить их) …. И когда я определю точку, я хотел бы знать диапазон, в котором эта точка попадает либо в O (1) Time, либо в O (logN) time …. Таким образом, My Query будет состоять из одной точки, и на выходе должен быть уникальный диапазон, содержащий эту точку …
Я запутался между деревьями диапазонов и деревьями сегментов …. я хочу построить дерево поверх c ++ stl map.
Решение
То, что вам нужно, называется интервальным деревом. 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
Другие решения
Может быть, эта библиотека поможет вам:
https://github.com/ekg/intervaltree
Если я вас правильно понимаю, вы можете легко это сделать с помощью 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;
}
}
конечно, вы должны построить класс-оболочку вокруг него