On Tue, Feb 19, 2013 at 11:56 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
On Wed, Feb 20, 2013 at 3:12 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Tue, Feb 19, 2013 at 2:04 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
[...]
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 :).
This = above or below? I guess below :)
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 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"). An operator[] which is O(log N) is not unusual (see std::map), much less "non-standard". Also, IIRC, one issue with an augmented data structure proposed in the (near) past was whether it was appropriate to classify the iterators as random access; I think such iterators (which have logarithmic-time advancement and differencing) are objectively *not* random access (according to the standard), but I agree there is a gap in the standard's iterator classification between random access and bidirectional iterators where an iterator of an augmented data structure may lie. As an event simpler example, a zip_iterator< bidirectional, random access > has *at least* bidirectional traversal, but additionally has constant-time differencing that's lost once an algorithm classifies the iterator as "simply" bidirectional. I think the present standard-endowed traversal categories are motivated by the standard-provided algorithms, so staying entirely within the standard, there probably isn't much need for further traversal granularity. Lastly, I think when you say "(non-)standard feature" you really mean "(non-)standard-*like* feature" (and I have thus far been interpreting such remarks more literally than you probably intended).
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.
Let's not forget such performance bugs are not restricted to the STL or even C++ :) http://thedailywtf.com/Articles/InternettoLowerCase.aspx 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.
But then how do you choose the Right Container For The Job among several choices with similar interfaces? 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.
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.
The solutions to current inefficiencies of STL
Can you provide examples of such inefficiencies?
are available through advanced data structures, but they are non-standard due to the specification of computational complexities for single operations.
:: mentally replacing "non-standard" with "non-standard-like" :: Sorry, I think I've veered too far from what your original gripe was. I'm still not clear what the problem is with developing and using "non-standard-like" containers (in the sense that maybe they don't offer the same complexity guarantees of its set of operations as other standard data structures...which I think calling them non-standard or non-standard-like is misleading but whatever). Something has to be changed in STL to take full advantage of these
solutions.
- Jeff