Konvertieren Sätze von ganzen Zahlen in Bereiche

Question

Was ist der idiomatische Weg, um eine Menge von ganzen Zahlen in eine Reihe von Bereichen zu konvertieren?

z. Bei der Menge {0, 1, 2, 3, 4, 7, 8, 9, 11} möchte ich {{0,4}, {7,9}, {11,11}} erhalten.

Nehmen wir an, wir konvertieren von std::set<int> in std::vector<std::pair<int, int>>. Ich behandle Ranges als inklusiv auf beiden Seiten, da es in meinem Fall bequemer ist, aber ich kann auch mit offenen Bereichen arbeiten, wenn nötig.

Ich habe die folgende Funktion geschrieben, aber ich fühle mich wie das Rad neu zu erfinden. Bitte sagen Sie, vielleicht gibt es etwas in STL oder Boost dafür.

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

Ich glaube nicht, dass es etwas in der STL oder Boost, die dies tut.

Eine Sache, die Sie tun können, ist Ihr Algorithmus etwas allgemeinere zu machen:

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

Verbrauch:

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

Sie auch interval statt range Verwendung des Begriffs in Betracht ziehen sollten, weil die Letzteres bedeutet im STL-Sprachgebrauch "jede Folge von Objekten, auf die durch Iteratoren oder Zeiger zugegriffen werden kann" (source).

Schließlich sollten Sie wahrscheinlich auf die Boost Interval Arithmetic Library betrachten, die derzeit für Boost-Aufnahme überprüft wird.

Answer 2

keine Lösung eingeschweißte ich Angst habe, aber ein alternativer Algorithmus.

Speichern Sie Ihre Artikel in einem Bitvektor - O (n), wenn Sie das maximale Element am Anfang kennen und den Vektor vorbelegen.

Übersetzen Sie diesen Vektor in einen Vektor von Übergangspunktflags - exklusiv - oder den Bitvektor mit einer bitverschobenen Version von sich. Etwas fummelig an den Wortgrenzen, aber immer noch O (n). Logischerweise erhalten Sie einen neuen Schlüssel mit dem alten max + 1 (der Übergang zurück zu Nullen, nachdem alle Ihre Schlüssel erschöpft sind), also ist es eine gute Idee, dies bei der Vorbelegung des Vektors zu berücksichtigen.

Dann durch den Bitvektor iterieren die gesetzten Bits zu finden. Das erste gesetzte Bit gibt den Beginn eines Bereichs an, das zweite das Ende, der dritte den Beginn des nächsten Bereichs und so weiter. Die folgende Bit-Hantieren Funktion (32-Bit-int vorausgesetzt) ​​kann nützlich sein, ...

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

I adjacent_find mit einem Prädikat verwenden würde, die „Adjazenz“ als zwei Elemente definiert, die nicht sequentiell sind. Diese Lösung hängt nicht von INT_MAX ab. Fühlt sich immer noch irgendwie klobig an.

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

Das testet gegen end mehr als notwendig. adjacent_find kann niemals das letzte Element einer Liste zurückgeben, daher wird der inkrementierte Iterator niemals end sein und kann daher immer noch dereferenziert werden. Es könnte umgeschrieben werden als:

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

Jetzt kann interval_set von Boost.ICL (Boost> 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; 
} 

Output:

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