रेंज

Question

में पूर्णांक के सेट को कनवर्ट करना पूर्णांक के सेट को पूर्णांक के सेट में कनवर्ट करने का सबसे बेवकूफ तरीका क्या है?

उदा। सेट {0, 1, 2, 3, 4, 7, 8, 9, 11} दिया गया है, मैं {{0,4}, {7, 9}, {11,11}} प्राप्त करना चाहता हूं।

मान लें कि हम std::set<int> से std::vector<std::pair<int, int>> में परिवर्तित कर रहे हैं। मैं रेंजों को दोनों तरफ शामिल करता हूं, क्योंकि यह मेरे मामले में अधिक सुविधाजनक है, लेकिन यदि आवश्यक हो तो मैं ओपन-एंडेड श्रेणियों के साथ भी काम कर सकता हूं।

मैंने निम्नलिखित फ़ंक्शन लिखा है, लेकिन मुझे पहिया को फिर से शुरू करने जैसा लगता है। कृपया बताएं कि एसटीएल में कुछ है या इसके लिए बढ़ावा है।

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

Answer 1

मुझे नहीं लगता कि एसटीएल या बूस्ट में ऐसा कुछ भी है जो ऐसा करता है।

एक बात आप कर सकते हैं अपने एल्गोरिथ्म थोड़ा और अधिक सामान्य बनाना है:

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

तुम भी, range के बजाय अवधि interval उपयोग करने पर विचार करना चाहिए, क्योंकि उत्तरार्द्ध में एसटीएल पार्लान्स का अर्थ है "ऑब्जेक्टर्स या पॉइंटर्स के माध्यम से एक्सेस किए जा सकने वाले ऑब्जेक्ट्स का कोई भी अनुक्रम" (source)।

अंत में, आपको शायद Boost Interval Arithmetic Library पर ध्यान देना चाहिए, जो वर्तमान में बूस्ट समावेशन के लिए समीक्षा अधीन है।

Answer 2

कोई संकुचित समाधान मैं डरता हूं, लेकिन एक वैकल्पिक एल्गोरिदम।

अपने आइटम को बिटकवेक्टर में स्टोर करें - ओ (एन) यदि आप शुरुआत में अधिकतम आइटम जानते हैं और वेक्टर को प्रीलाकेट करते हैं।

उस वेक्टर को संक्रमण बिंदु झंडे के वेक्टर में अनुवाद करें - अनन्य-या बिटकवेक्टर स्वयं के बिट्सफ़्ट संस्करण के साथ। शब्द सीमाओं पर थोड़ा सा झुकाव, लेकिन अभी भी ओ (एन)। तार्किक रूप से, आपको पुरानी अधिकतम + 1 पर एक नई कुंजी मिलती है (आपकी सभी चाबियाँ समाप्त हो जाने के बाद शून्य पर संक्रमण वापस आ जाता है), इसलिए वेक्टर के प्रीलोकेशन में इसके लिए अनुमति देना एक अच्छा विचार है।

फिर, सेट बिट्स खोजने वाले बिटकवेक्टर के माध्यम से पुनरावृत्त करें। पहला सेट बिट एक श्रेणी की शुरुआत इंगित करता है, दूसरा अंत, तीसरी अगली रेंज की शुरुआत और इसी तरह। निम्नलिखित बिट नगण्य समारोह (यह मानते हुए 32 बिट पूर्णांक) उपयोगी हो सकता है ...

int Low_Bit_No (unsigned int p) 
{ 
    if (p == 0) return -1; // No bits set 

    int   l_Result = 31; 
    unsigned int l_Range = 0xffffffff; 
    unsigned int l_Mask = 0x0000ffff; 

    if (p & l_Mask) { l_Result -= 16; } else { l_Mask ^= l_Range; } 
    l_Range &= l_Mask; 
    l_Mask &= 0x00ff00ff; 
    if (p & l_Mask) { l_Result -= 8; } else { l_Mask ^= l_Range; } 
    l_Range &= l_Mask; 
    l_Mask &= 0x0f0f0f0f; 
    if (p & l_Mask) { l_Result -= 4; } else { l_Mask ^= l_Range; } 
    l_Range &= l_Mask; 
    l_Mask &= 0x33333333; 
    if (p & l_Mask) { l_Result -= 2; } else { l_Mask ^= l_Range; } 
    l_Mask &= 0x55555555; 
    if (p & l_Mask) { l_Result -= 1; } 

    return l_Result; 
} 

Answer 3

मैं एक विधेय है कि "निकटता" को परिभाषित करता दो तत्वों है कि अनुक्रमिक नहीं कर रहे हैं के रूप में के साथ adjacent_find का उपयोग करेंगे। यह समाधान INT_MAX पर निर्भर नहीं है। अभी भी थोड़े घबराहट महसूस करता है।

bool notSequential(int a, int b) { return (a + 1) != b; } 

void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges) 
{ 
    std::set<int>::iterator iter = indices.begin(); 
    std::set<int>::iterator end = indices.end(); 
    int first; 
    while (iter != end) 
    { 
    first = *iter; 
    iter = std::adjacent_find(iter, end, notSequential); 
    if (iter != end) 
    { 
     ranges.push_back(std::make_pair(first, *iter)); 
     ++iter; 
    } 
    } 
    ranges.push_back(std::make_pair(first, *--iter)); 
} 

कि end के खिलाफ परीक्षण आवश्यकता से अधिक। adjacent_find कभी भी सूची का अंतिम तत्व वापस नहीं कर सकता है, इसलिए वृद्धि हुई इटरेटर कभी भी end नहीं होगा और इस प्रकार इसे अभी भी संदर्भित किया जा सकता है। यह फिर से लिखा जा सकता है के रूप में:

void setToRanges(const std::set<int>& indices, std::vector<Range>& ranges) 
{ 
    std::set<int>::iterator iter = indices.begin(); 
    std::set<int>::iterator end = indices.end(); 
    if (iter == end) return; // empty set has no ranges 
    int first; 
    while (true) 
    { 
    first = *iter; 
    iter = std::adjacent_find(iter, end, notSequential); 
    if (iter == end) break; 
    ranges.push_back(std::make_pair(first, *iter++)); 
    } 
    ranges.push_back(std::make_pair(first, *--iter)); 
} 

Answer 4

अब एक interval_set Boost.ICL से (उपयोग कर सकते हैं बूस्ट> 1।46)

#include <set> 
#include <iostream> 
#include <algorithm> 

#include <boost/icl/discrete_interval.hpp> 
#include <boost/icl/closed_interval.hpp> 
#include <boost/icl/interval_set.hpp> 

typedef std::set<int> Set; 
typedef boost::icl::interval_set<int> IntervalSet; 

void setToInterval(const Set& indices, IntervalSet& intervals) 
{ 
    Set::const_iterator pos; 
    for(pos = indices.begin(); pos != indices.end(); ++pos) 
    { 
     intervals.insert(boost::icl::construct<boost::icl::discrete_interval<int> >(*pos, *pos, boost::icl::interval_bounds::closed())); 
    } 
} 

int main() 
{ 
    std::cout << ">>Interval Container Library Rocks! <<\n"; 
    std::cout << "----------------------------------------------------\n"; 

    Set indices = {0, 1, 2, 3, 4, 7, 8, 9, 11}; 
    IntervalSet intervals; 

    setToInterval(indices, intervals); 

    std::cout << " intervals joined: " << intervals << "\n"; 

    return 0; 
} 

आउटपुट:

intervals joined: {[0,4][7,9][11,11]}