将整数集转换为范围

Question

将一组整数转换为一组范围的最惯用的方法是什么？

例如,给定{0,1,2,3,4,7,8,9,11}我想得到{{0,4},{7,9},{11,11}}.

让我们说我们正在转变std::set<int>为std::vector<std::pair<int, int>>.我认为Ranges在双方都是包容性的,因为在我的情况下它更方便,但如果有必要我也可以使用开放式范围.

我写了以下功能,但我觉得要重新发明轮子.请告诉我们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);
}

Answer 1

我认为 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 术语中的意思是“可以通过迭代器或指针访问的任何对象序列”（source）。

最后，您可能应该看看Boost Interval Arithmetic Library，目前正在审查是否包含 Boost。