Re: [boost] challenge: stable_vector

From: Ullrich Koethe (u.koethe_at_[hidden])
Date: 2001-07-12 09:53:04

David Abrahams wrote:
> 
> I just don't see it. Remember that erasing an element of the vector
> invalidates all following iterators. Maybe you have something in mind that
> you haven't explained?
> 

Am I solving the wrong problem? I'm trying to design a dictionary with
these properties:

* the internal representation is a sorted vector of pair<key, value>
* iterators are not invalidated by insert/erase

Even if we are talking about the same problem, you are right that my
current design is wrong. But let me try again.

Suppose the vector counts how many insert/erase operations have been
made. Each iterator stores the count where it last synchronized itself
with the vector. Then the rule is:

* when the iterator's counter equals the vectors counter, there were no
inserts/erases. Then the iterator behaves just like a normal vector
iterator (constant time behaviour).

* when the iterator's counter is different, it is out-of-date. Then the
iterator asks the dictionary were its key/value pair went as a result of
erase/insert (logarithmic time). The iterator's data are updated
accordingly, and it resumes working normally.

The iterator thus acts like a cache with a time stamp for a particular
dictionary state, and exhibits constant time behaviour as long as the
dictionary isn't modified. I'm not sure to what extend this design can
be made compatible to std::map, but at least the iterators remain valid,
which is my most important practical requirement.

To make this work, the iterator must store a reference to the underlying
container, the time stamp, the key, and an iterator for the internal
sorted vector. 

Rough sketch (handling of the end iterator is missing):

template <class Key, class Value>
class dictionary
{
    typedef vector<pair<Key, Value> > sorted_vector;
    typedef sorted_vector::iterator internal_iterator;
    
    friend class dictionary_iterator<dictionary>;
    
    unsigned long counter; // BigInt were even better
    sorted_vector data;
    
    internal_iterator internal_find(Key k) 
    {
         ... // binary search in the sorted vector
    }
    
  public:
    
    typedef Key key_type;
    typedef pair<Key, Value> value_type;
    typedef dictionary_iterator<dictionary> iterator;

    void insert(Key k, Value v)
    {
        internal_iterator lookup = internal_find(k);        
        if(lookup == data.end()) // key not found
        {
            ... // insert key/value pair
            counter++; // invalidate iterators
        }
        else
        {
            (*lookup).second = v;
            // do not increment counter - iterators remain valid
        }
    }
    
    iterator find(Key k) 
    {
        return iterator(*this, k, counter, internal_find(k));
    }
    
};

template <class Dictionary>
class dictionary_iterator
{
    Dictionary & dictionary;
    Dictionary::key_type key;
    mutable unsigned long time_stamp;
    mutable Dictionary::internal_iterator internal_iterator;
    
    // update() takes constant time if the dictionary wasn't modified
    // logarithmic time otherwise
    void update() const
    {
        if(time_stamp != dictionary.counter)
        {
            internal_iterator = dictionary.internal_find(key);
            time_stamp = dictionary.counter;
        }
    }
    
  public:
    
    typedef Dictionary::value_type value_type;
    
    dictionary_iterator(Dictionary & d, Dictionary::key_type k, 
                        unsigned long c, Dictionary::internal_iterator
i)
    : dictionary(d), key(k), time_stamp(c), internal_iterator(i)
    {}
    
    dictionary_iterator & operator++()
    {
        update();
        internal_iterator++;
        key = (*internal_iterator).first;
        return *this;
    }
    
    value_type operator*() const
    {
        update();
        return *internal_iterator;
    }
    
};

-- 
 ________________________________________________________________
|                                                                |
| Ullrich Koethe  Universität Hamburg / University of Hamburg    |
|                 FB Informatik / Dept. of Computer Science      |
|                 AB Kognitive Systeme / Cognitive Systems Group |
|                                                                |
| Phone: [phone]                Vogt-Koelln-Str. 30 |
| Fax:   [phone]                D - 22527 Hamburg   |
| Email: u.koethe_at_[hidden]               Germany             |
|        koethe_at_[hidden]                        |
| WWW:   http://kogs-www.informatik.uni-hamburg.de/~koethe/      |
|________________________________________________________________|