Boost logo

Boost :

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2011-12-01 06:45:03

> You are right, if you mean the cost of construction of an advanced data
> structure, it is O(N log N). As soon as the required data have been written
> the sum and mean value of any consecutive elements can be found in O(log N)
> time. Please, have a look at performance tests of the fast algorithm
> accumulate() in the section:

The next solution works in O(1) and requires only O(N) for construction
template <typename T>
class accumulator {
  void init(std::vector<T> &elems) {
     sum.reserve(elems.size() + 1);
     for (std::vector<T>::iterator it = elems.begin(); it != elems.end();
++it) {
       sum.push_back(sum.back() + *it);

  T operator()(T first, T last) const {
    return sum[last+1] - sum[first];

  std::vector<T> sum;
I guess this solution is slightly better for those math targets you
mentioned above. It also works with any associative operation.


On Thu, Dec 1, 2011 at 11:42 AM, Thorsten Ottosen <
thorsten.ottosen_at_[hidden]> wrote:

> Den 30-11-2011 10:58, Vadim Stadnik skrev:
> Hi all,
>> Advanced data structures (ADS) offer useful STL extensions that are not
>> possible or not efficient with basic data structures, such as arrays,
>> linked lists and red-black trees.
> I'm interested. In particular, if the library can be integrated seamlessly
> with Boost.Accumulators and other libs, it seems very interesting.
> Are there variations of the trees that allow for other types of fast
> queries than just accumulate? If so, then there might be a generic way to
> incorporate them.
> -Thorsten
> ______________________________**_________________
> Unsubscribe & other changes:**
> mailman/listinfo.cgi/boost<>

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