На этом шаге мы рассмотрим использование алгоритмов сравнения по лексикографическому критерию.

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

  bool
  lexicographical_compare (InputIterator1 beg, InputIterator1 end, 
                           InputIterator2 beg, InputIterator2 end)
  bool
  lexicographical_compare (InputIterator1 beg, InputIterator1 end,
                           InputIterator2 beg, InputIterator2 end,
                           CompFunc op)

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

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

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

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

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

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

Сложность линейная (не более 2*min(numberOfElements1,numberOfElements2) сравнений или вызовов ор соответственно).

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

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

#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;
}

void printCollection (const list<int>& l)
{
    PRINT_ELEMENTS(l);
}

bool lessForCollection (const list<int>& l1, const list<int>& l2)
{
    return lexicographical_compare
                (l1.begin(), l1.end(),   // Первый интервал
                 l2.begin(), l2.end());  // Второй интервал
}


int main()
{
  list<int> c1, c2, c3, c4;

  // Заполнение коллекций одинаковыми исходными данными
  INSERT_ELEMENTS(c1,1,5);
  c4 = c3 = c2 = c1;

  // Внесение различий
  c1.push_back(7);
  c3.push_back(2);
  c3.push_back(0);
  c4.push_back(2);

  // Создание "коллекции коллекций"
  vector<list<int> > cc;

  cc.push_back(c1);
  cc.push_back(c2);
  cc.push_back(c3);
  cc.push_back(c4);
  cc.push_back(c3);
  cc.push_back(c1);
  cc.push_back(c4);
  cc.push_back(c2);

  // Вывод всех коллекций
  cout << ToRus("Исходные коллекции:\n");
  for_each (cc.begin(), cc.end(),
            printCollection);
  cout << endl;

  // Лексикографическая сортировка коллекции
  sort (cc.begin(), cc.end(),    // Интервал
        lessForCollection);      // Критерий сортировки

  cout << ToRus("Вывод коллекций после сортировки:\n");
  // Повторный вывод коллекций
  for_each (cc.begin(), cc.end(),
            printCollection);


  getch();
  return 0;
}

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

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

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

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

Со следующего шага мы начнем знакомиться с модифицирующими алгоритмами.

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