Д. Стефенс - C++. Сборник рецептов

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 mismatch(In1 first1, In1 last1, In2 first2);

pair mismatch(In1 first1, In1 last1, In2 first2, BinPred);

Два возвращаемых итератора указывают на различные элементы каждой из последовательностей. Рассмотрим пример 7.4.

string s1 = "abcde";

string s2 = "abcdf";

pair iters =

mismatch(s1.begin(), s1.end(), s2.begin());

cout << "first mismatch = " << *(iters.first) << '\n'; // 'e'

cout << "second mismatch = " << *(iters.second) << '\n'; // 'f'

Вы должны убедиться, что длина второго диапазона не меньше первого. Если вторая последовательность короче первой, mismatchне сможет узнать этого и продолжит выполнение сравнения элементов за границей второй последовательности, что приведет к непредсказуемому поведению. Кроме того, если несовпадений нет, то первый итератор будет указывать на last1, который может оказаться недействительным (например, если в качестве last1передать end().

Вы, должно быть, заметили по объявлениям каждой из этих функций, что типы итераторов для каждой из этих последовательностей различны. Это означает, что две последовательности могут быть контейнерами разных типов, но при условии, что типы элементов, на которые указывают итераторы, имеют определенный для них operator<. Например, можно сравнивать stringи vector.

string s = "Coke";

vector v;

v.push.back('c');

v.push_back('o');

v.push_back('k');

v.push_back('e');

std::cout << std::lexicographical_compare(s.begin(), s.end(),

v.begin(), v.end()) << '\n';

Здесь каждый символ двух последовательностей сравнивается вне зависимости от типа контейнера, в которых они хранятся.

Стандартная библиотека C++ предоставляет несколько различных способов сравнения последовательностей. Если ни один из них вам не подходит, посмотрите на их исходный код — он является хорошим примером того, как надо писать собственные эффективные обобщенные алгоритмы.

Рецепт 7.1.

Имеется две отсортированные последовательности и их требуется объединить.

Используйте либо шаблон функции merge, либо шаблон функции inplace_merge. mergeобъединяет две последовательности и помещает результат в третью, a inplace_mergeобъединяет две последовательно расположенные последовательности. Пример 7.5 показывает, как это делается.

Пример 7.5. Объединение двух последовательностей

#include

#include

#include

#include

#include

#include

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

vector v1, v2, v3;

v1.push_back("a");

v1.push_back("c");

v1.push_back("e");

v2.push_back("b");

v2.push_back("d");

v2.push_back("f");

v3.reserve(v1.size() + v2.size() + 1);

// Используйте back_inserter от итератора, чтобы избежать необходимости

// помещать в контейнер набор объектов по умолчанию. Но это не означает,

// что не требуется использовать reserve!

merge(v1.begin(), v1.end(), v2.begin(), v2.end(),

back_inserter >(v3));

printContainer(v3);

// Теперь выполняем действия

random_shuffle(v3.begin(), v3.end());

sort(v3.begin(), v3.begin() + v3.size() / 2);

sort(v3.begin() + v3.size() / 2, v3.end());

printContainer(v3);

inplace_merge(v3.begin(), v3.begin() + 3, v3.end());

printContainer(v3);

// Однако если используется два списка, используйте list::merge.

// Как правило, ...

list lstStr1, lstStr2;

lstStr1.push_back("Frank");

lstStr1.push_back("Rizzo");

lstStr1.push_back("Bill");

lstStr1.push_back("Cheetoh");

lstStr2.push_back("Allie");

lstStr2.push_back("McBeal");

lstStr2.push_back("Slick");

lstStr2.push_back("Willie");

lstStr1.sort(); // Отсортировать, иначе объединение выдаст мусор!

lstStr2.sort();

lstStr1.merge(lstStr2); // Заметьте, что это работает только для другого

// списка того же типа

printContainer(lstStr1);

}

Вывод примера 7.5 выглядит так.

-----

a

b

с

d

e

f

-----

b

d

e

a

c

f

-----

a

b

с

d

e

f

Allie

Bill

Cheetoh

Frank

McBeal

Rizzo

Slick

Willie

mergeобъединяет две последовательности и помещает результат в третью — опционально используя функтор сравнения, указанный пользователем и определяющий, когда один элемент меньше другого, а по умолчанию используя operator<. Сложность линейна: число выполняемых mergeсравнений равно сумме длин двух последовательностей минус один. Типы элементов в обеих последовательностях должны быть сравниваемы с помощью operator<(или указанного вами функтора сравнения) и должны быть преобразуемы к типу элементов выходной последовательности при помощи конструктора копирования или присвоения; или должен быть определен оператор преобразования, определенный так, чтобы тип элементов выходной последовательности имел для обоих типов операторы присвоения и конструкторы копирования.

Объявления mergeвыглядят вот так

void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result);

void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result,