C++. Сборник рецептов - [101]

. В большинстве случаев для этого подойдет целое число. Например, вот мой псевдогенератор случайных чисел.

struct RanNumGenFtor {
 size_t operator()(size_t n) const {
  return(rand() % n);
 }
} rnd;

random_shuffle(v.begin(), vend(), rnd);

Приложения random_shuffle ограничены последовательностями, которые предоставляют итераторы случайного доступа (string, vector и deque), массивами или собственными контейнерами, удовлетворяющими этому требованию. Перемешать случайным образом ассоциативный контейнер невозможно, так как его содержимое всегда хранится в упорядоченном виде. На самом деле для ассоциативных контейнеров не всегда можно использовать алгоритм, изменяющий его диапазон (и который часто называется видоизменяющим (mutating) алгоритмом).

7.4. Сравнение диапазонов

Проблема

Имеется два диапазона и требуется сравнить их на равенство или определить, какой из них меньше, чем другой, основываясь на каком-либо порядке сортировки элементов.

Решение

В зависимости от типа выполняемого сравнения используйте один из стандартных алгоритмов — equal, lexicographical_compare или mismatch, определенных в . Пример 7.4 показывает некоторые из них в действии.

Пример 7.4. Различные типы сравнения

#include
#include
#include
#include
#include "utils.h"

using namespace std;
using namespace utils;

int main() {
 vector 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 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 — это итераторы двух последовательностей, то сравнение останавливается тогда, когда