Re: [boost] Review managers wanted for augmented data structures

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
<jwakely.boost_at_[hidden]> wrote:
> [..] 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
iterator category.

Best regards,
Martín Knoblauch Revuelta