将整数集转换为范围

小编典典

将整数集转换为范围

algorithm

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

例如，给定集合{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);
}

阅读 307

2020-07-28

共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中，后者的意思是“可以通过迭代器或指针访问的任何对象序列”（源）。

最后，您可能应该看一下Boost
Interval算术库，该库目前正在审查中是否包含Boost。

2020-07-28