Difference between Iterator and reverse iterator

Question

what is difference between the following two code snippets.

vector<int> a;
// initialization code
sort( a.rbegin(), a.rend() );

and

vector<int> a;
// same initialization as above
sort(a.begin(), a.end(), comp);

where comp is a boolean function given below

bool comp( int i, int j)
{
    return i>j;
}

To illustrate, the following code gives WA while this code gives AC for SPOJ problem XMAX. The only difference between AC and WA is the version of sort() used.

Answer 1

The two function calls do NOT give the same answer because std::sort is not a stable algorithm, i.e. it does not keep identical elements in their relative ordenings. Below an example where elements of std::pair<int, int> are sorted on their first element. Sorting and sorting in reverse order with the reversed comparison function does not yield identical sequences. Doing the same with std::stable_sort does yield identical results.

#include <algorithm>
#include <iostream>
#include <ios>
#include <vector>

int main()
{
    typedef std::pair<int, int> Element;
    std::vector<Element> v;

    v.push_back( Element(1,1) );
    v.push_back( Element(-1,1) );
    v.push_back( Element(1,2) );
    v.push_back( Element(-1,2) );
    v.push_back( Element(1,3) );
    v.push_back( Element(-1,3) );
    v.push_back( Element(1,4) );
    v.push_back( Element(-1,4) );
    v.push_back( Element(1,5) );
    v.push_back( Element(-1,5) );
    v.push_back( Element(1,6) );
    v.push_back( Element(-1,6) );
    v.push_back( Element(1,16) );
    v.push_back( Element(-1,16) );
    v.push_back( Element(1,22) );
    v.push_back( Element(-1,22) );
    v.push_back( Element(1,33) );
    v.push_back( Element(-1,33) );
    v.push_back( Element(1,44) );
    v.push_back( Element(-1,44) );
    v.push_back( Element(1,55) );
    v.push_back( Element(-1,55) );
    v.push_back( Element(1,66) );
    v.push_back( Element(-1,66) );

    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << "(" << it->first << "," << it->second << ")" << " ";
    }
    std::cout << "\n";

    auto w1 = v;
    std::sort(w1.begin(), w1.end(), [](Element const& e1, Element const& e2){ 
       return e1.first < e2. first;
    });
    auto w2 = v;
    std::sort(w2.rbegin(), w2.rend(), [](Element const& e1, Element const& e2) {
       return e1.first > e2.first;
    });
    std::cout << std::boolalpha << std::equal(w1.begin(), w1.end(), w2.begin()) << "\n";

    auto w3 = v;
    std::stable_sort(w3.begin(), w3.end(), [](Element const& e1, Element const& e2){ 
       return e1.first < e2. first;
    });
    auto w4 = v;
    std::stable_sort(w4.rbegin(), w4.rend(), [](Element const& e1, Element const& e2) {
       return e1.first > e2.first;
    });
    std::cout << std::boolalpha << std::equal(w3.begin(), w3.end(), w4.begin()) << "\n";

}

Output on LiveWorkSpace

Answer 2

Reverse iterators simple iterate in the reverse direction of normal iterators.

So, both snippets will sort everything inside the range [first, last] both in ascending order. The difference is in the first it will use the < operator for comparison and in the second your given function.

In detail the first actually is sorting in non-ascending order but since you also reverse tho comparison it gets reversed again, which neutralizes the effect.

NOTE: Elements that would compare equal to each other are not guaranteed to keep their original relative order.

USEFUL REFERENCES: std::sort, std::vector::begin, std::vector::end, std::vector::rbegin, std::vector::rend

Answer 3

As the name suggests, a reverse iterator visits a collection in reverse order. If you ask the STL sort() algorithm to sort the range from a.begin() to a.end(), it places the resulting values in... the range from a.begin() to a.end(), in the order defined by those iterators.

So what happens if you ask it to sort the range from a.rbegin() to a.rend()? It puts the results in... the range from a.rbegin() to a.rend(), in the order defined by those iterators.

Answer 4

An iterator runs from first to last, a reverse iterator runs from last to first. So sort(a.begin(), a.end()) puts the elements in the range [first, last) in order; sort(a.rbegin(), a.rend()) puts the elements in the range [last, first) in order, producing the opposite order from the first version.

Answer 5

rbegin gives you an iterator that points to the end of your list and will move backward as you ask for it to move forward. Similarly, rend gives you an iterator to the beginning of your list.

sort(a.begin(), a.end(), comp);

The third parameter here is used to define your own sort order. If you don't specify one then the default of that object will be used.

Answer 6

They both accomplish the same thing. In the first version, you reverse the order of the iterators to get a high-to-low sort. In the second version you reverse the sense of the comparison, also getting a high-to-low sort.