Iterator Operations

[Michael Mellor]

I have implemented the following insertion sort algorithm which is
probably pretty efficient* for vectors. However, the algorithm can be
made more efficient for containers such as list by replacing
move_end_to_begin with an insert. The problem lies in the fact the STL
requires knowledge of the container to insert before/after an iterator,
and even if an insert could be achieved without knowing about the
container there is no way of knowing the complexity of different
operations and whether they invalidate other iterators.

So the only way I can see of making this better for lists is by passing
the container or a move_end_to_begin function as a parameter. This seems
to defeat the point of a generic algorithm when it needs to know about
the container it is operating on. I am sure a better iterator design
would fix these limitations.

I would appreciate any comments.

template<typename BiIter>
void move_end_to_begin ( BiIter begin, BiIter end ) {
while ( begin != end ) {
BiIter current = end;
--end;
std::swap ( *current, *end );
}
}

// Binary insertion sort if BiIter is random-access
// Linear insertion sort if BiIter is bi-directional
template<typename BiIter>
void insertion_sort ( BiIter begin, BiIter end ) {
if ( std::distance ( begin, end ) <= 1 )
return;

BiIter middle = begin;
++middle;

while ( middle != end ) {
BiIter insert = std::upper_bound ( begin, middle, *middle );
move_end_to_begin ( insert, middle );
++middle;
}
}

Michael Mellor

* I am not interested in discussions about how it is an n^2 algorithm
and and an n*log n would be better.