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.
The project
https://github.com/vstadnik/stl_ext_adv
http://dl.dropbox.com/u/51041088/stl_ext_adv_doc/index.html
focuses mainly on a generalized and unified computer representation of sequences using the augmented B+ trees. It provides the following STL extensions ..
The examples demonstrate how to improve the computational complexity from O(N) to O(log N) in the following applications and problems:
- numerical integration. - calculation of mean value and standard deviation; - calculation of weighted mean value;
I think O(log N) is misleading. Problem: I want to estimate the mean of N numbers in a file on my disk. Clearly I should al least present all of the number in that file al least once (O(N)) to a black box algorithm that computes the mean?