On Sun, Mar 3, 2013 at 4:47 PM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
On Sun, Mar 3, 2013 at 7:38 PM, Martin Knoblauch Revuelta < mkrevuelta@gmail.com> wrote:
On Sun, Mar 3, 2013 at 3:22 AM, Jonathan Wakely <jwakely.boost@kayari.org> wrote:
[..] existing algorithms work with both standard and non-standard containers if they model the required concepts.
The containers we are proposing here are sequence containers. The computational complexity of their operations are somehow in between those of std::list and std::vector. They provide random access in O(log N) time _and_ insertion/removal in O(log N) time.
Therefore, their iterators are _not_ as random-access as those of std::vector. If we declare them random-access, existing algorithms will perform poorly on them. And if we declare them sequential-access (Bidirectional), it will be worse.
For example, if the contents of the iterator are sorted, we can make a binary search in O(log N) time, since the implementation is based on a self balanced tree. If we declare the iterators random-access, the existing binary_search algorithm will treat the sequence like a vector, and it will take O(log N log N) time.
The main point is that asymptotically this is much more efficient than linear search.
Do you mean that you would declare them RandomAccess iterators? We can expect to have containers with millions of elements. For that size, O(log N) is about 20 times faster than O(log N log N). That makes a big difference.
[..] I am not sure that adding a new category of an iterator will be helpful, since this can affect the generality of design and user algorithms. To some degree it is equivalent to the current C++ specification of computational complexities. This approach will make acceptable one class of augmented trees, but at the same time it will create problems for integration of other potentially useful data structures.
Yes, I perfectly understand that introducing a new iterator category is not as simple as editing a few lines. That's why I see this as the mayor obstacle for the integration of augmented trees with the style of the C++ Standard Library.
For example, suppose there is a new data structure that supports random access to elements with O(log(log N)) running time. Should we again introduce a new iterator category?
Well, for millions of elements, this means about "4 times slower than O(1)"... so... maybe? Best regards, MartÃn Knoblauch Revuelta