2009/8/12 Ion Gaztañaga <igaztanaga@gmail.com>:
Boost.Container
http://svn.boost.org/svn/boost/sandbox/move/libs/container/doc/html/index.ht...
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