Cần thiết: Lớp C++ để duy trì danh sách các chiều dài 1 chiều

Question

Tôi đang tìm một lớp C++ có thể duy trì danh sách các chiều dài 1 chiều.

Mỗi phạm vi được định nghĩa là một cặp (start,len).

Tôi muốn có thể thêm các phần bổ sung vào danh sách và để chúng tự động hợp nhất. Tức là, nếu chúng tôi có (0,5) và (10,5) trong danh sách và (5,5) được thêm vào, danh sách mới chỉ nên chứa (0,15).

Không bao giờ bị xóa khỏi danh sách.

Có điều gì như thế này tồn tại không?

Cảm ơn.

Answer 1

Bạn đang tìm kiếm Boost.Icl. Nó thực hiện chính xác những gì bạn mô tả.

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

Answer 2

Dưới đây là một ví dụ về thực hiện một container khoảng đơn giản:

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