Преобразование наборов целых чисел в диапазоны
Что самый идиоматический путь состоит в том, чтобы преобразовать ряд целых чисел в ряд диапазонов?
Например, учитывая набор {0, 1, 2, 3, 4, 7, 8, 9, 11} я хочу добраться {{0,4}, {7,9}, {11,11}}.
Скажем, мы преобразовываем из std::set<int> в std::vector<std::pair<int, int>>. Я рассматриваю Диапазоны как включительно с обеих сторон, так как это более удобно в моем случае, но я могу работать с открытыми диапазонами слишком при необходимости.
Я записал следующую функцию, но я испытываю желание изобретать велосипед. Скажите, возможно, существует что-то в STL или повышении для этого.
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);
}
3 ответа
Я не думаю, что в STL или Boost есть что-нибудь, что делает это.
Вы можете сделать свой алгоритм немного более общим:
template<class InputIterator, class OutputIterator>
void setToRanges(InputIterator first, InputIterator last, OutputIterator dest)
{
typedef std::iterator_traits<InputIterator>::value_type item_type;
typedef typename std::pair<item_type, item_type> pair_type;
pair_type r(-std::numeric_limits<item_type>::max(),
-std::numeric_limits<item_type>::max());
for(; first != last; ++first)
{
item_type i = *first;
if (i != r.second + 1)
{
if (r.second >= 0)
*dest = r;
r.first = i;
}
r.second = i;
}
*dest = r;
}
Использование:
std::set<int> set;
// insert items
typedef std::pair<int, int> Range;
std::vector<Range> ranges;
setToRanges(set.begin(), set.end(), std::back_inserter(ranges));
Вам также следует рассмотреть возможность использования термина interval вместо range , потому что последнее на языке STL означает «любую последовательность объектов, к которой можно получить доступ через итераторы или указатели» ( источник ).
Наконец, вам, вероятно, следует взглянуть на Библиотеку арифметических вычислений интервалов ускорения , которая в настоящее время находится на рассмотрении для включения в нее.
Боюсь, что решения для сжатия нет, но есть альтернативный алгоритм.
Храните элементы в битовом векторе - O(n), если вы знаете максимальный элемент в начале и предварительно распределяете вектор.
Переведите этот вектор в вектор флагов точек перехода - эксклюзивно-или битовый вектор с битовой сдвинутой версией самого себя. Немного сложновато на границах слов, но все равно O(n). По логике, вы получаете новый ключ при старом max + 1 (переход обратно к нулям после того, как все ключи исчерпаны), поэтому хорошо бы предусмотреть это в предварительном распределении вектора.
Затем пройдитесь итерациями по битовому вектору, находя биты set. Первый установленный бит указывает на начало диапазона, второй - на конец, третий - на начало следующего диапазона и так далее. Может быть полезна следующая функция перебора битов (предполагается, что это 32-битный int)...
int Low_Bit_No (unsigned int p)
{
if (p == 0) return -1; // No bits set
int l_Result = 31;
unsigned int l_Range = 0xffffffff;
unsigned int l_Mask = 0x0000ffff;
if (p & l_Mask) { l_Result -= 16; } else { l_Mask ^= l_Range; }
l_Range &= l_Mask;
l_Mask &= 0x00ff00ff;
if (p & l_Mask) { l_Result -= 8; } else { l_Mask ^= l_Range; }
l_Range &= l_Mask;
l_Mask &= 0x0f0f0f0f;
if (p & l_Mask) { l_Result -= 4; } else { l_Mask ^= l_Range; }
l_Range &= l_Mask;
l_Mask &= 0x33333333;
if (p & l_Mask) { l_Result -= 2; } else { l_Mask ^= l_Range; }
l_Mask &= 0x55555555;
if (p & l_Mask) { l_Result -= 1; }
return l_Result;
}
Я бы использовал neighbour_find с предикатом, определяющим " смежность »как два непоследовательных элемента. Это решение не зависит от INT_MAX. По-прежнему кажется немного неуклюжим.
bool notSequential(int a, int b) { return (a + 1) != b; }
void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges)
{
std::set<int>::iterator iter = indices.begin();
std::set<int>::iterator end = indices.end();
int first;
while (iter != end)
{
first = *iter;
iter = std::adjacent_find(iter, end, notSequential);
if (iter != end)
{
ranges.push_back(std::make_pair(first, *iter));
++iter;
}
}
ranges.push_back(std::make_pair(first, *--iter));
}
Это проверяет на конец больше, чем необходимо. neighbour_find никогда не может вернуть последний элемент списка, поэтому увеличенный итератор никогда не будет end и, таким образом, все еще может быть разыменован. Его можно было бы переписать как:
void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges)
{
std::set<int>::iterator iter = indices.begin();
std::set<int>::iterator end = indices.end();
if (iter == end) return; // empty set has no ranges
int first;
while (true)
{
first = *iter;
iter = std::adjacent_find(iter, end, notSequential);
if (iter == end) break;
ranges.push_back(std::make_pair(first, *iter++));
}
ranges.push_back(std::make_pair(first, *--iter));
}