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