C ++ – implementación del árbol de intervalos

¿Alguien sabe alguna buena implementación del interval tree en C ++?

Obviamente, algo impulsado por la plantilla, mejor en estilo de boost .

Y otra pregunta: si alguien lo prueba, ¿una implementación básica del árbol de intervalos basada en std::vector con ordenación puede vencer al árbol de intervalos genérico (con operaciones O (lg)) en la práctica?

Boost-como? Boost ICL !

La biblioteca Boost Interval Container

Tenía exactamente la misma necesidad. No pude encontrar ninguna implementación adecuada (simple, moderna, portátil), así que utilicé una implementación de Python por Brent Pedersen como guía y escribí una versión barebones de C ++ . El IntervalTree se comporta como un contenedor STL estándar, con algunas advertencias debido a su simplicidad (sin iteradores, por ejemplo). Lo usa así (“T” es un tipo arbitrario):

 vector > intervals; // ... make intervals! IntervalTree tree(intervals); 

Y lo consultas de esta manera:

 vector > results; tree.findContained(start, stop, results); // results now contains Intervals which are fully contained in the query interval results.clear(); tree.findOverlapping(start, stop, results); // results now contains Intervals which overlap the query interval 

Parece que hay uno en el kit de herramientas NCBI C ++ .

Sin embargo, el jurado todavía está deliberando sobre si es “bueno” (e incluso si está basado en plantillas, todavía soy algo nuevo en C ++, así que no estoy del todo seguro de que lo sea, pero sospecho que sí).

Cargué la implementación simple de Interval Tree en github: https://github.com/coolsoftware/ITree

Mira la clase en itree.h.

si no te importa traducir la implementación de ac # a c ++, ve a http://code.google.com/p/intervaltree/ .based en un árbol de auto equilibrio avl.