cout 5 could get position

distanceCcoll.beginO,posl) + 1 up to

distanceCcoll.beginO,pos2) + 1

without breaking the sorting endl:

Вставка 3 в первой возможной позиции без нарушения упорядоченности coll .insert (lower bound(coll .beginO.coll .endO.

Вставка 7 в первой возможной позиции без нарушения упорядоченности coll.insert (upper bound(coll.beginC).coll.endO.

PRiNTJLEMENTSCcoll);

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

5 could get position 9 up to 11 without breaking the sorting 1122334455667778899

Поиск первой и последней возможных позиций

pai r<Forwa rdIterator.ForwardIterator>

equal range CForwardlterator beg. Forwardlterator end. const T& value) palr<ForwardIterator.ForwardIterator>

equal range (Forwardlterator beg. Forwardlterator end. const T& value. BinaryPredicate op)

О Обе формы возвращают интервал значений, равных value. Интервал определяет nepBjrro и последнюю поэиции, в пределах которых элемент со значением value вставляется без нарушения упорядоченности интервала [beg,end).

О Алгоритм эквивалентен вызову

make pair(lower bound(...).upperJound(...))

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

О Перед вызовом интервал должен быть отсортирован по соответствующему критерию сортировки,

О В ассоциативных контейнерах (множество, мультимножество, отображение и мультиотображение) определена эквивалентная функция, которая работает более эффективно (см. с, 240).

О Сложность логарифмическая для итераторов произвольного доступа, линейная в остальных случаях (не более 2x\og(numberOfElements)+\ сравнений.

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

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

algo/eqrange.cpp #include 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<l1st<1nt>::iterator.list<lnt>::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 11 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: