Boost logo

Boost :

Subject: Re: [boost] [range] [general] making member functionsSFINAE-friendly
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-02-19 14:56:01

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

> On Tue, Feb 19, 2013 at 2:04 AM, Vadim Stadnik <vadimstdk_at_[hidden]>
> wrote:
> > On Tue, Feb 19, 2013 at 4:17 PM, Nathan Ridge <zeratul976_at_[hidden]
> > >wrote:
> > ...
> >
> > >
> > > This was discussed upthread. To summarize, the standard library
> > > makes the design choice of not providing certain operations
> > > if they cannot be implemented with a certain asymptotic
> > > complexity (for example, subtraction of two iterators if it
> > > cannot be implemented in constant time), and Boost is trying
> > > to be consistent with this design choice.
> > >
> > >
> > I agree that consistency of the library design is important, but the case
> > is not completely trivial. IMO, this design principle is only a
> theoretical
> > one. In practice, it is often unhelpful and counterproductive. Because of
> > this principle, STL and C++ miss the big selling point.
> >
> Okay, let's see why...
> > An end user (who pays for and uses a software product) is interested in
> the
> > best running time of an algorithm which is determined not only by costs
> of
> > specific operations, but also by their frequencies. Relatively small
> number
> > of inefficient operations does not affect the total computational cost of
> > an algorithm.
> >
> Sometimes, yes, I agree.
> Also, this design principle makes illegal advanced and/or augmented data
> > structures which are beneficial for many complex algorithms. For example,
> > insert() and erase() functions for a single element with O(log N) cost
> are
> > not allowed by the C++ standard, however, significantly less efficient
> O(N)
> > operations are allowed for std::vector.
> >
> I'm not really sure what to make of this paragraph. The standard makes some
> guarantees for std:: data structures, but you're free to provide your own
> augmented data structures with whatever complexity guarantees make sense,
> and I guarantee you wouldn't be violating any laws.
This is a bit non-standard interpretation of the C++ standard :).
Augmented data structures have been recently discussed a number of times by
Boost community, some of them are waiting for a review. There is a problem
of recognizing the value of augmented data structures for STL, since
formally, the subscript operator, function at() and iterators that support
std::distance() with O(log N) computational complexity are currently
non-standard features and thus many C++ professionals are at least cautious
about new data structures.

> I think that the current standard specifications for computational
> > complexities of operations are to some degree obsolete. They create
> > unnecessary restrictions that will be either amended or removed
> completely
> > in future versions of STL.
> >
> Strongly disagree, and you haven't provided any examples of these
> "unnecessary restrictions" (or you aren't being precise in what you mean).
> Much code and many algorithms rely on the constant-time random access of
> std::vector for their own complexity bounds; are you suggestion the
> standard should drop this complexity guarantee?
I can re-formulate the issue of STL design. After fixing for many years
numerous performance bottlenecks caused first of all by linear cost update
operations of std::vector, since it is the default STL container, I have
come to the following conclusion.

Right representation of math concepts through right interfaces is more
useful than specification of computational complexities of single
operations if a library provides a wide choice of interchangeable
containers. The design decisions based on the computational complexity of a
single operation are just not practical. At the design time of a library it
is not possible to know frequencies of all specific operations for all user
algorithms. The parameter of the total computational cost of a user
algorithm is more important in real life.

The solutions to current inefficiencies of STL are available through
advanced data structures, but they are non-standard due to the
specification of computational complexities for single operations.
Something has to be changed in STL to take full advantage of these

Vadim Stadnik

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