8
\$\begingroup\$

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;
}
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Snowbody Apr 13 '15 at 13:01
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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