Приложения random_shuffle ограничены последовательностями, которые предоставляют итераторы случайного доступа (string, vector и deque), массивами или собственными контейнерами, удовлетворяющими этому требованию. Перемешать случайным образом ассоциативный контейнер невозможно, так как его содержимое всегда хранится в упорядоченном виде. На самом деле для ассоциативных контейнеров не всегда можно использовать алгоритм, изменяющий его диапазон (и который часто называется видоизменяющим (mutating) алгоритмом).
7.4. Сравнение диапазонов
Имеется два диапазона и требуется сравнить их на равенство или определить, какой из них меньше, чем другой, основываясь на каком-либо порядке сортировки элементов.
В зависимости от типа выполняемого сравнения используйте один из стандартных алгоритмов — equal, lexicographical_compare или mismatch, определенных в <algorithm>. Пример 7.4 показывает некоторые из них в действии.
Пример 7.4. Различные типы сравнения
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include "utils.h"
using namespace std;
using namespace utils;
int main() {
vector<string> vec1, vec2;
vec1.push_back("Charles");
vec1.push_back("in");
vec1.push_back("Charge");
vec2.push_back("Charles");
vec2.push_back("in");
vec2.push_back("charge"); // Обратите внимание на строчную "с"
if (equal(vec1.begin(), vec1.end(), vec2.begin())) {
cout << "Два диапазона равны!" << endl;
} else {
cout << "Два диапазона HE равны!" << endl;
}
string s1 = "abcde";
string s2 = "abcdf";
string s3 = "abc";
cout << boolalpha // Отображает логические значения как "true" или "false"
<< lexicographical_compare(s1.begin(), s1.end(),
s1.begin(), s1.end()) << endl;
cout << lexicographical_compare(s1.begin(), s1.end(),
s2.begin(), s2.end()) << endl;
cout << lexicographical_compare(s2.begin(), s2.end(),
s1.begin(), s1.end()) << endl;
cout << lexicographical_compare(s1.begin(), s1.end(),
s3.begin(), s3.end()) << endl;
cout << lexicographical_compare(s3.begin(), s3.end(),
s1.begin(), s1.end()) << endl;
pair<string::iterator, string::iterator> iters =
mismatch(s1.begin(), s1.end(), s2.begin());
cout << "first mismatch = " << *(iters.first) << endl;
cout << "second mismatch = " << *(iters.second) << endl;
}
Вывод примера 7.4 выглядит так.
Два диапазона НЕ равны!
false
true
false
false
true
first mismatch = e
second mismatch = f
Для сравнения двух последовательностей на равенство используйте equal. Он принимает три или четыре аргумента, в зависимости от используемой версии. Вот как объявлен equal.
bool equal(In1 first1, In1 last1, In2 first2);
bool equal(In1 first1, In1 last1, In2 first2, BinPred pred);
equal с помощью operator== сравнивает каждый элемент между first1 и last1 с элементами, начиная с first2. Если указать pred, то equal для проверки будет использовать его. Перед вызовом equal убедитесь, что каждая последовательность имеет одинаковую длину. Он предполагает, что второй диапазон не меньше первого, и если это не так, то его поведение не определено.
Если требуется узнать, где и как последовательности отличаются, используйте lexicographical_compare или mismatch. lexicographical_compare сравнивает две последовательности и возвращает истину, если первая лексикографически меньше второй, что означает, что каждая пара элементов в двух последовательностях сравнивается с помощью оператора <. Объявление lexicographical_compare выглядит вот так.
bool lexicographical_compare(In1 first1, In1 last1,
In2 first2, In2 last2);
bool lexicographical_compare(In1 first1, In1 last1,
In2 first2, In2 last2, Compare comp);
Если operator< возвращает истину или первая последовательность заканчивается раньше второй, то возвращается истина. В противном случае возвращается ложь. Рассмотрим последовательность символов из примера 7.4.
string s1 = "abcde";
string s2 = "abcdf";
string s3 = "abc";
lexicographical_compare(s1.begin(), s1.end(), // abcde < abcde
s1.begin(), s1.end()); // = false
lexicographical_compare(s1.begin(), s1.end(), // abcde < abcdf
s2.begin(s2.end()); // = true
lexicographical_compare(s2.begin(), s2.end(), // abcdf < abcde
s1.begin(), s1.end()); // = false
lexicographical_compare(s1.begin(), s1.end(), // abcde < abc
s3.begin(s3.end()); // = false
lexicographical_compare(s3.begin(), s3.end(), // abc < abcde
s1.begin(), s1.end()); // = true
Сложность lexicographical_compare линейна и выполняет число сравнений, равное длине меньшей из двух последовательностей, или до тех пор, пока один из элементов в одной из последовательностей не окажется меньше соответствующего элемента другой. Сравнения реализованы полностью на основе operator<, так что если iter1 и iter2 — это итераторы двух последовательностей, то сравнение останавливается тогда, когда *iter1 < *iter2 или *iter2 < *iter1.
mismatch говорит, где две последовательности различаются. Однако его объявление несколько отличается от equal и lexicographical_compare, так как он возвращает не bool, a pair<> итераторов. Вот оно.
pair<In1, In2> mismatch(In1 first1, In1 last1, In2 first2);
pair<In1, In2> mismatch(In1 first1, In1 last1, In2 first2, BinPred);
Два возвращаемых итератора указывают на различные элементы каждой из последовательностей. Рассмотрим пример 7.4.
string s1 = "abcde";
string s2 = "abcdf";
pair<string::iterator, string::iterator> iters =
mismatch(s1.begin(), s1.end(), s2.begin());
cout << "first mismatch = " << *(iters.first) << '\n'; // 'e'