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

Пример использования алгоритмов lower bound() и upper bound():

algo/eqrange.cpp finclude "algostuff-hpp" using namespace std;

int mainO {

list<int> coll;

INSERT ELEMENTS(Coll.l.9): INSERT JLEMENTS(col 1.1.9); coll.sort (); PRINTJLEMENTSCcoll);

Вывод первой и последней позиций, в которых может быть

вставлен элемент со значением 5

pair<list<int>::iterator.list<int>::iterator> range;

range = equal range (coll.beginO, coll.endO.

cout « "5 could get position "

« d1stance(coll .beginO.range.first) + 1 « " up to

« distance(coll.beginO,range.second) + 1 « " without breaking the sorting" « endl;

Программа выводит следующий результат: 112233445566778899

5 could get positions 9 up to И without breaking the sorting

Слияние интервалов

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

Суммирование двух упорядоченных множеств элементов

Outputlterator

merge (Inputlterator sourcelBeg. Inputlterator sourcelEnd. Inputlterator source2Beg. Inputlterator source2End, Outputlterator destBeg)

Outputlterator

merge (Inputlterator sourcelBeg, Inputlterator sourcelEnd.

Inputlterator source2Beg, Inputlterator source2End.

Outputlterator destBeg, BinaryPredicate op)

О Обе формы комбинируют элементы упорядоченных исходных интервалов [source1Beg,source1End) и [source2Beg,source2End) таким образом, что приемный интервал [destBeg,...) содержит все элементы как первого, так и второго интервалов. Например, рассмотрим два интервала:

1 2 2 4 6 7 7 9 22236689

В результате вызова алгоритма merge() для этих интервалов будет получен следующий интервал:

1222223466677899

О В приемном интервале элементы следуют в порядке сортировки.

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

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op{elem1,elem2).

О Алгоритмы не изменяют состояние исходных интервалов,

О Согласно стандарту, оба исходных интервала должны быть упорядочены перед вызовом. Впрочем, в большинстве реализаций алгоритм merge() также комбинирует неупорядоченные исходные интервалы в неупорядоченный приемный интервал. Но чтобы сохранить переносимость программы, вызов merge() следует заменить двукратным вызовом сору().

О Перед вызовом необходимо убедиться в том, что приемный интервал имеет достаточный размер, или использовать итераторы вставки,

О Приемный интервал не должен перекрываться с исходными интервалами,

О Для списков определена аналогичная функция merge(), комбинирующая элементы двух списков (см. с. 252).

О Чтобы элементы, присутствующие в обоих исходных интервалах, включались в приемный интервал только один раз, используйте алгоритм setunionQ (см, с, 407).

О Чтобы в приемный интервал включались только элементы, присутствующие в обоих исходных интервалах, используйте алгоритм setJntersection() (см. с. 408).

О Сложность линейная (не более numberOfElements1+numberOfElements2-\ сравнений).

Пример использования алгоритма merge():

algo/mergel.cpp #include "algostuff.hpp" using namespace std:

int mainO

list<int> colli: set<int> C0112;

Запопнение обеих коллекций упорядоченными элементами INSERTJLEMENTS(coll 1.1.6): INSERT ELEMENTS(coll2.3.8):

PRINTJLEMENTS (col 11. "col 11; "); PRlNTJLEMENTS(coll2."coll2: "):

Вывод результата слияния

cout « "merged: ";

merge (colU.beginO. colli.endO,

C0112.beginO. coll2.end(),

ostream iterator<int>(cout," ")): cout « endl;

Результат выполнения программы выглядит так:

colli: 12 3 4 5 6 С0112: 3 4 5 6 7 8 merged: 123344556678

Объединение двух упорядоченных множеств элементов

Outputlterator

set union (Inputlterator sourcelBeg. Inputlterator sourcelEnd, Inputlterator source2Beg. Inputlterator source2End, Outputlterator destBeg)

set union (Inputlterator sourcelBeg. Inputlterator sourcelEnd.

Inputlterator source2Beg. Inputlterator source2End, Outputlterator destBeg. BinaryPredicate op)

О Обе формы комбинируют элементы упорядоченных исходных интервалов source 1Beg,source1 End) и [source2Begource2End) таким образом, что приемный интервал [destBeg,...) содержит все элементы, присутствующие в первом интервале, во втором интервале или в обоих интервалах сразу. Например, рассмотрим два интервала:

1 2 2 4 6 7 7 9 22236689

В результате вызова алгоритма set union() для этих интервалов будет получен следующий интервал:

122234667789

О В приемном интервале элементы следуют в порядке сортировки.