Difference between iterator and reverse iterator

Question

what's the 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 the boolean function below

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

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

Answer 1

Two function calls DO NOT give the same answer, because std::sort not a stable algorithm , i.e. he does not preserve the same elements in his relative orders. Below is an example where the elements std::pair<int, int> are sorted by their first element. Sorting and sorting in the reverse order using the inverse comparison function does not produce identical sequences. The same with std::stable_sort gives the same 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 to LiveWorkSpace

Answer 2

Reverse iterators are just iterations in the reverse direction of normal iterators.

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

In detail, the first one actually sorts in non-increasing order, but since you also cancel the comparison, it reverses again, which neutralizes the effect.

NOTE. Elements that will compare with each other do not guarantee the preservation of their original relative order.

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

Answer 3

As the name implies, the reverse iterator visits the collection in the reverse order. If you ask the STL algorithm sort() sort the range from a.begin() to a.end() , it will put the resulting values ​​in ... the range from a.begin() to a.end() in the order defined by these iterators .

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

Answer 4

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

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

The third parameter here is used to determine your own sort order. If you do not specify one, then the default value of this object will be used.

Answer 5

They both do the same thing. In the first version, you reverse the order of iterators to get the maximum sorting. In the second version, you change the meaning of the comparison, and also get a high-level category.

Answer 6

The iterator runs from the first to the last, the reverse iterator runs from the last to the first. Thus, sort(a.begin(), a.end()) arranges the elements in the range [first, last]; sort(a.rbegin(), a.rend()) puts the elements in the range [last, first) in order, creating the opposite order from the first version.