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

Subject: Re: [Boost-users] std::list and intrusive_list
From: Hicham Mouline (hicham_at_[hidden])
Date: 2010-04-08 05:12:50

-----Original Message-----From: strasser_at_uni-bremen.deDate: 07/04/2010 10:28 PMTo: boost-users_at_lists.boost.orgSubject: Re: [Boost-users] std::list and intrusive_listZitat 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. _______________________________________________ All right, I will use a boost::iterator_facade. 
Thank you,