On Sun, Mar 3, 2013 at 9:22 AM, Jonathan Wakely <jwakely.boost@kayari.org>wrote:
8:08 PM, "Vadim Stadnik" wrote:
Is there an alternative of not integrating advanced data structures into STL?
Why do they need to be put "into STL"?
Why can't they exist in addition to it, or alongside it?
In principle, this is a good option, since the class of advanced data structures is very wide (for library design can be regarded as unlimited) and it will be impossible to specify all data structures that support the same interfaces, but have minor differences in topology and data scheme in order to improve efficiency of specific container operations and user algorithms. The problems with this option is that current STL does not offer concepts of <sequence> or <set> that could be used in algorithms with "third party" data structures.
Augmented trees are non-standard due to different performance guarantees.
They're non-standard because they're not in the standard.
A more reasonable and practical approach to STL would be to provide a wide set of interchangeable containers and data structures with different performance guarantees and allow programmers to make decisions about the most suitable containers for specific applications.
That's exactly what the STL is. The STL is about iterators and algorithms and concepts, not a fixed set of predefined containers.
I agree that STL greatly improved representation of math concepts compared to all previous libraries. Nevertheless, it is well known that its containers are not completely interchangeable. First of all, this concerns the concept of <sequence>, which is represented in STL (C++03) by three types of containers with different interfaces: std::vector, std::list and std::deque. The next level of generalization is achieved with augmented trees that efficiently support the union of interfaces of all of these types of STL containers.
You've claimed the STL makes your containers "illegal" which is an odd claim that I can't agree with. Extending the STL with alternative containers is not just acceptable, I'm pretty sure it was intended by Stepanov et al.
I do not understand this statement. Because of ".. NOT just acceptable", it sounds like Stepanov et al. are responsible for STL being non-extendable,
If your containers don't meet the complexity requirements of an Associative Container as defined in the standard that's fine, just don't claim it is an Associative Container and there shouldn't be a problem, surely.
The case of associative containers is particularly illustrative. Basic search trees that currently support these types of containers are acceptable. However, the augmented variants of these trees that offer improved access to "n-th element" are not acceptable. Why should we avoid calling such containers associative when they use augmented trees (equivalent to improved trees) instead of basic trees? Just because they offer more efficient operations? Yes, that's correct! This conclusion follows from the C++ standard specification of computational complexities for single operations. This is an illustration how STL becomes unfriendly to more useful data structures.
I don't understand why you think there are objections to non-standard containers. The containers in the standard are not suitable for all situations and are not the only choices, if there's a more suitable non-standard container then using it makes sense. This doesn't put the STL "under pressure", it proves its value, because existing algorithms work with both standard and non-standard containers if they model the required concepts.
IMO, STL is fundamentally very strong ! First of all because of excellent interfaces. The problem is that it is not friendly to data structures that can make this library even better: improve efficiency of user algorithms and generalization of math concepts. The advantages of augmented data structures become obvious when they are tested in solutions to real problems. For everyone who is yet skeptical about usefulness of these data structures I would suggest to solve the following classical Josephus problem: http://en.wikipedia.org/wiki/Josephus_problem The performance test using two operations std::advance() and container.insert()) discussed in http://dl.dropbox.com/u/51041088/stl_ext_adv_review/doc/doc/boost_comparison... https://github.com/vstadnik/stl_ext_adv_review/blob/master/doc/doc/boost_comparison.html<https://github.com/vstadnik/stl_ext_adv_review> is a variant of algorithm for this type of problems with the difference that elements are not erased, but inserted into a container. Every STL and Boost container shows quadratic O(NxN) running time, whereas containers using augmented data structures have O(N logN) running time. Regards, Vadim Stadnik