From: corwinjoy (cjoy_at_[hidden])
Date: 2002-01-09 01:08:21
One other topic that is worth discussing while we are on this thread
is the iterator invariants for these containers. Specifically what
happens to iterators that have been returned by the container after
an insert or erase operation has been applied to the container. In
the case of std:: ordered associative container we get the following:
Given an iterator i that has previously been returned by the container
After an insert:
1. *i will remain unchanged.
2. &*i will remain unchanged. (The address of the object 'pointed
to' by the iterator will remain unchanged).
3. i will maintain it's "positional invariant". Specifically, if the
container is sorted in ascending order, all elements reachable by i
using the ++ operation will have a value greater than or equal to
*i. i.e. after an insert we will never have *i > *(++i)
Let me give a concrete example of what I mean. Suppose we start with
a list that contains the elements 1, 2, 6, 7, 8 at positions 0, 1, 2,
3, 4. We return an iterator, i, that points to the element in
position number 2 , i.e. *i == 6. Now suppose we insert the
elements '3', '4' into the list. After the insert operation users
familiar with std::ordered associative container would expect that
*i == 6 and *(++i)==7.
In fact, if we are using a vector to hold the elements (or a naive
vector of pointers to elements) and our iterators just hold a
position we will get:
*i == 3 (this is the element now at position 2 -- or even worse, if
we cached the old value in the iterator we may get *i == 6)
*++i == 4
A similar type of problem happens to the 'position' of an iterator
after an erase operation.
In the case of vec_multiset the bookkeeping that goes on behind the
scenes is primarily to make sure we maintain this 'positional
invariant'. In fact, whether you are holding objects directly or
simply holding pointers to the underlying objects I don't see how one
can maintain the position of an iterator without using bookkeeping
(or an address search to find where you are) if the sorting container
is a vector (the standard containers don't have this problem as they
are using linked nodes). Here I would be curious to understand how
the other proposed containers handle this issue. For example in the
associative indirect vector code, I don't really see how the indirect
iterator would account for this?