Subject: Re: [boost] Review managers wanted for augmented data structures
From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2013-03-03 03:38:39
On Sun, Mar 3, 2013 at 3:22 AM, Jonathan Wakely
> [..] existing algorithms
> work with both standard and non-standard containers if they model the
> required concepts.
The containers we are proposing here are sequence containers. The
computational complexity of their operations are somehow in between
those of std::list and std::vector. They provide random access in
O(log N) time _and_ insertion/removal in O(log N) time.
Therefore, their iterators are _not_ as random-access as those of
std::vector. If we declare them random-access, existing algorithms
will perform poorly on them. And if we declare them sequential-access
(Bidirectional), it will be worse.
For example, if the contents of the iterator are sorted, we can make a
binary search in O(log N) time, since the implementation is based on a
self balanced tree. If we declare the iterators random-access, the
existing binary_search algorithm will treat the sequence like a
vector, and it will take O(log N log N) time.
Existing algorithms are tailored for the existing sequence containers.
In order to integrate the use of these new containers ---even as
non-standard containers--- we need the standard library to at least
acknowledge the possibility of their existence by declaring a new
Martín Knoblauch Revuelta
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk