On Wed, Feb 20, 2013 at 10:38 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Tue, Feb 19, 2013 at 11:56 AM, Vadim Stadnik <vadimstdk@gmail.com> 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 structures.
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: https://github.com/vstadnik/stl_ext_adv_review/blob/master/doc/doc/boost_com... 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. Regards, Vadim Stadnik