current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 8 down vote favorite

Given an array of ints, return a string identifying the range of numbers.

Example:

  • Input arr - [0 1 2 7 21 22 1098 1099]
  • Output - "0-2,7,21-22,1098-1099"

Is there any improvement possible in this implementation?

#include<iostream>
#include<vector>
#include<algorithm>
#include<sstream>

std::string  range_creator(std::vector<int> & vec)
{
    std::sort(std::begin(vec),std::end(vec));

    int first=vec.at(0);
    int prev=first-1;

    std::stringbuf buffer;
    std::ostream os (&buffer);

    for(auto &x : vec)
    {
       if(++prev == x)
           continue;
        else
        {

           if(first != --prev)
           {               
               os << first<<"-"<<prev<<",";
               prev=x;
               first=x;
           }
           else
           {
               os<<first<<",";
               prev=x;
               first=x;
           }


        }

    }
    if(first != prev)
    {
        os<<first<<"-"<<prev;
    }
    else
    {  
       os<<first; 
    }
    return buffer.str();
}

int main()
{
    std::vector<int> vec={0,1,2,7,8,9,10,21,22,23,24,25,27,1098,1099,1100,2000};
    std::cout<<range_creator(vec);

    return 0;
}
share|improve this question

2 Answers 2

up vote 4 down vote accepted

You can make good use of std::adjacent_find. Like this:

std::string range_creator(std::vector<int> & vec)
{
    auto first = std::begin(vec), last = std::end(vec);
    if(first == last)
        return "";
    std::sort(first, last);
    std::stringbuf buffer;
    std::ostream os (&buffer);
    while(true)
    {
        auto mid = std::adjacent_find(first, last,
                [](int x, int y){ return x + 1 != y; });
        if(mid == last)
            break;
        if(first == mid)
            os << *first << ",";
        else
            os << *first << "-" << *mid << ",";
        first = ++mid;
    }
    if(first == --last)
        os << *first;
    else
        os << *first << "-" << *last;
    return buffer.str();
}

I think my code is still subject to further improvements, but I'm no expert, so I'll leave it to the community.

share|improve this answer
3  
I don't like while(true) loops; I'd declare mid at function scope and initialize it both just before the loop, then at the very end of the loop, and have (mid != last) be the condition. –  Snowbody Apr 13 at 13:01
up vote 3 down vote

Suggestions:

  • You better not mix data processing with printing in algorithms, that's separation of concerns. So I divided your code into two parts.
  • Fixed multiple occurrences of numbers.
  • I used the iterator directly rather than accessing .at(0) before the loop. Your code segfaults when given an empty vector.
  • I used std::ostringstream instead of std::stringbuf and std::ostream.

I hope all situations are handled properly. Here is the code, self-contained, compilable and lightly tested:

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>

void getRangesFromList(std::vector<int> &list, std::map<int, int> &ranges)
{
    int min = -1, max = -1;
    std::sort(std::begin(list),std::end(list));
    std::vector<int>::const_iterator it;
    for (it=list.begin(); it!=list.end();++it) {
        if (max == -1) {
            max = *it;
            min = *it;
            continue;
        }
        if (*it == max+1) {//growing in our range
            max = *it;
            continue;
        } else { //finish range and reset
            ranges[min] = max;
            min = *it;
            max = *it;
        }
    }
    if (list.size())
        ranges[min] = max;
}

int main()
{
    std::vector<int> nums = {0,1,2,7,7,7,8,9,10,21,22,23,24,25,27,1098,1099,1100,2000};
    std::map<int, int> ranges;
    std::map<int, int>::iterator rr;
    std::ostringstream out;

    getRangesFromList(nums, ranges);
    std::cout << "Got ranges of size " << ranges.size() << std::endl;
    for(rr=ranges.begin(); rr != ranges.end(); ++rr) {
        if (rr != ranges.begin())
            out << ",";
        out << rr->first;
        if (rr->first != rr->second)
            out << "-" << rr->second;
    }
    std::cout << out.str() << std::endl;
    return 0;
}

Output:

Got ranges of size 6
0-2,7-10,21-25,27,1098-1100,2000
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.