¿Cuál es la forma más idiomática de convertir un conjunto de enteros en un conjunto de rangos?Conversión de conjuntos de enteros en rangos
E.g. dado el conjunto {0, 1, 2, 3, 4, 7, 8, 9, 11}, quiero obtener {{0,4}, {7,9}, {11,11}}.
Digamos que estamos convirtiendo de std::set<int>
en std::vector<std::pair<int, int>>
. Trato los rangos como inclusivos en ambos lados, ya que es más conveniente en mi caso, pero también puedo trabajar con rangos abiertos si es necesario.
He escrito la siguiente función, pero tengo ganas de reinventar la rueda. Por favor, díganos que hay algo en STL o impulso para esto.
typedef std::pair<int, int> Range;
void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges)
{
Range r = std::make_pair(-INT_MAX, -INT_MAX);
BOOST_FOREACH(int i, indices)
{
if (i != r.second + 1)
{
if (r.second >= 0) ranges.push_back(r);
r.first = i;
}
r.second = i;
}
ranges.push_back(r);
}
no puedo ver una técnica que es mayor que O (n) para este tipo de cosas. El único aumento en la velocidad sería integrar esto en su género (si está haciendo uno) – dangerstat
@dangerstat: bueno, esto hace surgir otra pregunta: si existe una estructura de datos que pueda almacenar eficientemente la lista de rangos (algún tipo de árbol, supongo?). Actualmente utilizo plain std :: set para almacenar información sobre qué elementos de la lista numerada están seleccionados. –
un conjunto es internamente un árbol – Manuel