Chuyển đổi bộ số nguyên thành phạm vi

Question

Cách thành ngữ nhất để chuyển đổi tập hợp số nguyên thành một tập hợp dải ô là gì?

Ví dụ: với tập hợp {0, 1, 2, 3, 4, 7, 8, 9, 11}, tôi muốn nhận {{0,4}, {7,9}, {11,11}}.

Giả sử chúng tôi đang chuyển đổi từ std::set<int> thành std::vector<std::pair<int, int>>. Tôi xử lý các phạm vi bao gồm cả hai bên, vì nó thuận tiện hơn trong trường hợp của tôi, nhưng tôi cũng có thể làm việc với phạm vi kết thúc mở nếu cần.

Tôi đã viết chức năng sau, nhưng tôi cảm thấy muốn phát minh lại bánh xe. Xin vui lòng cho biết có thể có một cái gì đó trong STL hoặc tăng cho việc này.

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

Tôi không nghĩ có bất kỳ thứ gì trong STL hoặc Boost thực hiện việc này.

Một điều bạn có thể làm là để thực hiện thuật toán của bạn một chút tổng quát hơn:

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

Cách sử dụng:

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

Bạn cũng nên xem xét sử dụng thuật ngữ interval thay vì range, bởi vì trong ngôn ngữ STL có nghĩa là "bất kỳ chuỗi các đối tượng nào có thể được truy cập thông qua các trình lặp hoặc con trỏ" (source).

Cuối cùng, bạn có thể nên xem xét số Boost Interval Arithmetic Library, hiện đang được xem xét để bao gồm Tăng cường.

Answer 2

Không có giải pháp rút gọn Tôi sợ, nhưng là một thuật toán thay thế.

Lưu trữ các mục của bạn trong một bitvector - O (n) nếu bạn biết mục tối đa lúc bắt đầu và preallocate vector.

Dịch vectơ đó thành vectơ của cờ điểm chuyển tiếp - độc quyền hoặc bitvector với phiên bản bithifted của chính nó. Hơi khó sử dụng ở ranh giới từ, nhưng vẫn O (n). Về mặt logic, bạn nhận được một khóa mới ở mức tối đa cũ + 1 (quá trình chuyển đổi về số không sau khi tất cả các khóa của bạn đã cạn kiệt), vì vậy bạn nên cho phép điều đó trong việc preallocation của vec-tơ.

Sau đó, lặp qua bitvector tìm bit thiết lập. Bit thiết lập đầu tiên cho biết sự bắt đầu của một phạm vi, kết thúc thứ hai, thứ ba bắt đầu của dãy tiếp theo và vân vân. Chức năng-bit không quan trọng sau đây (giả sử 32 bit int) có thể hữu ích ...

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

Tôi muốn sử dụng adjacent_find với một vị định nghĩa "kề" như hai yếu tố mà không phải là tuần tự. Giải pháp này không phụ thuộc vào INT_MAX. Vẫn cảm thấy hơi bối rối.

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

Kiểm tra đó chống lại end nhiều hơn mức cần thiết. adjacent_find không bao giờ có thể trả lại phần tử cuối cùng của danh sách, do đó trình lặp lặp lại sẽ không bao giờ là end và do đó vẫn có thể bị hủy đăng ký. Nó có thể được viết lại là:

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

Bây giờ người ta có thể sử dụng interval_set từ 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]}