Boost logo

Boost :

From: Steven Watanabe (steven_at_[hidden])
Date: 2007-08-09 13:48:30


Eric Niebler <eric <at>> writes:

> It's not exactly what you're asking for, but if you want to modify a
> time_series in-place, you can do that with range_run_storage::set_at().
> It's a terrible way to build a series though, because you need to find
> the place in the series where this element should be inserted (could be
> O(log N)) and then insert it (could be O(N)).
> You seem to be asking for an ordered_append feature. That might be
> useful to add.
> > Is there some reason why this doesn't work? If I need the
> > other behavior I can always create a new series fill it and swap
> > myself.
> Fill it how? That's exactly what ordered_inserter is for! So you can
> see, ordered_inserter is necessary. But the name isn't right.

I would fill it using ordered_append.

> The reason for ordered_inserter's existence is that it is the fastest
> way to build a time_series from scratch, regardless of the internal
> representation. When you know elements are sorted, you can just bang
> them into a dense vector, sparse vector, map, or what-have-you -- very
> efficient. Once you have a time series, there are other ways to
> manipulate it.
> The reason for .commit() is that, since you're pushing in one datum at a
> time, there may be a more efficient intermediate representation than the
> final time series data structure. For the scenarios I've encountered,
> being able to efficiently build a series by pushing in one datum at a
> time is important.

Do you have an example where pushing them using a different
intermediate representation is significantly more efficient?
Even if there is such a case should we really use an interface
for insertion that departs from established practice even when
it isn't needed? Would it be possible to have a range assign
function template in addition to the inserter that takes a sequence
of tuples? Could this be as efficient as the current ordered inserter?

> The alternative would be use a range-based interface like the STL uses.
> E.g.:
> series.assign( from, to );
> Here, "from" and "to" can't really be iterators though, or, if they are,
> they should yield a 3-tuple of (value, offset, end offset). An interface
> like this is very unwieldy in signal processing, where you often collect
> data by polling a value at an interval.
> for(;;)
> series.push_back(poll_some_value(), last_time, current_time);
> Of course, push_back() may not be the most efficient way to build up
> some kinds of data structures. What the ordered_inserter gives is a way
> have something as efficient as a range-based assign() while retaining
> the poll-and-push-back convenience.
> Does that make sense?


std::vector<tuple<...> > elements;
    elements.push_back(make_tuple(poll_some_value(), last_time, current_time));


ordered_inserter inserter(series);
    *insert++ = make_tuple(poll_some_value(), last_time, current_time);

In Christ,
Steven Watanabe

Boost list run by bdawes at, gregod at, cpdaniel at, john at