David B. Held <dheld <at> codelogicconsulting.com> writes:
"Peter Palotas" <peter <at> smartbusiness.nu> wrote in message news:auto-000000364385 <at> statement.se...
I was wondering if there is any interest in a container that is a model of sequence (just like std::vector or std::list) and with an interface matching that of std::vector (maybe with minor differences due to effiency) but with different time complexities? [...]
Take a look at the policy-based map in the sandbox. I implement what I called "indexed nodes" which appear to give the complexity characteristics you describe. I'm not sure whether the indexed_set library soon to be reviewed also supports this feature or not, but given all the other features it has, I would be suprised if it didn't. ;)
Well, currently indexed_set does not have such an index type, although it could be probably implemented with relative ease. But I fail to see what this type of structure is useful for. From what I've read on this thread, the main reason one could want to have operator[] is that it allows the programmer to store the index of an element for later retrieval. But this can be also accomplished (and with better performance) if we store an iterator or a reference to the element instead. I guess I'm not fully understanding the use case. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo