Глава 5 Основы работы с алгоритмами STL

В этой главе:

□ копирование элементов из одних контейнеров в другие;

□ сортировка контейнеров;

□ удаление конкретных элементов из контейнеров;

□ преобразование содержимого контейнеров;

□ поиск элементов в упорядоченных и неупорядоченных векторах;

□ ограничение допустимых значений вектора конкретным численным диапазоном с помощью 

std::clamp
;

□ определение шаблонов в строках с помощью 

std::search
и выбор оптимальной реализации;

□ выборка данных из крупных векторов;

□ создание перестановок во входных последовательностях;

□ реализация инструмента для слияния словарей.

Введение

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

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

sum
:


vector v {100, 400, 200 /*, ... */ };


int sum {0};

for (int i : v) { sum += i; }


cout << sum << '\n';


Поскольку эта задача является стандартной, для ее решения предусмотрен алгоритм STL:


cout << accumulate(begin(v), end(v), 0) << '\n';


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

accumulate
. Во многих ситуациях, однако, может возникнуть неловкий момент: приходится читать состоящий из десятка строк цикл только затем, чтобы узнать, что он решает стандартную задачу 
Х
, вместо того чтобы увидеть одну строку кода, в которой используется стандартный алгоритм, чье имя явно указывает на то, какую задачу он решает, например 
accumulate
, 
copy
, 
move
, 
transform
или 
shuffle
.

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

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

std::fill
. Поскольку итератор вектора может указать компилятору, что итерирует по непрерывной памяти, он может выбрать ту реализацию алгоритма 
std::fill
, которая задает процедуру C 
memset
. Если программист изменяет тип контейнера с 
vector
на 
list
, то алгоритм STL больше не может использовать процедуру 
memset
и должен итерировать по списку, чтобы обнулять элементы по одному. В том случае, если программист сам задействует процедуру 
memset
, алгоритм обнуления сможет работать только с векторами и массивами, поскольку другие структуры не хранят данные во фрагментах непрерывной памяти. В большинстве случаев не стоит изобретать велосипед, поскольку авторы библиотеки STL уже реализовали эти идеи и вам ничто не мешает воспользоваться их трудом.

Подытожим. Алгоритмы STL предоставляют такие преимущества.

□ Легкость сопровождения: по названию алгоритма сразу понятно, что именно он делает. Явные циклы зачастую труднее прочесть, и им нужно знать о том, какие именно структуры данных будут применяться, в отличие от стандартных алгоритмов.

□ Правильность: библиотеку STL создавали и анализировали профессионалы, она используется и тестируется многими программистами, и вам, скорее всего, не удастся достичь той же степени правильности, если вы будете самостоятельно реализовывать сложные фрагменты алгоритмов.

□ Эффективность: по умолчанию алгоритмы STL эффективны как минимум настолько же, насколько эффективны циклы, написанные вручную.


Большинство алгоритмов работают с итераторами. Принципы работы итераторов мы уже рассмотрели в главе 3. В настоящей главе сконцентрируемся на использовании алгоритмов STL для решения конкретных задач, чтобы понять, какие возможности они предоставляют. Разбор всех алгоритмов превратит эту книгу в очень скучный справочный материал по С++, а подобное руководство уже доступно для широкого круга читателей.

Самый лучший способ стать мастером STL заключается в том, чтобы всегда иметь справочный материал по С++ под рукой или хотя бы в закладках браузера. При решении какой-нибудь задачи каждый программист должен задуматься: «Существует ли в STL алгоритм для решения моей задачи?» — прежде чем писать код самостоятельно.

Хорошая и полная справка по C++ доступна по адресу http://en.cppreference.com/w/. Кроме того, этот материал можно скачать для чтения в режиме офлайн.


На собеседованиях хорошее знание алгоритмов STL зачастую считается показателем глубоких знаний языка С++.

Копируем элементы из одних контейнеров в другие

Большинство важных структур данных STL поддерживают итераторы. Это значит, что вы как минимум сможете получить итераторы с помощью функций 

begin()
и 
end()
, которые указывают на полезные данные и позволяют итерировать по ним. Перебор всегда выглядит одинаково, независимо от того, по какой структуре данных выполняется.

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

На примере алгоритма 

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


Как это делается

В этом примере мы разберем разные варианты алгоритма 

std::copy
.


1. Сначала включим заголовочные файлы для всех структур данных, которые будем использовать. Кроме того, объявим, что задействуем пространство имен 

std
:


#include 

#include 

#include 

#include 

#include 

#include 

#include 


using namespace std;


2. Далее будем использовать пары, содержащие целое число и строку. Чтобы красиво вывести их на экран, нужно перегрузить оператор потока 

<<
:


namespace std {

  ostream& operator<<(ostream &os, const pair &p)

  {

    return os << "(" << p.first << ", " << p.second << ")";

  }

}


3. В функции 

main
заполним вектор пар «число — строка» некоторыми значениями по умолчанию. Кроме того, объявим переменную map, связывающую численные и строковые значения:


int main()

{

  vector> v {

   {1, "one"}, {2, "two"}, {3, "three"},

   {4, "four"}, {5, "five"}};

 map m;


4. Теперь воспользуемся алгоритмом 

std::copy_n
, чтобы скопировать три пары из вектора в ассоциативный массив. Поскольку векторы и ассоциативные массивы значительно отличаются друг от друга, нужно выполнить преобразование элементов вектора с помощью параметра адаптера 
insert_iterator
. Его предоставляет функция 
std::inserter
. Пожалуйста, всегда помните о том, что использование алгоритмов наподобие 
std::copy_n
в комбинации с итераторами вставки — наиболее обобщенный способ скопировать/вставить элементы в другие структуры данных, хотя и не самый быстрый. Зачастую эффективнее всего для вставки элементов применять функции-члены конкретных структур данных.


  copy_n(begin(v), 3, inserter(m, begin(m)));


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

std::copy
. Итератор 
std::ostream_iterator
значительно помогает в этом вопросе, поскольку позволяет считать выходные данные пользовательской консоли еще одним контейнером, в который можно скопировать данные.


  auto shell_it (ostream_iterator>{cout,

                            ", "});

  copy(begin(m), end(m), shell_it);

  cout << '\n';


6. Опустошим ассоциативный массив, чтобы подготовить его к следующему эксперименту. В этот раз мы переместим в него все элементы вектора:


  m.clear();

  move(begin(v), end(v), inserter(m, begin(m)));


7. Теперь снова выведем на экран содержимое ассоциативного массива. Более того, поскольку алгоритм 

std::move
изменяет еще и источник данных, выведем на экран и содержимое вектора. Таким образом, можно увидеть, что с ним произошло, когда он стал источником данных.


  copy(begin(m), end(m), shell_it);

 cout << '\n';

  copy(begin(v), end(v), shell_it);

 cout << '\n';

}


8. Скомпилируем программу, запустим ее и посмотрим на результат. Первые две строки выглядят просто. Они отражают содержимое ассоциативного массива после применения алгоритмов copy_n и move. Третья строка выглядит интереснее, поскольку в ней показывается, что строки вектора, который мы использовали в качестве источника данных, теперь пусты. Это произошло потому, что содержимое строк было не скопировано, а перемещено (т.е. ассоциативный массив применяет данные строк из кучи, на которые ссылались объекты строк, размещенные в векторе).

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


$ ./copying_items

(1, one), (2, two), (3, three),

(1, one), (2, two), (3, three), (4, four), (5, five),

(1, ), (2, ), (3, ), (4, ), (5, ),



Как это работает

Поскольку алгоритм 

std::copy
является одним их самых простых алгоритмов STL, его реализация очень короткая. Взглянем на то, как его можно было бы реализовать:


template 

OutputIterator copy(InputIterator it, InputIterator end_it,

           OutputIterator out_it)

{

  for (; it != end_it; ++it, ++out_it) {

   *out_it = *it;

  }

  return out_it;

}


Этот код выглядит как попытка вручную реализовать копирование элементов из одного итерабельного диапазона в другой. Кто-то может задаться вопросом: «Почему бы и не реализовать его вручную? Цикл выглядит достаточно просто, и мне даже не понадобится возвращаемое значение». Это, конечно, хороший вопрос.

Хотя алгоритм 

std::copy
не самый лучший пример и не может продемонстрировать, как код становится короче, другие алгоритмы выглядят гораздо сложнее. Это может быть неочевидно, но для алгоритмов STL выполняется скрытая оптимизация. Если мы будем пользоваться алгоритмом 
std::copy
для структур данных, которые хранят свои элементы в непрерывной памяти (например, 
std::vector
и 
std::array
), и самим элементам будет легко присвоить копию, то компилятор выберет совершенно другую реализацию (предполагается, что типом итератора является указатель):


template 

OutputIterator copy(InputIterator it, InputIterator end_it,

           OutputIterator out_it)

{

  const size_t num_items (distance(it, end_it));

 memmove(out_it, it, num_items * sizeof(*it));

 return it + num_items;

}


Перед вами упрощенная версия реализации алгоритма 

std::copy
с помощью 
memmove
. Она работает быстрее, чем стандартная версия с циклами, и в то же время не такая читабельная. Но тем не менее пользователи алгоритма 
std::copy
автоматически получают от него выгоду, если типы их аргументов соответствуют требованиям, выполнение которых необходимо для оптимизации. Компилятор выбирает для заданного алгоритма самую быструю реализацию из возможных, а код пользователя выражает, что именно делает алгоритм, не обрастая ненужными деталями.

Алгоритмы STL зачастую предоставляют наилучшее сочетание читабельности и оптимальности реализации.


Типам обычно можно легко присвоить копию, если они состоят из одного или нескольких (обернутых в класс/структуру) скалярных типов или классов, которые легко переместить с помощью 

memcopy/memmove
, не вызывая определенный пользователем оператор присваивания копии.


Кроме того, мы использовали алгоритм 

std::move
. Он работает точно так же, как и алгоритм 
std::copy
, но применяет 
std::move(*it)
к итератору источника в цикле, чтобы преобразовать значения 
lvalues
к значениям 
rvalues
. Это позволяет компилятору выбрать оператор присваивания перемещением целевого объекта вместо оператора присваивания копированием. Для многих сложных объектов данный способ работает быстрее, но при этом уничтожается исходный объект.

Сортируем контейнеры

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

Поскольку данную задачу уже когда-то решили, программисты не должны снова тратить на нее время; разве что для обучения.


Как это делается

В этом примере мы поработаем с алгоритмами 

std::sort
и 
std::partial_sort
.


1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен 

std
:


#include 

#include 

#include 

#include 

#include 


using namespace std;


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


static void print(const vector &v)

{

  copy(begin(v), end(v), ostream_iterator{cout, ", "});

 cout << '\n';

}


3. Начнем с вектора, содержащего некоторые числа:


int main()

{

  vector v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};


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


  random_device rd;

  mt19937 g {rd()};


5. Функция 

std::is_sorted
говорит о том, было ли отсортировано содержимое контейнера. Эта строка должна вывести значение 
1
:


  cout << is_sorted(begin(v), end(v)) << '\n';


6. С помощью 

std::shuffle
мы перемешаем содержимое вектора, чтобы позднее отсортировать его. Первые два аргумента указывают на диапазон данных, который будет перемешан, а третий — генератор случайных чисел:


  shuffle(begin(v), end(v), g);


7. Функция 

is_sorted
должна теперь вернуть значение 
false
, а на экране мы увидим значение 
0
, значения вектора должны остаться прежними, но их порядок изменится. Мы увидим это, когда выведем на экран его содержимое:


  cout << is_sorted(begin(v), end(v)) << '\n';

 print(v);


8. Теперь восстановим исходный порядок элементов с помощью алгоритма 

std::sort
. Вызвав те же команды на консоли, мы увидим значения вектора, отсортированные по возрастанию:


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

  cout << is_sorted(begin(v), end(v)) << '\n';

 print(v);


9. Еще одна интересная функция — 

std::partition
. Возможно, мы не хотим полностью сортировать список, поскольку достаточно поместить в начало те элементы, чье значение не превышает некий предел. Секционируем вектор, чтобы переместить все элементы, значение которых меньше 
5
, в начало, и выведем результат на экран:


  shuffle(begin(v), end(v), g);

  partition(begin(v), end(v), [] (int i) { return i < 5; });

 print(v);


10. Следующая функция, связанная с сортировкой, — 

std::partial_sort
. Ее можно использовать для сортировки содержимого контейнера, но не в полной мере. Эта функция поместит 
N
самых маленьких элементов в начало контейнера в отсортированном виде. Остальная часть элементов останется во второй половине, они не будут отсортированы.


 shuffle(begin(v), end(v), g);

  auto middle (next(begin(v), int(v.size()) / 2));

  partial_sort(begin(v), middle, end(v));

  print(v);


11. Что, если мы хотим отсортировать структуру данных, не поддерживающую оператора сравнения? Определим такую структуру и создадим следующий вектор элементов:


  struct mystruct {

   int a;

    int b;

  };

  vector mv {{5, 100}, {1, 50}, {-123, 1000},

             {3, 70}, {-10, 20}};


12. Функция 

std::sort
опционально принимает в качестве третьего аргумента функцию сравнения. Воспользуемся данным обстоятельством и передадим ей такую функцию. Для демонстрации того, что это возможно, мы будем сравнивать элементы на основе второго поля, 
b
. Таким образом, элементы отсортируются на основе поля 
mystruct::b
, а не поля 
mystruct::a
:


  sort(begin(mv), end(mv),

    [] (const mystruct &lhs, const mystruct &rhs) {

     return lhs.b < rhs.b;

  });


13. Последним шагом будет вывод на экран упорядоченного вектора, содержащего элементы типа 

mystruct
.


  for (const auto &[a, b] : mv) {

   cout << "{" << a << ", " << b << "} ";

  }

  cout << '\n';

}


14. Скомпилируем и запустим программу.

Первое значение 

1
получено от вызова функции 
std::is_sorted call
после инициализации упорядоченного вектора. Далее мы перемешали значения вектора и получили значение 
0
после второго вызова функции 
is_sorted
. В третьей строке показаны все элементы вектора после перемешивания. Следующее значение 
1
— это результат вызова функции 
is_sorted
после повторной сортировки с помощью алгоритма 
std::sort
.

Далее мы снова перемешали вектор и секционировали его, задействовав алгоритм 

std::partition
. Можно увидеть, что все элементы, чье значение не превышает 
5
, находятся слева от значения 
5
в векторе. Остальные элементы, чье значение превышает 
5
, стоят справа. За исключением этого они выглядят упорядоченными.

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

std::partial_sort
. Все элементы в первой половине вектора выглядят отсортированными, а остальные — нет.

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

mystruct
. Они строго отсортированы по значению второго члена.


$ ./sorting_containers

1

0

7, 1, 4, 6, 8, 9, 5, 2, 3, 10,

1

1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

1, 2, 4, 3, 5, 7, 8, 10, 9, 6,

1, 2, 3, 4, 5, 9, 8, 10, 7, 6,

{-10, 20} {1, 50} {3, 70} {5, 100} {-123, 1000}


Как это работает

Мы использовали разные алгоритмы, связанные с сортировкой (табл. 5.1).

Для объектов, не имеющих реализации оператора сравнения 

<
, можно предоставить собственные функции сравнения. Этим функциям всегда следует иметь сигнатуру 
bool имя_функции(const T &lhs, const T &rhs)
, и они не должны вызывать побочные эффекты во время выполнения.

Существуют и другие алгоритмы, такие как 

std::stable_sort
, которые сортируют элементы, но сохраняют порядок элементов с одинаковым ключом сортировки, и 
std::stable_partition
.


Алгоритм 

std::sort
имеет разные реализации. В зависимости от природы аргументов итератора его можно реализовать как сортировку методом выбора, вставки или слияния или полностью оптимизировать для небольшого диапазона элементов. С точки зрения пользователя нас это, как правило, не волнует.

Удаляем конкретные элементы из контейнеров

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

Фильтрация элементов из структур данных (или простое удаление конкретных элементов) работает по-разному для разных структур данных. В связанных списках (например, 

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

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

std::remove
и 
std::remove_if
.


Как это делается

В этом примере мы преобразуем содержимое вектора, удалив из него элементы разными способами.


1. Импортируем все необходимые заголовочные файлы и объявим об использовании пространства имен 

std
:


#include 

#include 

#include 

#include 


using namespace std;


2. Короткая вспомогательная функция print выведет на экран содержимое вектора:


void print(const vector &v)

{

  copy(begin(v), end(v), ostream_iterator{cout, ", "});

  cout << '\n';

}


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


int main()

{

  vector v {1, 2, 3, 4, 5, 6};

  print(v);


4. Теперь удалим из вектора все элементы со значением 

2
. Функция 
std::remove
переместит другие элементы так, что единственное значение 
2
, присутствующее в векторе, испарится. Поскольку длина реального содержимого вектора сократилась после удаления элементов, функция 
std::remove
вернет итератор, указывающий на новую конечную позицию. Элементы, стоящие между новым и старым конечными итераторами, считаются мусором, так что дадим вектору команду удалить их. Окружаем две строки, связанные с удалением этих элементов, новой областью видимости, поскольку итератор 
new_end
в дальнейшем станет некорректным, вследствие чего может мгновенно выйти из области видимости:


  {

   const auto new_end (remove(begin(v), end(v), 2));

   v.erase(new_end, end(v));

  }

  print(v);


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

std::remove_if
, принимающую подобные предикаты:


  {

   auto odd_number ([](int i) { return i % 2 != 0; });

   const auto new_end ( 

    remove_if(begin(v), end(v), odd_number));

  v.erase(new_end, end(v)); 

 } 

 print(v);


6. Далее поработаем с алгоритмом 

std::replace
. Воспользуемся им, чтобы переписать все значения 
4
значениями 
123
. Функция 
std::replace
существует и в форме 
std::replace_if
, которая также принимает функции-предикаты.


  replace(begin(v), end(v), 4, 123);

 print(v);


7. Заполним вектор совершенно новыми значениями и создадим два новых пустых вектора, чтобы провести еще один эксперимент:


  v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  vector v2; vector v3;


8. Далее снова реализуем предикат для нечетных чисел и еще одну функцию-предикат, которая решает прямо противоположную задачу: сообщает, является ли заданное число четным:


  auto odd_number  ([](int i) { return i % 2 != 0; });

 auto even_number ([](int i) { return i % 2 == 0; });


9. Следующие две строки делают одно и то же: копируют четные значения в векторы 

v2
и 
v3
. В первой строке это делается с помощью алгоритма 
std::remove_copy_if
, копирующего все из исходного контейнера в другой контейнер, который не соответствует ограничению, налагаемому предикатом. В другой строке используется алгоритм 
std::copy_if
, который копирует все значения, удовлетворяющие ограничению, налагаемому предикатом:


  remove_copy_if(begin(v), end(v),

          back_inserter(v2), odd_number);

 copy_if(begin(v), end(v),

  back_inserter(v3), even_number);


10. Вывод на экран двух векторов должен дать одинаковый результат: 


  print(v2);

 print(v3);

}


11. Скомпилируем и запустим программу. В первой строке показан вектор после инициализации. Во второй — вектор, из которого мы удалили все значения 

2
. В следующей строке представлен результат удаления всех нечетных чисел. Перед четвертой строкой мы заменили все значения 
4
на значения 
123
.

В последних двух строках показываются векторы 

v2
и 
v3
:


$ ./removing_items_from_containers

1, 2, 3, 4, 5, 6,

1, 3, 4, 5, 6,

4, 6,

123, 6,

2, 4, 6, 8, 10,

2, 4, 6, 8, 10,



Как это работает

Мы использовали различные алгоритмы, связанные с фильтрацией данных (табл. 5.2).

Для каждого из перечисленных алгоритмов существует версия 

*_if
, принимающая вместо значения функцию-предикат, которая затем выводит, какие значения будут удалены или заменены.

Преобразуем содержимое контейнеров

Если 

std::copy
является самым простым алгоритмом STL для работы с диапазонами данных, то 
std::transform
— второй по сложности алгоритм STL. Как и copy, он копирует элементы из одного диапазона данных в другой, но дополнительно принимает функцию преобразования. Она может изменить значение выходного типа до того, как это значение окажется в выходном диапазоне. Более того, данная функция может создать значение совершенно другого типа, что может быть полезно, если входной и выходной диапазоны данных имеют разные типы. Этот алгоритм прост в использовании, но в то же время очень полезен, вследствие чего он становится стандартным компонентом, который можно применять во многих повседневных программах.


Как это делается

В этом примере мы воспользуемся алгоритмом 

std::transform
, чтобы изменить элементы вектора путем копирования.


1. Как обычно, сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен 

std
, что сэкономит немного времени:


#include 

#include 

#include 

#include 

#include 

#include 


using namespace std;


2. В качестве примера исходной структуры данных возьмем вектор, содержащий простые целые числа:


int main()

{

  vector v {1, 2, 3, 4, 5};


3. Теперь скопируем все элементы в итератор вывода 

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


  transform(begin(v), end(v),

   ostream_iterator{cout, ", "},

   [] (int i) { return i * i; });

  cout << '\n';


4. Выполним еще одно преобразование. Например, из числа 

3
можно сгенерировать точную и читабельную строку 
3^2 = 9
. Следующая функция 
int_to_string
делает именно это с помощью объекта 
std::stringstream
:


  auto int_to_string ([](int i) {

   stringstream ss;

    ss << i << "^2 = " << i * i;

   return ss.str();

  });


5. Функция, которую мы только что реализовали, возвращает строковые значения на основе числовых. Мы также могли бы сказать, что она соотносит строки и числа. С помощью функции transform можно скопировать эти соотношения из вектора чисел в вектор строк:


  vector vs;

  transform(begin(v), end(v), back_inserter(vs),

        int_to_string);


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


  copy(begin(vs), end(vs),

   ostream_iterator{cout, "\n"});

}


7. Скомпилируем и запустим программу:


$ ./transforming_items_in_containers

1, 4, 9, 16, 25,

1^2 = 1

2^2 = 4

3^2 = 9

4^2 = 16

5^2 = 25


Как это работает

Функция 

std::transform
работает точно так же, как и 
std::copy
, но вместе с копированием элементов в новый диапазон применяет к значению пользовательскую функцию преобразования до того, как итоговый результат будет присвоен итератору по месту назначения.

Выполняем поиск элементов в упорядоченных и неупорядоченных векторах

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

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

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

std::find
(простой линейный поиск), 
std::equal_range
(бинарный поиск) и их вариациям.


Как это делается

В этом примере мы используем алгоритмы линейного и бинарного поиска на небольшом диапазоне данных.


1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен 

std
:


#include 

#include 

#include 

#include 

#include 


using namespace std;


2. Наш диапазон данных будет состоять из структур типа 

city
, в которых хранится название города и количество проживающих в нем человек:


struct city {

  string name;

 unsigned population;

};


3. Алгоритмы поиска должны уметь сравнивать элементы друг с другом, поэтому перегружаем оператор 

==
для экземпляров типа 
city
:


bool operator==(const city &a, const city &b) {

  return a.name == b.name && a.population == b.population;

}


4. Кроме того, мы хотим выводить на экран экземпляры типа 

city
, поэтому перегрузим оператор потока 
<<
:


ostream& operator<<(ostream &os, const city &city) {

 return os << "{" << city.name << ", "

       << city.population << "}";

}


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

.


template 

static auto opt_print (const C &container)

{

  return [end_it (end(container))] (const auto &item) {

   if (item != end_it) {

    cout << *item << '\n';

   } else {

    cout << "\n";

   }

  };

}


6. Начнем с рассмотрения примера вектора, содержащего названия немецких городов:


int main()

{

  const vector c {

   {"Aachen", 246000},

   {"Berlin", 3502000},

   {"Braunschweig", 251000},

   {"Cologne", 1060000}

  };


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

city
и принимающую конечный итератор нашего вектора 
c
:


  auto print_city (opt_print(c));


8. Используем алгоритм 

std::find
для поиска элемента вектора, он сохранит элемент для города Кельна. Поначалу эта операция поиска выглядит бессмысленной, поскольку мы получаем именно тот элемент, который искали. Но ранее мы не знали его позицию в векторе, а функция 
find
возвращает нам и ее. Однако мы могли бы, например, создать такой перегруженный оператор 
==
для структуры 
city
, который сравнивал бы только названия городов, не зная численности населения. Но это был бы пример плохого стиля программирования. На следующем шаге мы сделаем это по-другому.


  {

   auto found_cologne (find(begin(c), end(c), city{"Cologne", 1060000}));

   print_city(found_cologne);

  }


9. Не зная численности населения города, а также не задействуя оператор ==, можно выполнить поиск только путем сравнения названия с содержимым вектора. Функция 

std::find_if
принимает объект функции-предиката вместо конкретного значения. Таким образом можно выполнить поиск элемента для города Кельна, зная только его название:


  {

   auto found_cologne (find_if(begin(c), end(c),

    [] (const auto &item) {

     return item.name == "Cologne";

   }));

   print_city(found_cologne);

  }


10. Чтобы сделать операцию поиска чуть более выразительной, можно реализовать конструктор предикатов. Объект функции 

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


  {

   auto population_more_than ([](unsigned i) {

    return [=] (const city &item) {

     return item.population > i;

   };

   });

   auto found_large (find_if(begin(c), end(c),

     population_more_than(2000000)));

    print_city(found_large);

  }


11. Использованные нами функции поиска проходят по контейнерам линейно. Поэтому они имеют коэффициент сложности O(n). В STL также содержатся функции бинарного поиска, которые работают за время O(log(n)). Сгенерируем новый диапазон данных, включающий лишь целочисленные значения, и напишем для него еще одну функцию 

print
:


  const vector v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

 auto print_int (opt_print(v));


12. Функция 

std::binary_search
возвращает булевы значения и просто уведомляет о нахождении элемента, но при этом его не возвращает. Важно, чтобы контейнер, для которого мы выполняем поиск, был упорядочен, поскольку в противном случае бинарный поиск не будет выполнен корректно.


  bool contains_7 {binary_search(begin(v), end(v), 7)};

 cout << contains_7 << '\n';


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

std::equal_range
. Она возвращает не один итератор для искомого элемента, а сразу пару. Первый итератор указывает на первый элемент, чье значение не меньше искомого, второй — на первый элемент, значение которого больше искомого. В нашем диапазоне данных, содержащем числа от 
1
до 
10
, первый итератор указывает на значение 
7
, поскольку это первый элемент, чье значение не меньше 
7
. Второй итератор — на значение 
8
, так как это первый элемент, значение которого больше 
7
. При наличии в нашем диапазоне нескольких элементов 
7
оба итератора представляли бы собой поддиапазон элементов.


  auto [lower_it, upper_it] (

   equal_range(begin(v), end(v), 7));

  print_int(lower_it);

 print_int(upper_it);


14. Если нужно получить только один итератор, то можно воспользоваться функциями 

std::lower_bound
или 
std::upper_bound
. Первая возвращает итератор на первый элемент, чье значение не меньше искомого, вторая — на первый элемент, чье значение больше искомого:


  print_int(lower_bound(begin(v), end(v), 7));

  print_int(upper_bound(begin(v), end(v), 7));

}


15. Скомпилируем и запустим программу для подтверждения того, что наши предположения и результат ее работы совпадают:


$ ./finding_items

{Cologne, 1060000}

{Cologne, 1060000}

{Berlin, 3502000}

1

7

8

7

8


Как это работает

В этом примере мы использовали следующие алгоритмы поиска (табл. 5.3).

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

Рассмотрим более подробно принцип работы 

std::equal_range
. Представьте, что у нас есть вектор, 
v = {0,1,2,3,4,5,6,7,7,7,8}
и мы вызываем метод 
equal_range(begin(v),end(v),7);
, чтобы выполнить бинарный поиск значения 
7
. Функция equal_range возвращает пару итераторов, указывающих на нижнюю и верхнюю границы; они указывают на диапазон 
{7,7,7}
, поскольку в векторе содержится именно столько значений 
7
. Для большей ясности взгляните на рис. 5.1.

Сначала функция 

equal_range
использует типичный подход к выполнению бинарного поиска до тех пор, пока не встретит элементы, чье значение не меньше, чем искомое. Далее выполнение разбивается на вызовы методов 
lower_bound
и 
upper_bound
, чтобы объединить их возвращаемые значения в пару и затем вернуть эту пару вызывающей стороне.

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


template 

Iterator standard_binary_search(Iterator it, Iterator end_it, T value)

{

  const auto potential_match (lower_bound(it, end_it, value));

 if (potential_match != end_it && value == *potential_match) {

   return potential_match;

  }

  return end_it;

}


Эта функция использует вызов 

std::lower_bound
, чтобы найти первый элемент, чье значение не меньше, чем 
value
. Полученный результат 
potential_match
может соответствовать одному из трех сценариев.

□ Ни один элемент не соответствует нашему условию. В таком случае значение 

potential_match
будет идентично 
end_it
.

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

end_it
.

□ Элемент, на который указывает 

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


Если наш тип 

T
не поддерживает оператор 
==
, то должен поддерживать хотя бы оператор 
<
для выполнения бинарного поиска. Далее можно переписать сравнение как 
!(value < *potential_match) && !(*potential_match < value)
. Если найденный элемент не меньше и не больше искомого, то он должен быть равен искомому.

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

7
.


Обратите внимание: структуры данных наподобие 

std::map
, 
std::set
и т.д. имеют собственные функции 
find
. Они работают быстрее, чем более обобщенные алгоритмы, поскольку тесно связаны с реализациями структур данных.

Ограничиваем допустимые значения вектора конкретным численным диапазоном с помощью std::clamp

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

Обычно это значит, что нужно выполнить вызов 

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

Библиотека STL содержит полезные функции, которые можно применить для решения данной задачи: 

std::minmax_element
и 
std::clamp
. Эти функции можно использовать в совокупности с некоторыми лямбда-выражениями.


Как это делается

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

std::minmax_element
и 
std::clamp
.


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

std
:


#include 

#include 

#include 

#include 


using namespace std;


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

0
, поэтому независимо от того, какое смещение имели старые данные, нормализованные значения всегда будут соответствовать порядку нуля. Для повышения читабельности проигнорируем такой факт: значения 
max
и 
min
могут быть одинаковыми, что приведет к делению на ноль.


static auto norm (int min, int max, int new_max)

{

  const double diff (max - min);

  return [=] (int val) {

   return int((val - min) / diff * new_max);

  };

}


3. Еще один конструктор объектов функций с именем 

clampval
возвращает объект функции, который захватывает значения 
max
и 
min
и вызывает функцию 
std::clamp
, чтобы поместить получаемые значения в заданный диапазон:


static auto clampval (int min, int max)

{

  return [=] (int val) -> int {

   return clamp(val, min, max);

  };

}


4. Данные, которые мы будем нормализовывать, представляют собой вектор, содержащий разнообразные значения. Они могут быть, например, данными о температуре, высоте ландшафта или стоимости акций, изменяющимися с течением времени:


int main()

{

  vector v {0, 1000, 5, 250, 300, 800, 900, 321};


5. Чтобы нормализовать эти данные, нужно иметь наивысшее и наименьшее значения. Здесь поможет функция 

std::minmax_element
. Она возвращает пару итераторов, указывающих именно на эти два значения:


  const auto [min_it, max_it] (

   minmax_element(begin(v), end(v)));


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


  vector v_norm;

 v_norm.reserve(v.size());


7. С помощью функции 

std::transform
скопируем значения из первого вектора во второй. При копировании элементов преобразуем их благодаря вспомогательной функции нормализации. Минимальное и максимальное значения старого вектора равны 
0
и 
1000
. Минимальное и максимальное значения после нормализации равны 
0
и 
255
:


  transform(begin(v), end(v), back_inserter(v_norm),

       norm(*min_it, *max_it, 255));


8. Прежде чем реализовать вторую стратегию по нормализации, выведем полученный результат:


  copy(begin(v_norm), end(v_norm),

    ostream_iterator{cout, ", "});

  cout << '\n';


9. Снова используем тот же нормализованный вектор, чтобы продемонстрировать работу другой вспомогательной функции 

clampval
, которая сжимает старый диапазон к диапазону, в котором минимальное значение равно 
0
, а максимальное — 
255
:


  transform(begin(v), end(v), begin(v_norm),

       clampval(0, 255));


10. После вывода этих значений на экран пример будет закончен:


  copy(begin(v_norm), end(v_norm),

     ostream_iterator{cout, ", "});

  cout << '\n';

}


11. Скомпилируем и запустим программу. Поскольку значения элементов диапазона теперь попадают в диапазон от 

0
до 
255
, можно использовать их, например, как показатели яркости для цветовых кодов RGB:


$ ./reducing_range_in_vector

0, 255, 1, 63, 76, 204, 229, 81,

0, 255, 5, 250, 255, 255, 255, 255,


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


Как это работает

Помимо 

std::transform
мы использовали два алгоритма.

std::minmax_element
принимает начальный и конечный итераторы входного диапазона. Он проходит в цикле по диапазону данных и записывает в процессе максимальное и минимальное значения. Эти значения возвращаются в виде пары, которую мы затем применяем для функции масштабирования.

Функция 

std::clamp
, напротив, не работает с диапазоном данных. Она принимает три значения: входное, минимальное и максимальное. Результатом работы этой функции явится входное значение, обрезанное так, что будет находиться между указанными минимумом и максимумом. Кроме того, можно воспользоваться конструкцией 
max(min_val, min(max_val, x))
вместо 
std::clamp(x, min_val, max_val)
.

Находим шаблоны в строках с помощью функции std::search и выбираем оптимальную реализацию

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

std::string
уже содержит функцию 
find
, которая решает именно эту задачу; тем не менее в этом разделе мы сконцентрируемся на функции 
std::search
. Несмотря на то, что она применяется по большей части для строк, ее можно использовать для контейнеров всех видов. Самая интересная особенность 
std::search
заключается в том, что, начиная с C++17, у нее есть дополнительный интерфейс, позволяющий легко заменять алгоритм поиска. Эти алгоритмы оптимизированы, и пользователь может выбрать любой из них в зависимости от варианта применения. Вдобавок мы могли бы реализовать собственные алгоритмы поиска и подключить их в функцию 
std::search
.


Как это делается

В этом примере мы воспользуемся новой функцией 

std::search
для строк и опробуем ее разные вариации для объектов класса 
searcher
.


1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен 

std
:


#include 

#include 

#include 

#include 

#include 


using namespace std;


2. Мы будем выводить на экран подстроки из позиций, которые вернет алгоритм поиска, поэтому реализуем соответствующую вспомогательную функцию:


template 

static void print(Itr it, size_t chars)

{

  copy_n(it, chars, ostream_iterator{cout});

 cout << '\n';

}


3. Строка вида lorem-ipsum сгодится в качестве примера, мы будем искать в ней подстроку. В нашем случае таковой выступит сочетание 

"elitr"
:


int main()

{

  const string long_string {

   "Lorem ipsum dolor sit amet, consetetur"

   " sadipscing elitr, sed diam nonumy eirmod"};

 const string needle {"elitr"};


4. Старый интерфейс 

std::search
принимает начальный/конечный итераторы для строки, внутри которой мы будем искать конкретную подстроку. Он возвращает итератор, указывающий на подстроку, которую смог найти. Если поиск не удался, то он вернет конечный итератор:


  {

   auto match (search(begin(long_string), end(long_string),

             begin(needle), end(needle)));

   print(match, 5);

}


5. Версия функции 

std::search
, предлагаемая в C++17, принимает не две пары итераторов, а одну (начальный/конечный) и объект поиска. Объект 
std::default_searcher
принимает пару итераторов для подстроки, которую мы ищем в более крупной строке:


  {

   auto match (search(begin(long_string), end(long_string),

     default_searcher(begin(needle), end(needle))));

   print(match, 5);

  }


6. Суть этого изменения заключается в том, что так проще сменить алгоритм поиска. Объект 

std::boyer_moore_searcher
использует поисковый алгоритм Бойера — Мура, чтобы выполнять поиск несколько быстрее:


  {

   auto match (search(begin(long_string), end(long_string),

     boyer_moore_searcher(begin(needle),

                end(needle))));

   print(match, 5);

  }


7. В библиотеке STL версии C++17 появились три разные реализации поискового объекта. Третья реализация использует алгоритм Бойера—Мура—Хорспула.


  {

   auto match (search(begin(long_string), end(long_string),

     boyer_moore_horspool_searcher(begin(needle),

                    end(needle))));

   print(match, 5);

  }

}


8. Скомпилируем и запустим программу. Если все работает правильно, то мы должны увидеть несколько одинаковых строк:


$ ./pattern_search_string

elitr

elitr

elitr

elitr


Как это работает

Мы воспользовались четырьмя разными способами применения функции 

std::search
, чтобы получить одинаковые результаты. Какая функция больше подходит для конкретной ситуации?

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

s
, а сам шаблон — 
p
. Тогда выражения 
std::search(begin(s), end(s), begin(p), end(p));
и 
std::search(begin(s), end(s), default_searcher(begin(p), end(p));
станут делать одно и то же.

Другие поисковые объекты функций реализуют более сложные алгоритмы поиска:

□ 

std::default_searcher
— выполняет переадресацию к устаревшей реализации 
std::search
;

□ 

std::boyer_moore_searcher
— использует поисковый алгоритм Бойера — Мура;

□ 

std::boyer_moore_horspool_searcher
— по аналогии применяет алгоритм Бойера — Мура — Хорспула.


Что делает другие алгоритмы такими особенными? Алгоритм Бойера — Мура разрабатывали, опираясь на конкретную идею: шаблон поиска сравнивается со строкой, начиная с конца шаблона и двигаясь справа налево. Если символ в строке для поиска отличается от символа шаблона на перекрывающихся позициях и даже не встречается в шаблоне, то становится очевидно, что последний можно сместить в строке поиска на количество позиций, равное его длине. Взгляните на рис. 5.3, где это происходит в шаге 1. Если же символ, для которого в данный момент выполняется сравнение, отличается от символа шаблона на этой позиции, но при этом есть в шаблоне, то алгоритм знает, на сколько символов нужно сместить шаблон вправо, чтобы правильно выровнять его относительно этого символа, а затем начинается новая итерация сравнения справа налево. На рис. 5.3 это происходит в шаге 2. Таким образом, алгоритм Бойера — Мура может опустить множество ненужных операций сравнения, в отличие от исходной реализации поиска.

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

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

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


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

Делаем выборку данных из крупных векторов

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

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

100
. К сожалению, сигнал имеет одинаковое значение по оси Y во всех точках! График, получаемый путем соединения этих точек, выглядит как идеальная прямая горизонтальная линия. Квадратные точки, однако, показывают, что мы получим, если будем брать образец каждые 
100+random(-15, +15)
точек. Полученный сигнал все еще значительно отличается от оригинального, но уже не пропадает полностью, как это было в случае с выборкой с фиксированным шагом.

Функция 

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


Как это делается

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


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

std
, чтобы сэкономить немного времени на вводе текста:


#include 

#include 

#include 

#include 

#include 

#include 

#include 


using namespace std;


2. С кодом работать будет гораздо проще, если мы сконфигурируем конкретные характеристики нашего алгоритма с помощью константных переменных. Укажем размер большого вектора случайных чисел, а также количество точек:


int main()

{

  const size_t data_points {100000};

 const size_t sample_points {100};


3. Большой вектор, заполненный случайными числами, должен наполняться с помощью генератора случайных чисел, выдающего числа, которые будут иметь нормальное распределение. Любое нормальное распределение характеризуется математическим ожиданием и квадратическим отклонением:


  const int mean {10};

 const size_t dev {3};


4. Теперь настроим генератор случайных чисел. Сначала создадим экземпляр 

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


  random_device rd;

 mt19937 gen {rd()};

  normal_distribution<> d {mean, dev};


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

std::generate_n
, который вызовет объект функции генератора, чтобы передать его возвращаемое значение в наш вектор благодаря итератору 
back_inserter
. Объект функции генератора оборачивает выражение 
d(gen)
, получающее случайное число от случайного устройства и передает его в объект распределения:


  vector v;

 v.reserve(data_points);

  generate_n(back_inserter(v), data_points,

   [&] { return d(gen); });


6. Теперь создадим еще один вектор, который содержит гораздо меньший диапазон точек:


  vector samples;

 v.reserve(sample_points);


7. Алгоритм 

std::sample
работает аналогично алгоритму 
std::copy
, но при этом принимает два дополнительных параметра — количество точек, получаемых из входного диапазона данных, и объект генератора случайных чисел, к которому он будет обращаться, чтобы получить случайные позиции пробных точек:


  sample(begin(v), end(v), back_inserter(samples),

      sample_points, mt19937{random_device{}()});


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


  map hist;

  for (int i : samples) { ++hist[i]; }


9. Наконец, пройдем в цикле по всем элементам, чтобы вывести нашу гистограмму на экран:


  for (const auto &[value, count] : hist) {

   cout << setw(2) << value << " "

     << string(count, '*') << '\n';

  }

}


10. После компиляции и запуска программы мы видим, что полученный вектор имеет характеристики нормального распределения (рис. 5.5):



Как это работает

Алгоритм 

std::sample
— это новый алгоритм, который появился в версии С++17. Его сигнатура выглядит следующим образом:


template

     class Distance, class UniformRandomBitGenerator>

OutIterator sample(InIterator first, InIterator last,

          SampleIterator out, Distance n,

          UniformRandomBitGenerator&& g);


Входной диапазон данных обозначается итераторами 

first
и 
last
, в то время как 
out
— итератор вывода. Эти итераторы выполняют ту же функцию, что и для функции 
std::copy;
элементы копируются из одного диапазона в другой. Алгоритм 
std::sample
является особенным с той точки зрения, что копирует только часть входного диапазона, поскольку делает выборку только 
n
элементов. Он использует равномерное распределение внутри системы, поэтому каждая точка на графике во входном диапазоне данных может быть выбрана с одинаковой вероятностью.

Выполняем перестановки во входных последовательностях

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

Независимо от того, зачем нужны все перестановки для какого-то диапазона значений, 

std::next_permutation
позволит это реализовать. Можно вызвать эту функцию для изменяемого диапазона, и она изменит порядок его элементов на следующую лексикографическую перестановку.


Как это делается

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

std::next_permutation
, чтобы сгенерировать и вывести на экран все перестановки для этих строк.


1. Как и обычно, сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен 

std
:


#include 

#include 

#include 

#include 

#include 


using namespace std;


2. Мы начнем с вектора строк, который заполним из стандартного потока ввода. Затем отсортируем вектор:


int main()

{

  vector v {istream_iterator{cin}, {}};

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


3. Далее выведем содержимое вектора на консоль. Затем вызовем функцию 

std::next_permutation
. Она систематически перемешивает содержимое вектора, чтобы сгенерировать перестановки этих элементов, которое мы снова выведем на экран. Вызов 
next_permutation
вернет значение 
false
, когда будет сгенерирована последняя перестановка.


  do {

   copy(begin(v), end(v),

      ostream_iterator{cout, ", "});

   cout << '\n';

  } while (next_permutation(begin(v), end(v)));

}


4. Скомпилируем и запустим функцию, передав ей какие-нибудь данные:


$ echo "a b c" | ./input_permutations

a, b, c,

a, c, b,

b, a, c,

b, c, a,

c, a, b,

c, b, a,



Как это работает

Алгоритм 

std::next_permutation
выглядит несколько странным. Это потому, что он принимает только пару итераторов (начальный и конечный) и возвращает значение 
true
, если может найти следующую перестановку. В противном случае он возвращает значение 
false
. Но что вообще означает выражение следующая перестановка?

Алгоритм, с помощью которого функция 

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


1. Найдем самое большое значение индекса 

i
, для которого выполняется условие 
v[i-1] < v[i]
. Если такого значения нет, то вернем значение 
false
.

2. Теперь найдем самое большое значение индекса 

j
, для которого выполняются условия 
j >= i и v[j] > v[i-1]
.

3. Меняем местами элементы на позициях 

j
и 
i-1
.

4. Изменим порядок элементов, находящихся между позицией 

i
и концом диапазона данных, на противоположный.

5. Вернем значение 

true
.


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

"c b a"
, например, то алгоритм завершил бы работу немедленно, так как данная строка представляет собой последний возможный лексикографический порядок элементов.

Инструмент для слияния словарей

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

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

Алгоритм 

std::merge
позволяет решить именно эту задачу, поэтому не придется тратить время зря. В данном разделе мы увидим, как пользоваться этим алгоритмом.


Как это делается

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

std::deque
. Программа считает словари из файла и стандартного потока ввода, а затем выведет один большой объединенный словарь в стандартный поток вывода.


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

std
:


#include 

#include 

#include 

#include 

#include 

#include 

#include 


using namespace std;


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


using dict_entry = pair;


3. Выведем данные пары на консоль и считаем их с пользовательского ввода, поэтому нужно перегрузить операторы 

<<
и 
>>
:


namespace std {

  ostream& operator<<(ostream &os, const dict_entry p)

  {

    return os << p.first << " " << p.second;

  }


  istream& operator>>(istream &is, dict_entry &p)

  {

    return is >> p.first >> p.second;

  }

}


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

std::deque
, состоящий из записей словаря, которые будут считываться из потока ввода до тех пор, пока тот не опустеет. Прежде чем вернуть контейнер, отсортируем его:


template 

deque from_instream(IS &&is)

{

  deque d {istream_iterator{is}, {}};

 sort(begin(d), end(d));

  return d;

}


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

dict.txt
— мы предполагаем, что он существует. Он содержит пары слов, размещенные построчно. Другой поток — это стандартный поток ввода.


int main()

{

  const auto dict1 (from_instream(ifstream{"dict.txt"}));

 const auto dict2 (from_instream(cin));


6. С помощью вспомогательной функции 

from_instream
мы уже отсортировали оба словаря и теперь можем передать их алгоритму 
std::merge
. Он принимает два входных диапазона данных, определенных с помощью пар итераторов ввода/вывода. Вывод будет показан на консоли пользователя.


  merge(begin(dict1), end(dict1),

     begin(dict2), end(dict2),

     ostream_iterator{cout, "\n"});

}


7. Мы уже можем скомпилировать программу, но перед запуском следует создать файл 

dict.txt
, содержащий какие-нибудь строки. Заполним его английскими словами и их переводом на немецкий язык:


car     auto

cellphone handy

house   haus


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


$ echo "table tisch fish fisch dog hund" | ./dictionary_merge

car auto

cellphone handy

dog hund

fish fisch

house haus

table tisch


Как это работает

Алгоритм 

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

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

std::inplace_merge
. Он делает то же самое, что и предыдущий, но не нуждается в итераторе вывода, поскольку работает на месте, о чем можно догадаться из имени. Он принимает три параметра: начальный итератор, итератор для середины и конечный итератор. Эти итераторы должны ссылаться на данные в одной структуре. Итератор для середины является одновременно конечным итератором для первого диапазона данных и начальным итератором для второго диапазона. Это значит, что алгоритм работает с одним диапазоном данных, который на самом деле состоит из двух диапазонов, размещенных один за другим, например 
{A,C,B,D}
. Первый поддиапазон — 
{A,C}
, а второй — 
{B,D}
. Алгоритм 
std::inplace_merge
может объединить оба диапазона в одной структуре данных, что приведет к результату 
{A,B,C,D}
.

ТЕЛЕГРАМ

Канал с обзорами, анонсами новинок и книжными подборками

Книжный Вестник

Бот для удобного поиска книг (если не нашлось на сайте)

Поиск книг

Свежие любовные романы в удобных форматах

Любовные романы

О психологии, саморазвитии и личностном росте

Саморазвитие

Детективы и триллеры, все новинки

Детективы

Фантастика и фэнтези, все новинки

Фантастика

Отборные классические книги

Классика
ВКОНТАКТЕ

Цитаты, афоризмы, стихи, книжные подборки, обсуждения и многое другое

Книжный Вестник
БИБЛИОТЕКИ

Библиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории

Любовные романы

Библиотека с фантастикой и фэнтези, а также смежных жанров

Фантастика

Самые популярные книги в формате фб2

Топ фб2 книги