需要：用於維護範圍的一維列表的C++類

Question

我正在尋找一個可以維護範圍的一維列表的C++類。

每個範圍被定義爲一個(start,len)對。

我希望能夠添加額外的擴展到列表並自動合併。也就是說，如果我們在列表中有(0,5)和(10,5)，並且添加了(5,5)，則新列表只應包含(0,15)。

範圍永遠不會從列表中刪除。

這樣的事情是否存在？

謝謝。

Answer 1

您正在尋找Boost.Icl。它完全符合你所描述的。

http://www.boost.org/doc/libs/1_52_0/libs/icl/doc/html/index.html

Answer 2

下面是一個示例實現一個簡單的間隔容器：

#include <iostream> 
#include <vector> 
#include <memory> 
#include <algorithm> 

using std::vector; 
using std::pair; 
using std::make_pair; 

typedef pair<int, int> interval;  

struct interval_container 
{ 
    void add(int start, int len) 
    { 
     _data.emplace_back(make_pair(start, len)); 
    } 

    void consolidate() 
    { 
     // sort intervals first by start then by length 
     std::sort(_data.begin(), _data.end()); 

     // create temp data 
     vector<interval> consolidated; 

     // iterate over all sorted intervals 
     for(const interval& i : _data) 
     { 
      int start = i.first; 
      int len = i.second; 

      // special case: first interval 
      if (consolidated.empty()) 
      { 
       consolidated.emplace_back(i); 
      } 
      // all other cases 
      else 
      { 
       // get last interval in the consolidated array 
       interval& last = consolidated.back(); 
       int& last_start = last.first; 
       int& last_len = last.second; 


       // if the current interval can be merged with the last one 
       if ((start >= last_start) and (start < (last_start + last_len))) 
       { 
        // merge the interval with the last one 
        last_len = std::max(last_len, (start + len - last_start)); 
       } 
       // if the current interval can't be merged with the last one 
       else 
       { 
        consolidated.emplace_back(i); 
       } 
      } 
     } 

     // copy consolidated data 
     _data = consolidated; 
    } 


    vector<interval>& data() { return _data; } 

private: 
    vector<interval> _data; 
}; 


int main() 
{ 
    interval_container intervals; 

    intervals.add(0, 2); 
    intervals.add(1, 3); 
    intervals.add(5, 3); 

    intervals.consolidate(); 

    int c(0); 
    for(interval i : intervals.data()) 
    { 
     std::cout << (c++) << ": from " << i.first << " to " << (i.first + i.second) << std::endl; 
    } 
}