pa1r<InputIteratorl. InputIterator2> mismatchdnputlteratorl firstl,

Inputlteratorl lastl. InputIterator2 first2): pair<InputIteratorl. InputIterator2> mismatchdnputlteratorl firstl.

Inputlteratorl lastl. InputIterator2 first2,

BinaryPredicate binary pred):

Как и в случае с equal(), оба интервала должны иметь одинаковую длину, поэтому для второго интервала достаточно одного итератора, а его длина определяется длиной первого интервала. Если алгоритм equal() просто сообщает, равны ли два интервала, то mismatch() позволяет узнать, где именно начинаются расхождения. Передаваемая информация состоит из двух значений: различающихся элементов первого и второго интервалов. Эти два итератора упаковываются в объект pair и возвращаются как единое целое. При отсутствии расхождений алгоритм возвращает lastl в сочетании с конечным итератором второго интер-вллл. Шаблон pair представляет собой структуру из двух элементов, обозначенных имеиа.ми first и second, а его определение находится в заголовочном файле <utility>.

Как и в случае с equal(), в первой форме алгоритма элементы сравниваются оператором ==, а во второй эквивалентность определяется бинарным предикатом binary pred.

Стандартный класс С++ обладает свойствами контейнера (он содержит функции begin() и end(), возвращающие объекты типа string::iterator), поэтому его удобно использовать для создания символьных интервалов при тестировании алгоритмов сравнения STL. Однако следует помнить, что класс string поддерживает достаточно полный набор собственных операций. Прежде чем задействовать алгоритмы STL для выполнения операций, стоит внимательнее изучить класс string.

: СОб:Comparison.срр

Алгоритмы сравнения интервалов STL

#include <algorithm>

#include <functional>

#include <string>

#i nclude <vector>

#include PrintSequence.h

using namespace std:

int mainO {

Класс string содержит удобные средства для создания символьных интервалов, но обычно строковые операции лучше выполнять функциями этого класса: string si( This is a test ): string s2( This is a Test ):

cout si: si endl s2: s2 endl cout compare si & si:

equaKsl.beginO, sl.endO. si.beginO) endl cout compare si & s2:

equal (si.beginO. sl.endO. s2.beginO) endl cout lexicographical compare si & si:

lexicographical compa re(s1.beg i n(). s1.end О, si.beginO. sl.endO) endl: cout lexicographical compare si & s2:

lexicographical compare(sl.begin(). sl.endO. s2.beginO, s2.end()) endl: cout lexicographical compare s2 & si:

1 exicographical compare(s2.begin(), s2.endO,

si.beginO. sl.endO) endl; cout lexicographical compare shortened

si & full-length s2: endl; string s3(sl); while(S3.lengthO != 0) { bool result = lexicographical compare(

S3.beginO. s3.end(). s2.beginO.s2.end()); cout s3 endl s2 . result =

result endl; if(result == true) break; S3 = s3.substr(0. S3.lengthO - 1);

pair<string::iterator, string;:iterator> p = mismatch(sl.beginO, sl.endO. s2.beginO); print(p.first. Sl.endO. p.first . ); print(p.second, s2.end(). p.second , ); } /;-

Строки si и s2 различаются только прописной буквой Т в слове Test строки s2. Как и следовало ожидать, при проверке равенства si и si возвращается значение true, а si и s2 не равны из-за отличий в регистре буквы Т .

Чтобы понять результаты тестов lexicographicaLcompare(), следует помнить две вещи: во-первых, сравнение производится посимвольно, во-вторых, на нашей платформе прописные буквы предшествуют строчным. В первом тесте si сравнивается с si. Так как строки точно совпадают, ни одна из них не меньше другой по лексикографическому критерию (что проверяется алгоритмом), поэтому результат равен false. Фактически второй тест проверяет, предшествует ли si строке s2. Когда алгоритм добирается до буквы t в слове test , он обнаруживает, что строчная t в si больше прописной t в s2, так что результат снова равен false. Но если проверить, предшествует ли s2 строке si, мы получим true.

Чтобы читатель лучше понял смысл лексикографического сравнения, следующий тест в этом примере снова сравнивает si с s2 (раньше при этой проверке был получен результат false). Но в новом варианте проверки с конца строки si, предварительно скопированной в s3, последовательно отсекается по одному символу до тех пор, пока алгоритм не вернет true. Как только из s3 (копии si) удаляется буква Т , результат меняется. Так как строка s3 короче s2, в лексикографическом отношении она предшествует ей.

В последнем тесте используется алгоритм mismatch(). Чтобы сохранить возвращаемое значение, мы создаем объект pair р с типами итераторов из первого и второго интервалов (в нашем примере оба итератора относятся к типу string::iterator). При выводе результатов несовпадающий элемент в первом интервале определяется итератором р.first, а во втором - итератором р.second. В обоих случаях выводится содержимое интервала от несовпадающего элемента до конца, чтобы было понятно, на какой элемент ссылается итератор.

Удаление элементов

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

алгоритмы удаления в STL всего лишь переставляют элементы интервала так, чтобы удаленные элементы находились в конце интервала, а оставшиеся - в начале (ив том же порядке, что прежде, за исключением удаленных элементов, то есть операция является устойчивой). Алгоритм возврашает итератор для нового последнего элемента, обозначающий конец подынтервала оставшихся элементов и начало подынтервала удаленных элементов. Другими словами, если алгоритм удаления возвращает итератор new last, то интервал [first,new last) не содержит ни одного удаленного элемента, а интервал [new lastlast) состоит только из удаленных элементов.

Если вы работаете с элементами интервала при помощи других алгоритмов STL, можно просто использовать итератор new last как новый конечный итератор. С другой стороны, если вы применяете контейнер с, поддерживающий изменение размеров (то есть не массив), и хотите исключить логически удаленные элементы из контейнера, воспользуйтесь алгоритмом erase():

с.erase(remove(c.beginO. c.endO, value). c.endO):

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

Алгоритм remove() возвращает итератор new last, а erase() уничтожает все удаленные элементы из контейнера с.

К итераторам в интервале [new last,last) может применяться операция разыменования, но значения элементов не определены и не должны использоваться в программе.

Forwardlterator remove(Forwardlterator first.

Forwardlterator last, const T& value): Forwardlterator remove if(Forwardlterator first.

Forwardlterator last. Predicate pred): Outputlterator remove copy(Inputlterator first.

Inputlterator last. Outputlterator result, const T& value): Outputlterator remove copy if(Inputlterator first,

Inputlterator last, Outputlterator result, Predicate pred):

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

Версии этих алгоритмов с суффиксом if передают каждый элемент предикату pred и по полученному значению определяют, должен ли этот элемент остаться в контейнере (если ргес1() возвращает true, элемент удаляется). Версии с суффиксом сору не изменяют исходный интервал; они копируют неудаленные элементы в интервал, начинающийся с result, и возвращают конечный итератор для этого нового интервала.

Forwardlterator unique(Forwardlterator first.

Forwardlterator last): Forwardlterator unique(Forwardlterator first.

Forwardlterator last. BinaryPredicate binary pred): Outputlterator unique copy(Inputlterator first.

Inputlterator last. Outputlterator result):