The iterators are not like the vector's itertors, but they are not like the list iterators. They permit you go directly to a position without travel all the previous nodes. It's a different type. You can do a std::sort over the data structure with good results. Really the ++operator and --operator are O(1), because involve a small number of nodes, and don't depend of the tree size. The polynomy of any algorith must be multiplied by logN. Then que quicksort is O ( (logN)²). This new type of iterator was not defined, because until now, it was not necessary. But now appear and we must name it, I name as random iterators wth access O(logN), If we agree any other name, I will use. It's a semantic problem only. In the same way, the interface of STL set , map , multiset and multimap is dangerous in a concurrent environment, because you obtain an iterator to a node, and before to access, other thread delete that node , and your program crash. We can wait until the C++ standard define a new interface or we can propose an interface, and begin to use, correct the failures, and learn with the experience, in order to obtain the best solution. When the standard define something, change and adapt. About the speed, mentioned for Chris. I examined briefly your code, I didn't understood what do some benchmarks. I will check. If your code is better, you will have all my support. i will clap the winner. But I need to examine. Let me some days, and I will say you my oppinion 2015-09-14 15:19 GMT+02:00 Neil Groves <neil@grovescomputing.com>:
You have Random access iterators with access time O(logN) ( you can run a std::sort over the data structure with good results).
Traversal operations are mandated to be Amortized O(1) for random-access iterators. If the traversal is O(log N) it isn't a random-access iterator. http://en.cppreference.com/w/cpp/concept/RandomAccessIterator
Neil
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost