C++. Сборник рецептов

7.0. Введение

Эта глава рассказывает, как работать со стандартными алгоритмами и как использовать их для стандартных контейнеров. Эти алгоритмы первоначально являлись частью того, что часто называется Standard Template Library (STL — стандартная библиотека шаблонов) и представляет собой набор алгоритмов, итераторов и контейнеров, которые теперь вошли в стандартную библиотеку (глава 6 содержит рецепты по работе со стандартными контейнерами). Я их буду называть просто стандартными алгоритмами, итераторами и контейнерами, но не забывайте, что это то же самое, что другие авторы называют частью STL. Одним из базовых элементов стандартной библиотеки являются итераторы, так что первый рецепт описывает, что они собой представляют и как их использовать. После этого идет несколько рецептов, которые объясняют, как использовать и расширять стандартные алгоритмы. Наконец, если вы не нашли ничего подходящего в стандартной библиотеке, то рецепт 7.10 расскажет, как написать собственный алгоритм.

Представленные здесь рецепты в основном предназначены для работы со стандартными контейнерами, и тому есть две причины. Во-первых, стандартные контейнеры очень распространены, и лучше изучить стандарт, чем изобретать колесо. Во-вторых, реализация алгоритмов из стандартной библиотеки предоставляет хороший пример для подражания в смысле взаимодействия и производительности. Если вы посмотрите, как профессионалы выполнили код стандартной библиотеки, вы, скорее всего, узнаете много нового и полезного для себя.

Все стандартные алгоритмы используют итераторы. Даже если вы знакомы с концепцией итераторов, которые рассматриваются в первом рецепте, посмотрите на табл. 7.1, которая содержит перечень соглашений, используемых в остальных рецептах главы при демонстрации объявлений функций стандартных алгоритмов.

Табл. 7.1. Сокращения категорий итераторов

Стандартные алгоритмы также используют функциональные объекты, или функторы. Функциональный объект — это класс, который переопределяет

operator()

bool

Табл. 7.2. Типы функторов

В большинстве случаев там, где требуется аргумент в виде функтора, может использоваться указатель на функцию. При использовании термина «функтор» я также подразумеваю указатель на функцию, если не указано иного.

7.1. Перебор элементов контейнера

Имеется диапазон итераторов — скорее всего, из стандартного контейнера — и стандартные алгоритмы не удовлетворяют вашим требованиям, так что вам требуется выполнить итерации самостоятельно.

Для доступа к элементам контейнера и перехода от одного элемента к другому используйте

iterator

const_iterator

Пример 7.1. Использование итераторов с контейнерами

#include 

#include 

#include 

#include 

using namespace std;

static const int ARRAY_SIZE = 5;

template

FwdIter fixOutliersUBound(FwdIter p1,

 FwdIter p2, const T& oldVal, const T& newVal) {

 for ( ; p1 != p2; ++p1) {

  if (greater(*p1, oldVal)) {

  *p1 = newVal;

  }

 }

}

int main() {

 list lstStr;

 lstStr.push_back("Please");

 lstStr.push_back("leave");

 lstStr.push_back("a");

 lstStr.push_back("message");

 // Создать итератор для последовательного перебора элементов списка

 for (list::iterator p = lstStr.begin();

  p != lstStr.end(); ++p) {

  cout << *p << endl;

 }

 // Или можно использовать reverse_iterator для перебора от конца

 // к началу, rbegin возвращает reverse_iterator, указывающий

 // на последний элемент, a rend возвращает reverse_iterator, указывающий

 // на один-перед-первым.

 for (list::reverse_iterator p = lstStr.rbegin();

  p != lstStr.rend(); ++p) {

  cout << *p << endl;

 }

 // Перебор диапазона элементов

 string arrStr[ARRAY_SIZE] = {"My", "cup", "cup", "runneth", "over"};

 for (string* p = &arrStr[0];

  p != &arrStr[ARRAY_SIZE]; ++p) {

  cout << *p << endl;

 }

 // Использование стандартных алгоритмов со стандартной последовательностью

 list lstStrDest;

 unique_copy(&arrStr[0], &arrStr[ARRAY_SIZE],

  back_inserter(lstStrDest));

}

Итератор — это тип, который используется для ссылки на единственный объект в контейнере. Стандартные контейнеры используют итераторы как основной механизм для доступа к содержащимся в них элементам. Итератор ведет себя как указатель; для доступа к объекту, на который указывает итератор, вы его разыменовываете (с помощью операторов

*

->

Итератор объявляется с помощью типа, элементы которого с его помощью будут перебираться. Например, в примере 7.1 используется

list

list::iterator p = lstStr.begin();

Если вы не работали со стандартными контейнерами, то часть этого объявления

::iterator

list typedef

list

set

list::iterator p1;

set::iterator p2;

Возвращаясь обратно к нашему примеру, итератор о инициализируется первым элементом последовательности, который возвращается методом

begin

operator++

p++

p++

p

Как только будет достигнут элемент

end

end

end

for

for (list::iterator p = lstStr.begin();

 p != lstStr.end(); ++p) {

 cout << *p << endl;

}

Как только

p

end

p

begin == end

true

empty

begin

end

size == 0

Это простое объяснение функциональности итераторов, но это не все. Во-первых, как только что было сказано, итератор работает как

rvalue

lvalue

for (list::iterator p = lstStr.begin();

 p != lstStr.end(); ++p) {

 *p = "mustard";

}

Так как

*p

string

string::operator=(const char*)

lstStr

const

iterator

const_iterator

rvalue

const

template

void printElements(const T& cont) {

 for(T::const_iterator p = cont.begin();

  p ! = cont.end(); ++p) {

  cout << *p << endl;

 }

}

В этой ситуации следует использовать именно

const

const_iterator

*p

Время от времени вам также может потребоваться перебирать элементы контейнера в обратном порядке. Это можно сделать с помощью обычного

iterator

reverse_iterator

reverse_iterator

iterator

iterator

begin

end

rbegin

rend

reverse_iterator

reverse_iterator

reverse_iterator

begin

rbegin

reverse_iterator

operator++

rend

reverse_iterator

for (list::reverse_iterator p = lstStr.rbegin();

 p != lstStr.rend(); ++p) {

 cout << *p << endl;

}

Но может возникнуть ситуация, когда использовать

reverse_iterator

iterator

for (list::iterator p = --lstStr.end();

 p != --lstStr.begin(); --p) {

 cout << *p << endl;

}

Наконец, если вы знаете, на сколько элементов вперед или назад следует выполнить перебор, используйте вычисление значения, на которое следует перевести итератор. Например, чтобы перейти в середину списка, сделайте вот так.

size_t i = lstStr.size();

list::iterator p = begin();

p += i/2; // Переход к середине последовательности

Но помните: в зависимости от типа используемого контейнера эта операция может иметь как постоянную, так и линейную сложность. При использовании контейнеров, которые хранят элементы последовательно, таких как

vector

deque

iterator

list

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

operator[]

iterator

iterator

С итератором можно делает еще много чего, но не с любым

iterator

iterator

Итераторы, предоставляемые различными типами контейнеров, не обязательно все умеют делать одно и то же. Например,

vector::iterator

operator+=

list::iterator

Категории итераторов — это, по сути, интерфейс (не технически; для реализации категорий итераторов абстрактные базовые классы не используются). Имеется пять категорий, и каждая предлагает увеличение возможностей. Вот как они выглядят — от наименее до наиболее функциональной.

Input iterator (Итератор ввода)

Итератор ввода поддерживает переход вперед с помощью

p++

++p

*p

rvalue

iterator

Output iterator (Итератор вывода)

Итератор вывода поддерживает переход вперед с помощью

p++

++p

*p

rvalue

lvalue,

Forward iterator (Однонаправленный итератор)

Однонаправленный итератор объединяет функциональность итераторов ввода и вывода: он поддерживает

++p

p++

*p

rvalue

lvalue

Bidirectional iterator (Двунаправленный итератор)

Как следует из его названия, двунаправленный

iterator

iterator

--p

p--

Random-access iterator (Итератор произвольного доступа)

Итератор произвольного доступа делает все, что делает двунаправленный

iterator

p

p[n]

+

+=

-

-=

<

>

<=

>=

p1

p2

Или можно представить все в виде диаграммы Венна. Она представлена на рис. 7.1.

Рис. 7.1. Категории итераторов

Большая часть стандартных контейнеров поддерживает как минимум двунаправленный

iterator

vector

deque

iterator

В большинстве случае вы будете использовать

iterator

iterator

iterator

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

iterator

std::sort

sort

template

void sort(RandomAccessIterator first, RandomAccessIterator last);

По имени типа итератора можно определить, что он ожидает итератор произвольного доступа. Если попробовать откомпилировать

sort

iterator

Категория итератора, предоставляемая определенным контейнером и требуемая определенным стандартным алгоритмом, — это то, что определяет, какой алгоритм с каким контейнером может работать. Многие из стандартных алгоритмов описаны далее в этой главе. Таблица 7.1 показывает сокращения, используемые в остальной части главы для указания типов итераторов, принимаемых алгоритмами в качестве аргументов.

Этот рецепт описывал итераторы, как они используются для контейнеров. Но шаблон итераторов используется не только для контейнеров, и, таким образом, имеются другие типы итераторов. Имеются потоковые итераторы, итераторы буферов потоков и итераторы хранения в необработанном виде, но они здесь не описываются.

Глава 6.

7.2. Удаление объектов из контейнера

Требуется удалить объекты из контейнера.

Для удаления одного или диапазона элементов используйте метод контейнера erase или один из стандартных алгоритмов. Пример 7.2 показывает пару различных способов удаления элементов из последовательностей.

Пример 7.2. Удаление элементов из контейнера

#include 

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

 list lstStr;

 lstStr.push_back("On");

 lstStr.push_back("a");

 lstStr.push_back("cloudy");

 lstStr.push_back("cloudy");

 lstStr.push_back("day");

 list::iterator p;

 // Найти то что требуется, с помощью find

 p = find(lstStr.begin(), lstStr.end(), "day");

 p = lstStr.erase(p); // Теперь p указывает на последний элемент

 // Или для удаления всех вхождений чего-либо используйте remove

 lstStr.erase(remove(lstStr.begin(), lstStr.end(), "cloudy"),

  listStr.end());

 printContainer(lstStr); // См. 7.10

}

Для удаления одного или нескольких элементов из контейнера используйте метод

erase

erase

iterator

iterator

iterator

erase

p = find(lstStr.begin(), lstStr.end(), "day");

p = lstStr.erase(p);

В результате объект, на который указывает

p

В последовательностях

erase

iterator

end

vector

vector

В ассоциативных контейнерах

erase

void

erase

lstStr.erase(std::remove(lstStr.begin(), lstStr.end(), "cloudy"),

 lstStr.end());

Обратите внимание, что я использую

erase

list

remove

iterator

erase

end

erase

obj

delete

obj == "cloudy"

remove

iterator

erase

p, end)

p

iterator

remove

remove

remove_if

Conn

struct IdleConnFn :

 public std::unary_function { // Включите эту строку,

 bool operator() (const Conn& c) const {      // чтобы он работал с

  if (с.getIdleTime() > TIMEOUT) {        // другими объектами из

  return(true);                 // 

  } else return(false);

 }

} idle;

Затем вызовите

remove_if

vec.erase(std::remove_if(vec.begin(), vec.end(), idle), vec.end());

Есть причина, по которой такие функторы следует наследовать от

unary_function

unary_function

typedef

not1

vec.erase(std::remove_if(vec.begin(), vec.end(); std::not1(idle)),

 vec.end());

Наконец, вам может потребоваться сохранить первоначальную последовательность (может, с помощью

const

remove_copy

remove_copy_if

remove_if

iterator

std::remove_copy(lstStr.begin(), lstStr.end(), lstStr2, "cloudy");

При использовании

remove_copy

erase

remove

Рецепты 6.2 и 7.1.

7.3. Случайное перемешивание данных

Имеется последовательность данных и требуется перемешать их так, чтобы они были расположены в случайном порядке.

Используйте стандартный алгоритм

random_shuffle

random_shuffle

Пример 7.3. Случайное перемешивание последовательностей

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

 vector v;

 back_insert_iterator > p = back_inserter(v);

 for (int i = 0; i < 10; ++i) *p = i;

 printContainer(v, true);

 random_shuffle(v.begin(), v.end());

 printContainer(v, true);

}

Вывод должен выглядеть примерно так.

-----

0123456789

-----

8192057346

random_shuffle

void random_shuffle(RndIter first, RndIter last);

void random_shuffle(RndIter first, RndIter last, RandFunc& rand);

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

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

iterator_traits::difference_type

struct RanNumGenFtor {

 size_t operator()(size_t n) const {

  return(rand() % n);

 }

} rnd;

random_shuffle(v.begin(), vend(), rnd);

Приложения

random_shuffle

string

vector

deque

7.4. Сравнение диапазонов

Имеется два диапазона и требуется сравнить их на равенство или определить, какой из них меньше, чем другой, основываясь на каком-либо порядке сортировки элементов.

В зависимости от типа выполняемого сравнения используйте один из стандартных алгоритмов —

equal

lexicographical_compare

mismatch

Пример 7.4. Различные типы сравнения

#include 

#include 

#include 

#include 

#include "utils.h"

using namespace std;

using namespace utils;

int main() {

 vector vec1, vec2;

 vec1.push_back("Charles");

 vec1.push_back("in");

 vec1.push_back("Charge");

 vec2.push_back("Charles");

 vec2.push_back("in");

 vec2.push_back("charge"); // Обратите внимание на строчную "с"

 if (equal(vec1.begin(), vec1.end(), vec2.begin())) {

  cout << "Два диапазона равны!" << endl;

 } else {

 cout << "Два диапазона HE равны!" << endl;

 }

 string s1 = "abcde";

 string s2 = "abcdf";

 string s3 = "abc";

 cout << boolalpha // Отображает логические значения как "true" или "false"

  << lexicographical_compare(s1.begin(), s1.end(),

  s1.begin(), s1.end()) << endl;

 cout << lexicographical_compare(s1.begin(), s1.end(),

  s2.begin(), s2.end()) << endl;

 cout << lexicographical_compare(s2.begin(), s2.end(),

  s1.begin(), s1.end()) << endl;

 cout << lexicographical_compare(s1.begin(), s1.end(),

  s3.begin(), s3.end()) << endl;

 cout << lexicographical_compare(s3.begin(), s3.end(),

  s1.begin(), s1.end()) << endl;

 pair iters =

  mismatch(s1.begin(), s1.end(), s2.begin());

 cout << "first mismatch = " << *(iters.first) << endl;

 cout << "second mismatch = " << *(iters.second) << endl;

}

Вывод примера 7.4 выглядит так.

Два диапазона НЕ равны!

false

true

false

false

true

first mismatch = e

second mismatch = f

Для сравнения двух последовательностей на равенство используйте

equal

equal

bool equal(In1 first1, In1 last1, In2 first2);

bool equal(In1 first1, In1 last1, In2 first2, BinPred pred);

equal

operator==

first1

last1

first2

pred

equal

equal

Если требуется узнать, где и как последовательности отличаются, используйте

lexicographical_compare

mismatch

lexicographical_compare

<

lexicographical_compare

bool lexicographical_compare(In1 first1, In1 last1,

 In2 first2, In2 last2);

bool lexicographical_compare(In1 first1, In1 last1,

 In2 first2, In2 last2, Compare comp);

Если

operator<

string s1 = "abcde";

string s2 = "abcdf";

string s3 = "abc";

lexicographical_compare(s1.begin(), s1.end(), // abcde < abcde

 s1.begin(), s1.end());             // = false

lexicographical_compare(s1.begin(), s1.end(), // abcde < abcdf

 s2.begin(s2.end());              // = true

lexicographical_compare(s2.begin(), s2.end(), // abcdf < abcde

 s1.begin(), s1.end());             // = false

lexicographical_compare(s1.begin(), s1.end(), // abcde < abc

 s3.begin(s3.end());              // = false

lexicographical_compare(s3.begin(), s3.end(), // abc < abcde

 s1.begin(), s1.end());            // = true

Сложность

lexicographical_compare

operator<

iter1

iter2

*iter1 < *iter2

*iter2 < *iter1

mismatch

equal

lexicographical_compare

bool

pair<>

pair mismatch(In1 first1, In1 last1, In2 first2);

pair mismatch(In1 first1, In1 last1, In2 first2, BinPred);

Два возвращаемых итератора указывают на различные элементы каждой из последовательностей. Рассмотрим пример 7.4.

string s1 = "abcde";

string s2 = "abcdf";

pair iters =

 mismatch(s1.begin(), s1.end(), s2.begin());

cout << "first mismatch = " << *(iters.first) << '\n'; // 'e'

cout << "second mismatch = " << *(iters.second) << '\n'; // 'f'

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

mismatch

last1

last1

end()

Вы, должно быть, заметили по объявлениям каждой из этих функций, что типы итераторов для каждой из этих последовательностей различны. Это означает, что две последовательности могут быть контейнерами разных типов, но при условии, что типы элементов, на которые указывают итераторы, имеют определенный для них

operator<

string

vector

string s = "Coke";

vector v;

v.push.back('c');

v.push_back('o');

v.push_back('k');

v.push_back('e');

std::cout << std::lexicographical_compare(s.begin(), s.end(),

 v.begin(), v.end()) << '\n';

Здесь каждый символ двух последовательностей сравнивается вне зависимости от типа контейнера, в которых они хранятся.

Стандартная библиотека C++ предоставляет несколько различных способов сравнения последовательностей. Если ни один из них вам не подходит, посмотрите на их исходный код — он является хорошим примером того, как надо писать собственные эффективные обобщенные алгоритмы.

Рецепт 7.1.

7.5. Объединение данных

Имеется две отсортированные последовательности и их требуется объединить.

Используйте либо шаблон функции

merge

inplace_merge

merge

inplace_merge

Пример 7.5. Объединение двух последовательностей

#include 

#include 

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

 vector v1, v2, v3;

 v1.push_back("a");

 v1.push_back("c");

 v1.push_back("e");

 v2.push_back("b");

 v2.push_back("d");

 v2.push_back("f");

 v3.reserve(v1.size() + v2.size() + 1);

 // Используйте back_inserter от итератора, чтобы избежать необходимости

 // помещать в контейнер набор объектов по умолчанию. Но это не означает,

 // что не требуется использовать reserve!

 merge(v1.begin(), v1.end(), v2.begin(), v2.end(),

  back_inserter >(v3));

 printContainer(v3);

 // Теперь выполняем действия

 random_shuffle(v3.begin(), v3.end());

 sort(v3.begin(), v3.begin() + v3.size() / 2);

 sort(v3.begin() + v3.size() / 2, v3.end());

 printContainer(v3);

 inplace_merge(v3.begin(), v3.begin() + 3, v3.end());

 printContainer(v3);

 // Однако если используется два списка, используйте list::merge.

 // Как правило, ...

 list lstStr1, lstStr2;

 lstStr1.push_back("Frank");

 lstStr1.push_back("Rizzo");

 lstStr1.push_back("Bill");

 lstStr1.push_back("Cheetoh");

 lstStr2.push_back("Allie");

 lstStr2.push_back("McBeal");

 lstStr2.push_back("Slick");

 lstStr2.push_back("Willie");

 lstStr1.sort(); // Отсортировать, иначе объединение выдаст мусор!

 lstStr2.sort();

 lstStr1.merge(lstStr2); // Заметьте, что это работает только для другого

             // списка того же типа

 printContainer(lstStr1);

}

Вывод примера 7.5 выглядит так.

-----

a

b

с

d

e

f

-----

b

d

e

a

c

f

-----

a

b

с

d

e

f

Allie

Bill

Cheetoh

Frank

McBeal

Rizzo

Slick

Willie

merge

operator<

merge

operator<

Объявления

merge

void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result);

void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result,

 BinPred comp)

Использование

merge

merge

back_inserter

merge(v1.begin(), v1.end(), v2.begin(), v2.end(),

 back_inserter(v3));

back_inserter

push_back

back_inserter

vector

v3

back_inserter(v3);

Указывать аргументы шаблона не требуется, так как

back_inserter

back_inserter >(v3);

Однако заметьте, что иногда вам потребуется явно указывать размер выходной последовательности, особенно при использовании в качестве такой последовательности

vector

vector

push_back

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

merge

Объединение двух

list

Рассмотрим список строк из примера 7.5:

lstStr1.sort(); // Сортируем, или объединение даст мусор!

lstStr2.sort(),

 lstStr1.merge(lstStr2); // Это list::merge

Есть две причины, по которым этот код отличается от вызова

std::merge

list

list::merge

void merge(list& lst);

template 

void merge(list& lst, Compare comp)

Где

T

string

Второе отличие состоит в том, что

list::merge

std::merge

list::merge

Также объединить две непрерывные последовательности можно с помощью

inplace_merge

inplace_merge

merge

inplace_merge

inplace_merge

Объявление

inplace_merge

void inplace_merge(Bid first, Bid mid, Bid last);

void inplace_merge(Bid first, Bid mid, Bid last, BinPred comp)

inplace_merge

merge

operator<

comp

7.6. Сортировка диапазона

Имеется диапазон элементов, которые требуется отсортировать.

Для сортировки диапазонов имеется целый набор алгоритмов. Можно выполнить обычную сортировку (в восходящем или нисходящем порядке) с помощью

sort

partial_sort

Пример 7.6. Сортировка

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

 cout << "Введите набор строк: ";

 istream_iterator start(cin);

 istream_iterator end; // Здесь создается "маркер"

 vector v(start, end);

 // Стандартный алгоритм sort сортирует элементы диапазона. Он

 // требует итератор произвольного доступа, так что он работает для vector.

 sort(v.begin(), v.end());

 printContainer(v);

 random_shuffle(v.begin(), v.end()); // См. 7.2

 string* arr = new string[v.size()];

 // Копируем элементы в массив

 copy(v.begin(), v.end(), &arr[0]);

 // Сортировка работает для любого типа диапазонов, но при условии, что

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

 sort(&arr[0], &arr[v.size()]);

 printRange(&arr[0], &arr[v.size()]);

 // Создаем список с такими же элементами

 list lst(v.begin(), v.end());

 lst.sort(); // Самостоятельная версия sort работать не будет, здесь требуется

     // использовать list::sort. Заметьте, что невозможно отсортировать

     // только часть списка.

 printContainer(lst);

}

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

Введите набор строк: a z b y c x d w

^Z

-----

a b c d w x y z

-----

w b y c a x z d

-----

a b c d w x y z

-----

a b c d w x y z

Сортировка — это очень часто выполняющаяся операция, и есть два способа отсортировать последовательность. Можно обеспечить хранение элементов в определенном порядке с помощью ассоциативного контейнера, но при этом длительность операции вставки будет иметь логарифмическую зависимость от размера последовательности. Либо можно сортировать элементы только по мере надобности с помощью

sort

Стандартный алгоритм

sort

operator<

void sort(Rnd first, Rnd last);

void sort(Rnd first, Rnd last, BinPred comp);

Как и в большинстве других алгоритмов, если

operator<

Если требуется, чтобы одинаковые элементы сохранили свой первоначальный порядок, используйте

stable_sort

Однако

sort

deque

vector

string

wstring

list

list::sort

list::sort

lst.sort();

Это отличает его от

std::sort

list

Концепция сортировки очень проста, но есть несколько вариаций на тему ее реализации в стандартной библиотеке. Следующий перечень описывает эти вариации.

partial_sort

Принимает три итератора произвольного доступа —

first

middle

last

first

middle

middle

last

first

middle

operator<

partial_sort_сору

Делает то же, что и

partial_sort

nth_element

Принимает три итератора произвольного доступа —

first

nth

last

nth

first

nth

nth

nth

last

nth

Также можно разделить элементы диапазона в соответствии с каким-либо критерием (функтором), и это является предметом обсуждения рецепта 7.7.

Рецепт 7.7.

7.7. Разделение диапазона

Имеется диапазон элементов, которые требуется каким-либо образом разделить на группы. Например, необходимо переместить в начало диапазона все элементы, которые меньше определенного значения.

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

partition

Пример 7.7. Разделение диапазона

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. рецепт 7.10

using namespace std;

int main() {

 cout << "Введите набор строк: ";

 istream_iterator start(cin);

 istream_iterator end; // Здесь создается "маркер"

 vector v(start, end);

 // Реорганизуем элементы в v так, чтобы те, которые меньше,

 // чем "foo", оказались перед остальными.

 vector::iterator p =

  partition(v.begin(), v.end(),

  bind2nd(less(), "foo"));

 printContainer(v);

 cout << "*p = " << *p << endl;

}

Вывод примера 7.7 выглядит примерно так.

Введите набор строк: a d f j k l

^Z

-----

a d f j k l

*p = j

После работы

partition

p

less(*p, "foo")

true

partition

true

true

Bi partition(Bi first, Bi last, Pred pred);

pred

true

false

less

bind2nd

vector::iterator p =

partition(v.begin(), v.end(),

bind2nd(less(), "foo"));

Здесь все элементы, которые меньше

"foo"

bind2nd

less(*i, "foo")

stable_partition

partition

set

multiset

map

multimap

partition

deque

vector

list

Рецепт 7.9.

7.8. Выполнение для последовательностей операций над множествами

Имеются последовательности, которые требуется реорганизовать с помощью операций над множествами, таких как объединение (union), различие (difference) или пересечение (intersection).

Для этой цели используйте специальные функции стандартной библиотеки.

set_union

set_difference

set_intersection

Пример 7.8. Использование операций над множествами

#include 

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

 cout << "Введите несколько строк: ";

 istream_iterator start(cin);

 istream_iterator end;

 set s1(start, end);

 cin.clear();

 cout << "Введите еще несколько строк: ";

 set s2(++start, end);

 set setUnion;

 set setInter;

 set setDiff;

 set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),

  inserter(setUnion, setUnion.begin()));

 set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),

  inserter(setDiff, setDiff.begin()));

 set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),

  inserter(setInter,setInter.begin()));

 cout << "Объединение:\n";

 printContainer(setUnion);

 cout << "Различие:\n";

 printContainer(setDiff);

 cout << "Пересечение:\n";

 printContainer(setInter);

}

Вывод этой программы выглядит примерно так (

printContainer

Введите несколько строк: a b c d

^Z

Введите еще несколько строк: d е f g

^Z

Объединение: a b с d e f g

Различие: a b c

Пересечение: d

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

inserter

back_inserter

back_inserter

Объявление

set_union

Out set_union(In first1, In last1, In first2, In last2, Out result);

Объявления

set_difference

set_intersection

set_symmetric_difference

Чтобы использовать эти функции, сделайте так, как показано в примере 7.8. Например, чтобы найти пересечение двух множеств, вызовите

set_intersection

set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),

 inserter(setInter, setInter.begin()));

Последний аргумент

set_intersection

inserter

inserter

insert

iterator

set

set

list

list lst1, lst2, lst3;

// Заполняем их данными

lst1.sort(); // Элементы должны быть отсортированы

lst2.sort();

set_symmetric_difference(lst1 begin(), lst1.end(),

lst2.begin(), lst2.end(), back_inserter(lst3));

Однако так как

list

inserter

back_inserter

back_inserter

inserter

push_back

lst3.resize(lst1.size() + lst2.size()),

set_symmetric_difference(lst1.begin(), lst1.end(),

 lst2.begin(), lst2.end(), lst3.begin())

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

begin

Если вы не знаете, что такое

set_symmetric_difference

Есть еще один момент, который следует знать при работе с операциями над множествами. Так как последовательности не обязаны быть уникальными, можно получить «множество» с повторяющимися значениями. Конечно, строго математически множество не может содержать повторяющиеся значения, так что этот момент может быть не очевиден, Рассмотрим, как будет выглядеть вывод примера 7.8, если вместо

set

list

set

set::insert

set

Введите несколько строк: a a a b с с

^Z

Введите еще несколько строк: a a b b с

^Z

Объединение a a a b b с с

Различие: a c

Пересечение: a a b с

Здесь операции над множествами перебирают обе последовательности и сравнивают соответствующие значения, определяя, что следует поместить в выходную последовательность.

Наконец, операции над множествами в их оригинальном виде (использующие для сравнения элементов

operator<

Рецепт 7.4.

7.9. Преобразование элементов последовательности

Имеется последовательность элементов, и с каждым элементом требуется выполнить какие-либо действия — либо на месте, либо скопировав их в другую последовательность.

Используйте стандартные алгоритмы

transform

for_each

Пример 7.9. Преобразование данных

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

// Преобразуем строки к верхнему регистру

string strToUpper(const string& s) {

 string tmp;

 for (string::const_iterator p = s.begin(); p != s.end(); ++p)

  tmp += toupper(*p);

 return(tmp);

}

string strAppend(const string& s1, const string& s2) {

 return(s1 + s2);

}

int main() {

 cout << "Введите несколько строк: ";

 istream_iterator start(cin);

 istream iterator end;

 list lst(start, end), out;

 // Используем преобразование с помощью унарной функции...

 transform(lst.begin(), lst.end(), back_inserter(out),

  strToUpper);

 printContainer(out);

 cin.clear();

 cout << Введите другой набор строк: ";

 list lst2(++start, end);

 out.clear();

 // ...или бинарную функцию и другую входную последовательность

 transform(lst.begin(), lst.end(), lst2.begin(),

  back_inserter(out), StrAppend);

 printContainer(out);

}

Очевидно, что для преобразования данных используется

transform

transfоrm

Вот как выглядит объявление

transform

Out transform(In first, In last, Out result, UnFunc f);

Out transform(In first1, In last1, In first2, In last2,

 Out result, BinFunc f);

Обе версии возвращают итератор, который указывает на один после конца результирующей последовательности.

Использование обеих версий очень просто. Чтобы скопировать строку из одной последовательности в другую, но с преобразованием ее к верхнему регистру, сделайте так, как в примере 7.9.

std::transform(lst.begin(), lst.end(),

 std::back_inserter(out), strToUpper);

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

std::transform(lst.begin(), lst.end(),

 lst.begin(), strToUpper);

Использование двух последовательностей и бинарной операции работает точно так же. и в качестве выходной последовательности можно использовать одну из входных.

Если требуется преобразовать элементы на месте, можно избежать накладных расходов на присвоение каждому элементу возвращаемого значения некоторой функции. Или, если функтор, который требуется использовать, изменяет свой объект-источник, то можно использовать

for_each

void strToUpperInPlace(string& s) {

 for (string::iterator p = s.begin(); p != s.end(); ++p)

  *p = std::toupper(*p);

}

// ...

std::for_each(lst.begin(), lst.end(), strToUpperInPlace);

Если же все, что требуется сделать, — это изменить саму последовательность, не изменяя каждый из ее элементов, то в рецепте 7.6 описывается множество стандартных алгоритмов для реорганизации элементов в последовательностях.

Рецепты 7.1 и 7.6.

7.10. Написание собственного алгоритма

Для диапазона требуется выполнить алгоритм, и ни один из стандартных алгоритмов не удовлетворяет требованиям.

Напишите алгоритм в виде шаблона функции и с помощью имен параметров шаблона укажите свои требования к итератору. В примере 7.10 показан измененный стандартный алгоритм

сору

Пример 7.10. Написание собственного алгоритма

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

template

Out copyIf(In first, In last, Out result, UnPred pred) {

 for ( ; first != last; ++first)

  if (pred(*first)) *results = *first;

 return(result);

}

int main() {

 cout << "Введите несколько строк: ";

 istream_iterator start(cin);

 istream_iterator end; // Здесь создается "маркер"

 vector v(start, end);

 list lst;

 copyIf(v.begin(), v.end(), back_inserter >(lst),

  bind2nd(less(), "cookie"));

 printContainer(lst);

}

Запуск примера 7.10 будет выглядеть примерно так.

Введите несколько строк: apple banana danish eclaire

^Z

-----

apple banana

Вы видите, что он копирует в результирующий диапазон только те значения, которые меньше, чем «cookie».

Стандартная библиотека содержит шаблон функции

сору

copy_if

true

Этот алгоритм прост, но в его реализации есть еще кое-что, что привлекает внимание. Посмотрев на объявление, вы увидите, что в нем присутствует три параметра шаблона.

template

Out copyIf(In first, In last, Out result UnPred pred) {

Первый параметр шаблона

In

copyIf

In

In

Out

InIter

Input_T

InputIterator.

Out

copyIf

Имеется, по крайней мере, две причины использования в

copyIf

vector

list

vector v(start, end);

list lst;

copyIf(v.begin(), v.end(), back_inserter >(lst),

 bind2nd(less(), "cookie"));

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

В примере 7.10 я в качестве начала выходного диапазона передаю

back_inserter

lst.begin

copyIf

back_inserter

push_back

lst

back_inserter

При написании собственного алгоритма для работы с диапазонами (т.е. со стандартными контейнерами) вы должны работать с аргументами-итераторами, а не с аргументами-контейнерами. У вас может возникнуть желание объявить

copyIf

copyIf

begin

end

copyIf

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

Рецепт 7.5.

7.11. Печать диапазона в поток

Имеется диапазон элементов, который требуется напечатать в поток, например, в

cout

Напишите шаблон функции, который принимает диапазон или контейнер, перебирает все его элементы и использует алгоритм

сору

ostream_iterator

Пример 7.11. Печать диапазона в поток

#include 

#include 

#include 

#include 

#include 

using namespace std;

int main() {

 // Итератор ввода - это противоположность итератору вывода: он

 // читает элементы из потока так. как будто это контейнер.

 cout << "Введите несколько строк: ";

 istream_iterator start(cin);

 istream_iterator end;

 vector v(start, end);

 // Используем выходной поток как контейнер, используя

 // output_iterator. Он создает итератор вывода, для которого запись

 // в каждый элемент эквивалентна записи в поток.

 copy(v.begin(), v.end(), ostreamIterator(cout, ", "));

}

Вывод примера 7.11 может выглядеть так.

Введите несколько строк: z x y a b с

^Z

z, x, y, a, b, с,

Потоковый итератор — это итератор, который основан на потоке, а не на диапазоне элементов контейнера, и позволяет рассматривать поток как итератор ввода (читать из разыменованного значения и увеличивать итератор) или итератор вывода (аналогично итератору ввода, но для записи в разыменованное значение вместо чтения из него). Это облегчает чтение значений (особенно строк) из потока, что делается в нескольких других примерах этой главы, и запись значений в поток, что делается в примере 7.11. Я знаю, что этот рецепт посвящен записи диапазона в поток, но позвольте мне немного отойти от этой задачи и, поскольку я использую потоковые итераторы во многих примерах этой главы, объяснить, что это такое.

В примере 7.11 показаны три ключевые части

istream_iterator

istream_iterator

istream_iterator start(cin);

В результате создается итератор с именем

start

vec.begin

vec

vector

string

istream_iterator

string

cin

cin

Вторая часть итератора входного потока — это маркер конца, который создается вот так.

istream_iterator end;

Стандартные контейнеры используют специальное значение «один после конца», указывающее на точку, где должно остановиться использование алгоритма. Так как итератор входного потока не имеет в памяти последнего элемента, он для создания логической конечной точки, представляющей точку остановки использования алгоритма, использует конструктор без аргументов.

Последней частью методики использования

istream_iterator

vector

start

end

vector v(start, end);

Именно здесь происходит чтение значений из потока. При создании

v

start

end

v

*start

cin

cin >> v[i]; // v - это vector

Другими словами, следующее значение, извлекаемое из

cin

string

vector

cin

Итераторы выходных потоков ведут себя аналогично итераторам потоков ввода. В примере 7.11 я копирую значения из своего

vector

cout

ostream_iterator

cout

copy(v.begin(), v.end(), ostream_iterator(cout, ", "));

Аргумент шаблона

ostream_iterator

string

ostream_iterator

ofstream

ostringstream

Если требуется дополнительное управление внешним видом вывода, например вывод последовательности в квадратных или фигурных скобках или отсутствие последнего разделителя в конце последовательности, то это потребует всего нескольких дополнительных строк кода. Пример 7.12 показывает тело

printContainer

printRange

Пример 7.12. Написание собственной функции печати

#include 

#include 

#include 

#include 

#include 

using namespace std;

template

void printContainer(const C& c, char delim = ',', ostream& out = cout) {

 printRange(c.begin(), c.end(), delim, out);

}

template

void printRange(Fwd first, Fwd last, char delim = ',', ostream& out = cout) {

 out << "{";

 while (first != last) {

  out << *first;

  if (++first != last)

  out << delim << ' ';

 }

 out << "}" << endl;

}

int main() {

 cout << "Введите набор строк: ";

 istream_iterator start(cin);

 istream_iterator end;

 vector v(start, end);

 printContainer(v);

 printRange(v.begin(), v.end(), ';', cout);

}

Функция

printRange

printContainer

operator<<

for_each