- How about a sequence container (like a vector) with the advantage of logarithmic time insertion/removal at any point of the sequence? The disadvantage is that random access takes logarithmic time too (instead of the usual constant time random access of a vector). Here it is: http://sourceforge.net/projects/avl-array It is implemented with a tree, but it is _not_ a map. The 'position' of elements in avl_array are always natural numbers (0, 1, 2... up to size()-1). When an element is inserted/removed, it changes automatically the position of all elements after it in the sequence (in logarithmic time!). A simple experiment realized consisted in populating a container by inserting random numbers in random positions, and then removing numbers from random positions, showing the value of the last one for checking. In this test AVL Arrays completely outperform list, vector and deque. The test code and the results are in sourceforge too. Version 1.1 includes a new experimental feature that I call "Non-Proportional Sequence View". In the normal sequence, every element occupies a position of size 1. Additionally, elements can be viewed as a sequence where the 'width' of every element can be changed (in O(log n) time), being the position of every element the sum of the widths of all previous elements in the sequence. Negative widths are forbidden, but zero widths are valid. The type used for the width is a template parameter, so any class supporting some operators can be used, not only unsigned or double. I've tried to adapt it to the boost requirements, but I'm sure there's still a lot of things to change. If you are interested, please take a look at it, and tell me your opinion. Regards, Martin Knoblauch Revuelta Universidad de Alcala