David Abrahams escribió:
on Sat Nov 01 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:
Not that this can't be done, at least in principle, but it breaks the current index orthogonality in (IMHO) nasty ways. What's more, the following type
multi_index_container<random_access,random_access>
couldn't provide any O(1) erase method.
How do you erase in O(1) from the middle of a random-access container?
Ouch... Yep' you're right again. I have thought about this more carefully, and an no-up-pointer random access index might be designed with the following trade-offs with respect to the current random_access: * no stable iterators * no constant iterator projection Other than that, the big-O complexities (constant push_back, etc) can be kept, I think. Do you think this would be a useful addition to B.MI? A suggestion for a name coexisting with the current random_access (which should be kept for the current up-pointer index)? Anyway, I don't think this new index would serve your purposes, since you need some of the elements to be "disconnected" from the list: there might be workarounds like considering the sequence divided into two ranges [begin,first_not_connected),[first_not_connected,end) but I don't know if this holds water.
Suppose you wrote a library that provided only deque, and not vector, as a random access container. Your premise seems analogous to one that says, "not having O(1) push_front for a random access container is a problem." I'm saying it's not a problem to lose a feature unless you need it, especially if you get something in exchange.
Understood. I was meaning that it was a problem to incorporate this feature lacking components into the whole system in a coherent way, but maybe I spoke too fast (see above). Joaquín M López Muñoz Telefónica, Investigación y Desarrollo