On Thu, Feb 21, 2013 at 8:20 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
On 20-02-2013 12:38, Vadim Stadnik wrote:
On Wed, Feb 20, 2013 at 10:38 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@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.
We have no problem with containers that have different complexity guarantees for certain operations. As long as the complexities are clearly documented and explained.
This is very encouraging! Hopefully, one day Boost community will solve the challenging problem - how to add augmented, advanced and other data structures to the C++ STL. For the beginning, there are two libraries ("STL Extensions" and "Countertree") in Boost review schedule: http://www.boost.org/community/review_schedule.html I am asking if anyone could volunteer to become a review manager for any of these libraries. Regards, Vadim Stadnik