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

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

  BidirectionalIterator
  partition (BidirectionalIterator beg, BidirectionalIterator end, 
             UnaryPredicate op)

  BidirectionalIterator
  stable_partition (BidirectionalIterator beg, BidirectionalIterator end, 
                    UnaryPredicate op)

Оба алгоритма перемещают в начало интервала [beg,end) все элементы, для которых унарный предикат op(elem) возвращает true.

Оба алгоритма возвращают первую позицию, для которой op() возвращает false.

Отличие partition() от stable_partition() заключается в том, что stable_partition() сохраняет относительный порядок следования элементов (как соответствующих, так и не соответствующих критерию).

Алгоритм может использоваться для разбиения элементов на две группы в соответствии с критерием сортировки. Аналогичной возможностью обладает алгоритм nth_element(). Отличия этих алгоритмов от nth_element() описаны на 261 шаге.

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

Сложность:

partition() - линейная (numberOfElements вызовов ор() и не более numberOfElements/2 обменов);
stable_partition() - линейная при наличии дополнительной памяти (numberOfElements вызовов op() и обменов), n*log(n) в противном случае (numberOfElements*log(numberOfElements) вызовов op()).

Следующая программа демонстрирует использование алгоритмов partition() и stable_partition(), а также различия между ними:

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

#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;
  vector<int> coll2;

  INSERT_ELEMENTS(coll1,1,9);
  INSERT_ELEMENTS(coll2,1,9);
  PRINT_ELEMENTS(coll1,"1-я коллекция:\n");
  PRINT_ELEMENTS(coll2,"2-я коллекция:\n");
  cout << endl;

  // Перемещение всех нечетных элементов в начало
  vector<int>::iterator pos1, pos2;
  pos1 = partition(coll1.begin(), coll1.end(),              // Интервал
                   not1(bind2nd(modulus<int>(),2)));        // Критерий
  pos2 = stable_partition(coll2.begin(), coll2.end(),       // Интервал
                          not1(bind2nd(modulus<int>(),2))); // Критерий

  // Вывод коллекций и первого нечетного элемента
  PRINT_ELEMENTS(coll1,"1-я коллекция:\n");
  cout << ToRus("Первый нечетный элемент: ") << *pos1 << endl;
  PRINT_ELEMENTS(coll2,"2-я коллекция:\n");
  cout << ToRus("Первый нечетный элемент: ") << *pos2 << endl;


  getch();
  return 0;
}

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

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

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

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

Как видно из приведенного примера, stable_partition(), в отличие от partition(), сохраняет относительный порядок следования четных и нечетных элементов.

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

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