Re: [boost] [stl_ext_adv] ] Interest in advanced data structures

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
step:
template <typename T>
class accumulator {
public:
  void init(std::vector<T> &elems) {
     sum.reserve(elems.size() + 1);
     sum.push_back(0);
     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];
  }

private:
  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.

Andrii

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: http://lists.boost.org/**
> mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>
>