Re: [Boost-users] std::list and intrusive_list

Subject: Re: [Boost-users] std::list and intrusive_list
From: strasser_at_[hidden]
Date: 2010-04-07 17:28:20

Zitat von Hicham Mouline <hicham_at_[hidden]>:
> Hello, I have say 10 (could very well be 1000) instances of const  
> std::list containers holding the same type T.T is a boost::tuple,  
> the first field of which is boost::gregorian::date, 4 other double  
> fields.All the lists are ordered by date. The first, last dates  
> ranges overlap across lists.The size of each list is of the order of  
> a 10000 entries. The lists may have different sizes.Further  
> development of the product may lead to millions of entries in each  
> list.The objective is to get a uniform set of 10 ranges of dates  
> from these 10 lists.That is, 1. we apply first an external  
> [start,finish] date range and reduce the viable entries in each list  
> to those included in this range.2. As start and finish might not  
> match a date present in some/all the lists, we further reduce this  
> date range until we find a range [actual_start, actual_finish] with  
> these bounds present in all the 10 lists.3. At this stage, we want  
> to take the union of all the dates available in all the 10 lists,  
> and where the dates are missing, set the entries to values from the  
> previous entry in the same list.As the lists are const, and may be  
> very large, I wish not to modify nor copy the lists to add the  
> missing dates in each of the 10 list.Instead I thought of adding a  
> second std::list for each of the 10 lists, and somehow treat the  
> combined 2 lists as 1 input, using a begin/end pair of iterators  
> that would iterate over the combined 2 lists as if they were 1  
> list.This is impossible to do if I also want to have these iterators  
> _be_ std::list<T>::iterator.However, if I relax this constraint, I  
> should be able to write a new iterator class (bidirectional like  
> list's) that take the 2 lists and would let me iterate over the  
> combination.Can Boost.Intrusive's list help with this?regards,

that was slightly confusing, but IIUC you need an iterator that merges  
multiple sorted ranges. you could write a boost::iterator_facade that  
uses a std::priority_queue to decide which of the underlying lists  
contains the next value.
if you can store the resulting list, you can use  
std::merge/std::inplace_merge instead.