Boost logo

Boost :

Subject: Re: [boost] [range] [general] making member functionsSFINAE-friendly
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-02-20 06:38:21

On Wed, Feb 20, 2013 at 10:38 AM, Jeffrey Lee Hellrung, Jr. <
jeffrey.hellrung_at_[hidden]> wrote:

> On Tue, Feb 19, 2013 at 11:56 AM, Vadim Stadnik <vadimstdk_at_[hidden]>
> wrote:

> I think you're overgeneralizing and/or exaggerating. IIRC, the value of
> augmented data structures is certainly recognized (although I'm not sure of
> what you mean by "value...for STL").

There is some interest and there are discussions, but the fact is that
there are still no containers based on augmented data structures neither in
STL nor in Boost libraries. I do not understand this situation, since
augmenting of data structures is a relatively simple textbook method. This
is also interesting in the light of the other fact that the functional
language Haskell provides the augmented data structure Finger Tree. One of
the explanations I have found is the standardization of computational
complexities of operations for containers and iterators. The main point
that I wanted to make in this thread is about damaging effect of this
standardization on the generality of programming solutions and the
performance optimization using interchangeable types that offer different
performance guarantees.

> Sure, but that doesn't mean you won't have some informed ideas or concrete
> information on the frequency of *some* specific operations for *some* user
> algorithm. And this should certainly influence your design decisions,
> including which data structures are appropriate to use.
In a well managed software development process both design and
implementation can be fine-tuned. However, there is always unknown vector
of a future change associated with an enhancement request. The cost of
implementing such requests can be reduced with augmented data structures,
since they provide a wider set of efficient operations against basic data

> > The solutions to current inefficiencies of STL
> Can you provide examples of such inefficiencies?
The simplest performance test is

    std::distance ( pos, dist ) ;
    container.insert ( pos, value ) ;

it is discussed in details in this document:

Thank you for a number of useful comments. There are, of course, other
aspects of augmented data structures, but I think they would be better
discussed in a separate thread.

Vadim Stadnik

Boost list run by bdawes at, gregod at, cpdaniel at, john at