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