-----Original Message-----
From: strasser@uni-bremen.de
Date: 07/04/2010 10:28 PM
To: boost-users@lists.boost.org
Subject: Re: [Boost-users] std::list and intrusive_list
Zitat von Hicham Mouline <hicham@mouline.org>;:
> 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.
_______________________________________________
All right, I will use a boost::iterator_facade.