Hi Jon, If the elements in the flat associative container are sorted, you need only to sort the elements to insert and after do a fusion of the two parts. If your container admit repeated elements, you can use the std::sort, if not, you must use an stable sort , and delete the repeated. You have several algorithms for to do a stable sort. In the library we are developing (https://github.com/fjtapia/sort_parallel ) you have a smart_merge_sort, which is a very fast stable sort and use only one half of the memory used by the data, is exception safe and use the move semantics I didn't see any implementation of the stable sort algorithms without additional memory, in any library GCC, TBB, IPP … I suppose because they are slow. If you have 100 elements and want to insert 30 elements, need to resize the vector to 130 elements, the last 30 are empty. If you have other vector with the data to insert, you can use smart_merge_sort, and use as auxiliary memory the last 15 elements of the main vector. After sort, delete the repeated elements. And with the two vectors you must do a half_merge fusion , and all is done. With this method you need only the vector for to sort the elements to insert. If you want I can write a small program doing this, using the code of the library.