Сравнение по лексикографическому критерию

bool

lex1cographical compare (Inputlteratorl beg. Inputlteratorl end.

InputIterator2 beg. InputIterator2 end)

bool

lexicograph1cal conpare (Inputlteratorl beg. Inputlteratorl end.

InputIterator2 beg. InputIterator2 end. CompFunc op)

О Обе формы проверяют, что интервал Ibeg1,end1) меньше интервала [beg2,end2) по лексикографическому критерию.

О Первая форма сравнивает, элементы оператором <.

О Вторая форма сравнивает элементы бинарным предикатом op(elem1 ,elem2). Предикат возвращает true, если eleml меньше elem2.

О Лексикографическое сравнение означает, что интервалы сравниваются по парам элементов до тех пор, пока не будет выполнено одно из следующих условий:

□ если два элементы не равны, то результат их сравнения определяет результат всего сравнения;

□ интервал, содержащий меньшее количество элементов, считается меньше другого, то есть при достижении конца первого интервала результат сравнения считается равным true (первый интервал меньше второго);

□ если количество элементов в обоих интервалах одинаково, то интервалы считаются равными, а результат сравнения равен false.

О Предикат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на с. 303.

О Предикат ор не должен изменять передаваемые аргументы.

О Сложность линейная (не более 2xmin(numberOfElements 1,numberOfElement2) сравнений или вызовов ор соответственно).

Пример лексикографической сортировки коллекций:

algo/lexicol.cpp Include algostuff.hpp using namespace std:

void printCollection (const list<int>8i 1) {

PRINTJLEMENTSO):

bool lessForCollection (const I1st<int>& 11. const list<int>& 12)

return lexicographicaljompare

(U.beginO. U.endO. Первый интервал 12.beginO. 12,end()): Второй интервал

int mainC) {

list<1nt> cl. c2. c3. c4:

Заполнение коллекций одинаковыми исходными данными

INSERT ELEMENTS(cl.l.5):

с4 = сЗ = с2 = cl:

Внесение различий cl.push backC7) c3,push backC2) c3.push backC0) c4.push backC2);

Создание коллекции коллекций vector<11st<1nt> > сс:

сс. pU5h

сс. push cc.push сс. push сс. push сс. push сс. push сс. push

back(cl) back(c2) Ьаск(сЗ) back(c4) ЬаскСсЗ) backCcD back(c4) backCc2)

Вывод всех коллекций for each (сс.beginO. cc.endO.

printCollectlon); cout endl:

Лексикографическая сортировка коллекции sort (сс.beginO. cc.endO. Интервал

lessForCollection); Критерий сортировки

Повторный вывод коллекций for each (cc.begln(). cc.endO. printCollectlon):

Вектор сс инициализируется несколькими списками. При вызове sort() коллекции сравниваются бинарным предикатом lessForCollection() (см. описание алгоритма sort() на с. 389). Алгоритм lexicographicaLconnpareO производит лексикографическое сравнение коллекций. Программа выводит следующий результат:

1 2 3 4 5 7

1 2 3 4 5

1 2 3 4 5 2 0

1 2 3 4 5 2

1 2 3 4 5 2 0

1 2 3 4 5 7 1 2 3 4 5 2 1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5 2

1 2 3 4 5 2

1 2 3 4 5 2 0

1 2 3 4 5 2 0

1 2 3 4 5 7

1 2 3 4 5 7

Модифицирующие алгоритмы

в этом разделе описаны алгоритмы, модифицирующие элементы интервалов. Существуют два способа модификации:

О непосредственная модификация во время перебора;

О модификация в процессе копирования из источника в приемник.

Некоторые модифицирующие алгоритмы поддерживают оба способа модификации элементов в интервале. В этом случае форма с модификацией при копировании снабжается суффиксом сору.

Ассоциативный контейнер не может быть приемником модифицирующего алгоритма, потому что элементы ассоциативных контейнеров являются константными. Без этого ограничения модификация привела бы к нарушению автоматической упорядоченности.

Все алгоритмы, использующие отдельный приемный интервал, возвращают позицию за последним скопированным элементом этого интервала.

Копирование элементов

Outputlterator

сору (Inputlterator sourceBeg. Inputlterator sourceEnd. Outputlterator destBeg)

BidirectionalIteratorl

copy backward (Bidirectionallteratorl sourceBeg.

Bidirectionallteratorl sourceEnd. BidirectionalIterator2 destBeg)

О Оба алгоритма копируют все элементы исходного интервала [sourceBegsourceEnd) в приемный интервал, начиная с destBeg или заканчивая destEnd соответственно.

О Алгоритмы возвращают позицию за последним скопированным элементом в приемном интервале (то есть позицию первого элемента, который не был заменен в ходе копирования).