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

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-03-03 06:03:58

On Sun, Mar 3, 2013 at 9:22 AM, Jonathan Wakely <jwakely.boost_at_[hidden]>wrote:

> 8:08 PM, "Vadim Stadnik" wrote:
> >
> > Is there an alternative of not integrating advanced data structures into
> > STL?
>
> Why do they need to be put "into STL"?
>
> Why can't they exist in addition to it, or alongside it?
>
>
In principle, this is a good option, since the class of advanced data
structures is very wide (for library design can be regarded as unlimited)
and it will be impossible to specify all data structures that support the
same interfaces, but have minor differences in topology and data scheme in
order to improve efficiency of specific container operations and user
algorithms. The problems with this option is that current STL does not
offer concepts of <sequence> or <set> that could be used in algorithms with
"third party" data structures.

> > Augmented trees are non-standard due to different performance guarantees.
>
> They're non-standard because they're not in the standard.
>
> > A more reasonable and practical approach to STL would be to provide a
> wide
> > set of interchangeable containers and data structures with different
> > performance guarantees and allow programmers to make decisions about the
> > most suitable containers for specific applications.
>
> That's exactly what the STL is. The STL is about iterators and
> algorithms and concepts, not a fixed set of predefined containers.
>
>
I agree that STL greatly improved representation of math concepts compared
to all previous libraries. Nevertheless, it is well known that its
containers are not completely interchangeable. First of all, this concerns
the concept of <sequence>, which is represented in STL (C++03) by three
types of containers with different interfaces: std::vector, std::list and
std::deque. The next level of generalization is achieved with augmented
trees that efficiently support the union of interfaces of all of these
types of STL containers.

> You've claimed the STL makes your containers "illegal" which is an odd
> claim that I can't agree with. Extending the STL with alternative
> containers is not just acceptable, I'm pretty sure it was intended by
> Stepanov et al.
>
>
I do not understand this statement. Because of ".. NOT just acceptable", it
sounds like Stepanov et al. are responsible for STL being non-extendable,

> If your containers don't meet the complexity requirements of an
> Associative Container as defined in the standard that's fine, just
> don't claim it is an Associative Container and there shouldn't be a
> problem, surely.
>
>
The case of associative containers is particularly illustrative. Basic
search trees that currently support these types of containers are
acceptable. However, the augmented variants of these trees that offer
improved access to "n-th element" are not acceptable. Why should we avoid
calling such containers associative when they use augmented trees
(equivalent to improved trees) instead of basic trees? Just because they
offer more efficient operations?
Yes, that's correct! This conclusion follows from the C++ standard
specification of computational complexities for single operations. This is
an illustration how STL becomes unfriendly to more useful data structures.

> I don't understand why you think there are objections to non-standard
> containers. The containers in the standard are not suitable for all
> situations and are not the only choices, if there's a more suitable
> non-standard container then using it makes sense. This doesn't put the
> STL "under pressure", it proves its value, because existing algorithms
> work with both standard and non-standard containers if they model the
> required concepts.
>
>
IMO, STL is fundamentally very strong !
First of all because of excellent interfaces. The problem is that it is not
friendly to data structures that can make this library even better: improve
efficiency of user algorithms and generalization of math concepts.

The advantages of augmented data structures become obvious when they are
tested in solutions to real problems. For everyone who is yet skeptical
about usefulness of these data structures I would suggest to solve the
following classical Josephus problem:

http://en.wikipedia.org/wiki/Josephus_problem

The performance test using two operations std::advance() and
container.insert()) discussed in

http://dl.dropbox.com/u/51041088/stl_ext_adv_review/doc/doc/boost_comparison.html
https://github.com/vstadnik/stl_ext_adv_review/blob/master/doc/doc/boost_comparison.html
>

is a variant of algorithm for this type of problems with the difference
that elements are not erased, but inserted into a container. Every STL and
Boost container shows quadratic O(NxN) running time, whereas containers
using augmented data structures have O(N logN) running time.

Regards,
Vadim Stadnik