Boost logo

Boost :

Subject: Re: [boost] [move][container] Review Request (new versions of Boost.Move and Boost.Container in sandbox and vault)
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2009-08-24 00:26:29

2009/8/12 Ion Gaztañaga <igaztanaga_at_[hidden]>:
> Boost.Container
> Boost.Container depends on Boost.Move and Boost.Intrusive so you must
> download also the post-1.40 version of Intrusive placed in the same
> (Boost.Container uses new features from Intrusive not included in Boost
> 1.40). Just take fresh Boost 1.39 folder and overwrite it with package
> contents.

Looking at Boost.Container docs (not code), reminds me of similar
experiments I've done in the past. One thing I find interesting is that we
could make flat_map's iterators 'stable':
 - keep the 'outstanding' iterators in a list and update them when the
container changes. Of course, then the list might not be 'flat' - but
here's the trick, make the iterators contain a 'next' pointer to the next
iterator, so the iterator list doesn't live in flat memory at all, but on
the stack(s). I guess this doesn't work for the original purpose of
flat_map (ie existing in shared memory), but it makes a nice flat map if you
just want it to be contiguous, for memory performance reasons. It makes
some operations linear over the number of iterators, but that is usually a
small number.
 - add a level of indirection - the array of value_types isn't sorted, but
instead a separate array of indexes (into the value_type array) IS sorted.
 Iterators point into the 'stable' value_type array, thus being maintained.
 You also need a 'back-index' from value_type entry to sorted-index, which
gets updated whenever the orderedindex array is sorted.

So (using fixed-width font):

| 1 | 2 | 0 | 3 | ordered indexes
| foo | asd | bar | qwe | values (order they were added)
| 2 | 0 | 1 | 3 | back index (and ordinal!)
 iter to bar --+
iterator to bar points to value array containing bar. To do iterator++,
follow back_index to find bar in ordered indexes, then move forward to next
index. ie iterator++ is:
  &value_array[ ordered[iter->back_index + 1] ].
That's a bit extra work, and not always worth it, but maybe it is sometimes?
 Particularly when the value_type is large and costly to move. Note also
that the back index (+ 1) is the 'ordinal' of the value - ie 'bar' is the
2nd item by order, since back_index + 1 == 2 in this case. (Not sure how
often that is important, but there it is.)
Is stable_vector somewhat similar to that? Or what is the data structure of
stable_vector? (Sorry I haven't dug into the code yet to find out - I think
it would be nice to mention it in the docs, even if the implementation is
suppose to be hidden and separate from the requirements.)

Boost list run by bdawes at, gregod at, cpdaniel at, john at