First, note that the lookup times for multiset and vector were the same, which says that the penalty for tree traversals is not that large in this case (and should also not be a major factor in the sort).  This also says to me that memory contiguity may not be playing that large a role here because even if elements are scattered in the multiset versus in a narrow area of memory in a vector the penalty may not be that large (a slightly surprising results).  What's more interesting here is the story on the inserts which includes the allocation/sort phase for both containers.  Comparing the time taken for lookups in the two containers makes it unlikely that tree traversals are to blame for the slow setup time of a multiset.  Instead, it seems much more likely that the big culprit is allocation.  Either, a) the allocator is not very good for multisets or b) the overhead of all the pointers associated with a tree node is bloating the object a lot and making allocations much slower than they should be.  This is especially surprising in light of the fact that they vector may have to do reallocations and copying to retain contiguity which the multiset does not. So, I guess one moral here is to be careful about the overhead associated with each node.

 

The second comparison that we did below was for vector<int> versus vector<int *> -- where we allocated the items we put in the vector int * from a vector in order to remove the effects allocators and memory contiguity.  Unsurprisingly, sorting a vector of int * came back significantly slower because each comparison operation has to go through dereference operations slowing it down relative to vector<int>.  In general, the timing of the sort of vector<object> versus vector<object*> will come down to:

    n log n comparison operations:  Object * will always be slower because of additional derefereces as shown below

    n log n swap operations: Object * may or may not be faster here.  If the object it smaller than sizeof(pointer) Object * will have no advantage.  If the object is larger than sizeof(pointer) it will be faster to swap pointers thatn the actual object.

 

So what would an "ideal" sorted container come down to:

 

1. Size matters.  Keep the node overhead as small as possible to minimize allocation costs.

2. Given 1 try to minimize the comparison and swap costs for the individual elements.

3. Try to keep memory contiguity if you can - although it may not matter all that much.

 

So how does a sorted vector perform? 

I would give it a B on item 1 - it keeps the size down but does expensive reallocations and copies to keep more memory contiguity than it may need.

I would give it a B on item 2 as well, it may have significant swap costs for larger objects making the setup time slower than it needs to be. (The swap time will not impact the search speed, though).