On 05/01/2011 04:08 PM, Francisco José Tapia wrote:
Technically this library is an implementation of a binary red-black counter tree. Colloquially is a balanced tree with an additional counter in each leaf. This permit the access to the elements by the position, like in a vector. It is a random access container.
This sounds really useful. I was wanting something like this the other day. I was working on some code for processing named items. Sometimes processing of an item will discover other items needing to be processed. We don't want to process an item twice. So I wrote something like: std::set<string> names_todo; std::set<string> names_done; names_todo.insert( initial set of names ); while ( ! names_todo.empty() ) { string name = remove_first_element(names_todo); // by ref // adds names to 'todo' and 'done' sets. process_name(name, names_todo, names_done); // by ref } But unfortunately always removing the "first" element of a tree is pretty much the worst-case in terms of rebalancing overhead. Probably most algorithms use a stack for the 'todo' list but I was passing in a set anyway and thought it might benefit from the deduplication. However, with your container I'd have decent access to an arbitrary element of the set. Then the part that was remove_first_element(set&) could instead be "remove randomly selected element from set". This way I'd expect average case rather than worst-case performance. What would be even cooler though would be operations like "give me an element among those most efficient to remove" and "most efficient to insert before/after". - Marsh