CODEWITHSUNDEEP
c++stlaccelerated-c++
kmad1729
kmad1729

Reputation: 1624

Why do we need swap in reverse STL implementation? Accelerated C++ (ques 8.4)

I am trying to answer the question: Why did we call swap rather than exchange the values of *first and *last in the implementation of reverse function? Here is the reverse function:

template <class BiDirectionalIterator>
void reverse(BiDirectionalIterator first, BiDirectionalIterator last)
{
    while(first < last) {
        --last;
        if(first != last) {
            swap(*first++, *last);
        }
    }
}

I am trying to clear my understanding here. I tried exchanging *first and *last directly:

template <class Bi>
void incorrect_reverse(Bi first, Bi last)
{
    while(first < last) {
        --last;
        if(first != last) {
            //here tmp and first both point to the same thing
            Bi tmp = first;
            *first = *last;
            *last = *tmp;
            first++;
        }
    }
}

I saw that this did not work. Then I tried Bi tmp = *first to get the value of first but get a compiler error. Is there not way than calling the swap function that I can do this? I am looking for way to do it in the function itself.

Upvotes: 0

Views: 69

Answers (1)

Benjamin Lindley
Benjamin Lindley

Reputation: 103741

You need to store the value *first as your temporary storage, not the iterator first.

auto tmp = *first;
*first = *last;
*last = tmp;
first++;

Otherwise you are overwriting *first without storing its previous value, and so you are essentially just copying from *last to *first (and then redundantly copying it back again), instead of swapping.

The reason you got an error when you did this:

Bi tmp = *first

Is because Bi is the type of the iterator, not the type of the value you are trying to swap. To get the correct type, you can just use auto like I did above, or you can be more explicit:

typename std::iterator_traits<Bi>::value_type tmp = *first;

Upvotes: 2

Related Questions