On Sun, Mar 3, 2013 at 11:57 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
On Sun, Mar 3, 2013 at 1:21 AM, Martin Knoblauch Revuelta < mkrevuelta@gmail.com> wrote:
[...]
It looks like you already gained quite significant experience in this area. Do you know any other reasons and/or concerns why augmented data structures should NOT be added to STL?
The main concern is the balance between the value they add and their cost. On one hand, which are the real-life applications where these containers would really help? In my opinion, the programming community has learned to solve zillions of problems with arrays, lists, search trees, heaps and hash tables. Now it's not easy to find a real-life problem where augmented trees provide a significantly faster solution. Though, they may allow amazingly simple, non-tuning, easier-to-code, solutions. On the other hand, in addition to the usual bloat, there is a deep concern regarding the possible incorrect use of these sequence containers. Lazy unexperienced programmers might misuse them as an all-purpose replacement of vector and list. If the standard library adopted them, it would be somehow advocating their use. If there were no real-life applications, then it would be advocating inefficiency.
[..] The discussion of augmented trees by Boost community is particularly interesting. Do you know if there was a formal Boost review of any variant of augmented data structures and/or containers?
There was an interesting discussion when I proposed it: http://boost.2283326.n4.nabble.com/proposal-Sequence-container-with-O-log-n-... http://boost.2283326.n4.nabble.com/proposal-Rank-List-old-name-AVL-Array-in-...
[..] I proposed for the Boost review array based augmented B+ trees and decided to postpone the review of dynamically allocated augmented B+ trees.
If you only plan to augment the tree with an integer, then this is perfectly reasonable. Though, if you plan to augment the trees with a data type that doesn't support subtraction ---like the interval trees of "Introduction to Algorithms", or something more complex--- it might be better to stick to a few children per node. Otherwise, deleting an element might require a lot of [potentially expensive] additions of a user-defined type. Best regards, MartÃn Knoblauch Revuelta