Effective STL

* If you need to perform a full sort on a vector, string, deque, or array, you can use sort or stable_sort. * If you have a vector, string, deque, or array and you need to put only the top n elements in order, partial_sort is available. * If you have a vector, string, deque, or array and you need to identify the element at position n or you need to identify the top n elements without putting them in order. nth_element is at your beck and call. * If you need to separate the elements of a standard sequence container or an array into those that do and do not satisfy some criterion, you're probably looking for partition or stable_partition. * If your data is in a list, you can use partition and stable_partition directly, and you can use list-sort in place of sort and stable_sort. If you need the effects offered by partial_sort or nth_element, you'll have to approach the task indirectly, but there are a number of options, as I sketched above.

advance(i, distance<ConstIter>(i, ci)); 

It's as efficient as the iterators allow it to be. For random access iterators (such as those sported by vector,string, and deque), it's a constant-time operation. For bidirectional iterators (i.e., those for all other standard containers and for some implementations of the hashed containers (see Item 25)), it's a linear-time operation.

If you're updating an existing map element, operator[] is preferable, but if you're adding a new element, insert has the edge.

That's why it makes sense to consider using a sorted vector instead of an associative container only when you know that your data structure is used in such a way that lookups are almost never mixed with insertions and erasures.