Iterator Operations

Discussion in 'C++' started by Michael Mellor, Jan 20, 2004.

  1. 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.
    Michael Mellor, Jan 20, 2004
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,416
  2. Jesus M. Salvo Jr.
    Replies:
    2
    Views:
    4,138
    robert
    Feb 11, 2006
  3. greg
    Replies:
    6
    Views:
    454
    Dietmar Kuehl
    Jul 17, 2003
  4. Replies:
    6
    Views:
    640
    Jim Langston
    Oct 30, 2005
  5. Hizo
    Replies:
    7
    Views:
    701
    James Kanze
    Apr 3, 2011
Loading...

Share This Page