Шаг 301.
Библиотека STL.
Алгоритмы STL. Перестановочные алгоритмы. Перемещение элементов в начало

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

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

  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() и 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(), сохраняет относительный порядок следования четных и нечетных элементов.

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




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