Re: Proposal: Sorted Vector Container

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?