Re: [boost] [move][container] Review Request (new versions of Boost.Move and Boost.Container in sandbox and vault)

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
>
>
http://svn.boost.org/svn/boost/sandbox/move/libs/container/doc/html/index.html
>
> 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
package
> (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.
 or
 - 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.)
Tony