将整数集转换为范围

2022-01-24 00:00:00 algorithm set range c++

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

What's the most idiomatic way to convert a set of integers into a set of ranges?

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

E.g. given the set {0, 1, 2, 3, 4, 7, 8, 9, 11} I want to get { {0,4}, {7,9}, {11,11} }.

假设我们正在从 std::set 转换为 std::vector.我将 Ranges 视为双方的包容性，因为在我的情况下它更方便，但如果需要，我也可以使用开放式范围.

Let's say we are converting from std::set<int> into std::vector<std::pair<int, int>>. I treat Ranges as inclusive on both sides, since it's more convenient in my case, but I can work with open-ended ranges too if necessary.

我已经编写了以下函数，但我想重新发明轮子.请告知 STL 中是否存在某些内容或对此进行了增强.

I've written the following function, but I feel like reinventing the wheel. Please tell maybe there's something in STL or boost for this.

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);
}

推荐答案

我认为 STL 或 Boost 中没有任何东西可以做到这一点.

I don't think there's anything in the STL or Boost that does this.

你可以做的一件事是让你的算法更通用一点:

One thing you can do is to make your algorithm a little bit more general:

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 用语中的意思是可以通过迭代器或指针访问的任何对象序列"(来源).

You should also consider using the term interval instead of range, because the latter in STL parlance means "any sequence of objects that can be accessed through iterators or pointers" (source).

最后，你应该看看 Boost Interval Arithmetic Library，目前正在审查 Boost 是否包含.

Finally, you should probably take at look at the Boost Interval Arithmetic Library, which is currently under review for Boost inclusion.

相关文章