On Thu, Jul 10, 2014 at 4:44 AM, Aleksandr Kupriianov
Hi again, boost community! After some time of hesitating, I re-implemented the container. Shortly speaking, the container has interface like vector, but performs insertions/deletions much faster (random access, however, a bit slower). It takes O(log(N)) for insertions, deletions, random access, near O(1) for iterative access. It performs random insertions/deletions faster than vector in absolute values (not only in O() terms) on all range of container size.
Hi Aleksandr, IMO, the data structure and container that you developed are quite useful. Any data structure or container that outperforms std::vector<T> is important in practice, since std::vector<T> is the default and the most frequently used standard container. Linear computational complexity of its update operations can significantly affect performance of user algorithms. This is why I suggest keep improving your code and project. The first problem is that your files do not include Boost license. If you are planning to submit your project for Boost review please check this list of requirements: http://www.boost.org/development/requirements.html As for documentation, it is necessary to explain benefits of your data structure and container. It would be helpful to provide examples of applications in which the new container can replace std::vector<T> with significant performance gain. You can use already available examples discussed in my and other similar projects, but it would be even more impressive if you add some new examples. It is also highly desirable to include a section that explains the design of your data structure. One or two figures that illustrate the method of augmenting would help every interested programmer to better understand your achievements. Thank you for comparing performance with my containers. A bit later I will test your container and will write more comments. Regards, Vadim Stadnik