полезно, если входной и выходной диапазоны данных имеют разные типы. Этот алгоритм прост в использовании, но в то же время очень полезен, вследствие чего он становится стандартным компонентом, который можно применять во многих повседневных программах.
Как это делается
В этом примере мы воспользуемся алгоритмом std::transform, чтобы изменить элементы вектора путем копирования.
1. Как обычно, сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен std, что сэкономит немного времени:
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <iterator>
using namespace std;
2. В качестве примера исходной структуры данных возьмем вектор, содержащий простые целые числа:
int main()
{
vector<int> v {1, 2, 3, 4, 5};
3. Теперь скопируем все элементы в итератор вывода ostream_iterator, чтобы вывести их на экран. Функция transform принимает объект функции, который принимает элементы, чей тип совпадает с типом элементов контейнера, и преобразует их во время каждой операции копирования. В данном случае мы вычисляем квадрат каждого числа, поэтому наш код выведет значения элементов вектора, возведенные в квадрат, избавив от необходимости сохранять их куда-либо.
transform(begin(v), end(v),
ostream_iterator<int>{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<string> vs;
transform(begin(v), end(v), back_inserter(vs),
int_to_string);
6. Выведем полученный результат на экран, и пример закончится:
copy(begin(vs), end(vs),
ostream_iterator<string>{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 <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <string>
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. Поисковые функции, как правило, возвращают итераторы. Последние указывают на элемент, если таковой был найден, или же на конечный итератор заданного контейнера. В последнем случае нам нельзя получить доступ к такому итератору. Поскольку мы собираемся вывести на экран результаты поиска, реализуем функцию, которая возвращает другой объект функции, инкапсулирующий конечный итератор структуры данных. При использовании этого объекта функции для вывода объектов на экран он сравнит свой итератор-аргумент с конечным итератором, а затем выведет на экран либо сам элемент, либо строку <end>.
template <typename C>
static auto opt_print (const C &container)
{
return [end_it (end(container))] (const auto &item) {
if (item != end_it) {
cout << *item << 'n';
} else {
cout << "<end>n";
}
};
}
6. Начнем с рассмотрения примера вектора, содержащего названия немецких городов:
int main()
{
const vector<city> c {
{"Aachen", 246000},
{"Berlin", 3502000},
{"Braunschweig", 251000},
{"Cologne", 1060000}
};
7. С помощью этой вспомогательной функции создадим функцию, выводящую на экран экземпляры типа city и принимающую конечный итератор нашего вектора c:
auto print_city (opt_print(c));
8. Используем алгоритм std::find для поиска элемента вектора, он сохранит элемент для города Кельна. Поначалу эта операция поиска выглядит бессмысленной, поскольку мы получаем именно тот элемент, который искали. Но ранее мы не знали его позицию в векторе, а функция find возвращает нам и ее. Однако мы могли бы, например, создать такой перегруженный оператор == для структуры city, который сравнивал бы только названия городов, не зная численности населения. Но это был бы пример плохого стиля программирования. На следующем шаге мы сделаем
