Разница между итератором и обратным итератором
В чем разница между следующими двумя фрагментами кода.
vector<int> a;
// initialization code
sort( a.rbegin(), a.rend() );
а также
vector<int> a;
// same initialization as above
sort(a.begin(), a.end(), comp);
где comp — логическая функция, приведенная ниже
bool comp( int i, int j)
{
return i>j;
}
Чтобы проиллюстрировать, следующий код дает Вашингтон в то время как этот код дает переменный ток для проблемы SPOJ XMAX.
Единственная разница между переменный ток а также Вашингтон используется версия sort ()
Решение
Два вызова функций делают НЕ дать тот же ответ, потому что std::sort является не стабильный алгоритм, то есть он не сохраняет идентичные элементы в их относительном расположении. Ниже приведен пример, где элементы std::pair<int, int> отсортированы по первому элементу. Сортировка и сортировка в обратном порядке с помощью функции обратного сравнения не дает идентичных последовательностей. Делать то же самое с std::stable_sort действительно дает идентичные результаты.
#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";
}
Выход на LiveWorkSpace
Другие решения
Обратные итераторы простые итерации в обратном направлении нормальных итераторов.
Таким образом, оба фрагмента будут сортировать все внутри диапазона [первый, последний] как в порядке возрастания.
Разница в том, что в первом он будет использовать < оператор для сравнения а во второй заданная вами функция.
Подробно, первая на самом деле сортирует в не возрастающем порядке, но, поскольку вы также обращаете вспять сравнение, оно снова переворачивается, что нейтрализует эффект.
ПРИМЕЧАНИЕ. Элементы, сравниваемые равными друг другу, не гарантируют сохранения своего первоначального относительного порядка.
ПОЛЕЗНЫЕ ССЫЛКИ: std::sort, std::vector::begin, std::vector::end,
std::vector::rbegin,
std::vector::rend
Как следует из названия, обратный итератор посещает коллекцию в обратном порядке. Если вы спросите STL sort() алгоритм сортировки диапазона из a.begin() в a.end(), он помещает полученные значения в … диапазон от a.begin() в a.end()в порядке, определенном этими итераторами.
Так что же произойдет, если вы попросите его отсортировать диапазон a.rbegin() в a.rend()? Это ставит результаты в … диапазоне от a.rbegin() в a.rend()в порядке, определяемом те итераторы.
rbegin дает вам итератор, который указывает на конец вашего списка и будет двигаться назад, когда вы просите его двигаться вперед. Так же, rend дает вам итератор в начале вашего списка.
sort(a.begin(), a.end(), comp);
Третий параметр здесь используется для определения собственного порядка сортировки. Если вы не укажете один из них, будет использоваться объект по умолчанию.
Они оба выполняют одно и то же. В первой версии вы изменяете порядок итераторов, чтобы получить сортировку по убыванию. Во второй версии вы меняете смысл сравнения, также получая сортировку от высокого к низкому уровню.
Итератор работает с первого до последнего, обратный итератор работает с последнего до первого. Так sort(a.begin(), a.end()) размещает элементы в диапазоне [first, last) по порядку; sort(a.rbegin(), a.rend()) размещает элементы в диапазоне [last, first) по порядку, производя порядок, противоположный первой версии.