转换整数集到的范围 [英] Converting sets of integers into ranges

问题描述

什么是最地道的方式转换成一个整数集为一组范围？

例如。给出的集合{0，1，2，3，4，7，8，9，11}我想要得到{{0,4}，{7,9}，{11,11}}。

比方说，我们是从 STD转换::设为＆LT; INT＆GT; 到的std ::矢量＆lt;的std ::对＆LT; INT，INT＆GT; ＆GT; 。 我把范围为包容性的两侧，因为这是在我的情况比较方便，但我可以用开放式的范围，必要时工作了。

我已经写了下面的函数，但我觉得像重新发明轮子。 请告诉也许有什么东西在STL或升压这一点。

 的typedef的std ::对＆LT; INT，INT＆GT;范围;

无效setToRanges（常量的std ::设为＆LT; INT＆GT;＆安培;指数的std ::矢量＆lt;范围和GT;＆安培;范围）
{
    范围R =的std :: make_pair（-INT_MAX，-INT_MAX）;

    BOOST_FOREACH（INT I，索引）
    {
           如果（ⅰ！= r.second + 1）的
           {
            如果（r.second＆GT; = 0）ranges.push_back（r）的;
            r.first =我;
           }

           r.second =我;
    }

    ranges.push_back（r）的;
}
 

解决方案

我不认为有在STL或升压，做这样的事。

一件事你可以做的是让你的算法多一点点普遍：

 模板＆LT;类InputIterator的，一流的输出迭代器＆GT;
无效setToRanges（InputIterator的第一，InputIterator的最后输出迭代器DEST）
{
    类型定义的std :: iterator_traits实现＆LT; InputIterator的＆GT; :: value_type的ITEM_TYPE;
    的typedef类型名的std ::对＆LT; ITEM_TYPE，ITEM_TYPE＆GT; pair_type;
    pair_type R（-std ::  -  numeric_limits的LT; ITEM_TYPE＆GT; :: MAX（）
                -std ::  -  numeric_limits的LT; ITEM_TYPE＆GT; :: MAX（））;

    为（;！先=最后++第一）
    {
        ITEM_TYPE I = *第一;
        如果（ⅰ！= r.second + 1）的
        {
            如果（r.second＆GT; = 0）
                * DEST = R;
            r.first =我;
        }
        r.second =我;
    }
    * DEST = R;
}
 

用法：

 的std ::设为＆LT; INT＆GT;组;
//插入项目

类型定义的std ::对＆LT; INT，INT＆GT;范围;
的std ::矢量＆lt;范围和GT;范围;

setToRanges（set.begin（），set.end（），性病:: back_inserter（范围））;
 

您也应该考虑使用期限的间隔而不是范围，因为后者在STL的说法是指任何可以通过迭代器或指针（源）。

被访问的对象的序列

最后，你应该考虑在看的升压区间运算库，目前正在审查升压包容。

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

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

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.

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

解决方案

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

Usage:

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

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).

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

这篇关于转换整数集到的范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！