На этом шаге мы рассмотрим поиск первого несовпадения.

Для организации такого поиска можно использовать следующие алгоритмы:

  pair<InputIterator1, InputIterator2> 
  mismatch (InputIterator1 beg, InputIterator1 end, 
            InputIterator2 cmpBeg)
  pair<InputIterator1, InputIterator2> 
  mismatch (InputIterator1 beg, InputIterator1 end, 
            InputIterator2 cmpBeg,
            BinaryPredicate op)

Первая форма возвращает [beg,end) и [cmpBeg,...) первые два элемента интервалов, имеющие разные значения.

Вторая форма возвращает [beg,end) и [cmpBeg,...) первые два элемента интервалов, для которых бинарный предикат op(elem,cmpElem) возвращает false.

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

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

Перед вызовом необходимо убедиться в том, что интервал, начинающийся с cmpBeg, содержит достаточное количество элементов.

Для проверки равенства интервалов следует использовать алгоритм equal().

Сложность линейная (не более numberOfElements сравнений или вызовов ор соответственно).

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

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{
  vector<int> coll1;
  list<int> coll2;

  INSERT_ELEMENTS(coll1,1,6);
  for (int i=1; i<=16; i*=2) {
      coll2.push_back(i);
  }
  coll2.push_back(3);

  PRINT_ELEMENTS(coll1,"Вектор:\n");
  PRINT_ELEMENTS(coll2,"Список:\n");

  // Поиск первого расхождения
  pair<vector<int>::iterator,list<int>::iterator> values;
  values = mismatch (coll1.begin(), coll1.end(),  // Первый интервал
                     coll2.begin());              // Второй интервал
  if (values.first == coll1.end()) {
        cout << ToRus("Нет расхождений.") << endl;
  }
  else {
    cout << ToRus("Первое расхождение: ")
         << *values.first  << ToRus(" и ")
         << *values.second << endl;
    }

  // Поиск первой позиции, в которой элемент coll
  //   не меньше соответствующего элемента coll2
  values = mismatch (coll1.begin(), coll1.end(),  // Первый интервал
                     coll2.begin(),               // Второй интервал
                     less_equal<int>());          // Критерий
  if (values.first == coll1.end()) {
      cout << ToRus("Всегда меньше или равно.") << endl;
    }
    else {
        cout << ToRus("Элемент вектора больше соответствующего\n")
             << ToRus("элемента списка: ")
             << *values.first << ToRus(" и ")
             << *values.second << endl;
    }


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

Первый вызов mismatch() ищет первую позицию, в которой элементы двух интервалов имеют разные значения. Если такая позиция будет найдена, значения элементов направляются в стандартный выходной поток данных. Второй вызов ищет первую позицию, в которой элемент первой коллекции больше элемента второй коллекции, и возвращает их значения. Результат выполнения программы выглядит так:

Рис.1. Результат работы приложения

На следующем шаге мы рассмотрим сравнение по лексикографическому критерию.

Предыдущий шаг Содержание Следующий шаг