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,
Zitat von Hicham Mouline
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.
participants (2)
-
Hicham Mouline -
strasser＠uni-bremen.de