Алгоритмы STL

Часть раздела Объектно-ориентированное программирование путешествия по C++ на Coddy — урок 73 из 104.

Алгоритмы STL — это шаблонные функции, которые работают с диапазонами, определяемыми итераторами. Они находятся в заголовочных файлах <algorithm> и <numeric> и работают с любым контейнером, предоставляющим совместимые итераторы.

std::sort по умолчанию упорядочивает элементы по возрастанию:

#include <algorithm>
#include <vector>

std::vector<int> nums = {5, 2, 8, 1};
std::sort(nums.begin(), nums.end());
// nums: {1, 2, 5, 8}

std::find ищет значение и возвращает итератор на первое совпадение или end(), если оно не найдено:

auto it = std::find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    std::cout << "Found at index: " << (it - nums.begin());
}

std::transform применяет операцию к каждому элементу и сохраняет результаты в целевом диапазоне:

std::vector<int> doubled(nums.size());
std::transform(nums.begin(), nums.end(), doubled.begin(),
               [](int x) { return x * 2; });
// doubled: {2, 4, 10, 16}

std::accumulate из <numeric> объединяет все элементы в одно значение:

#include <numeric>

int sum = std::accumulate(nums.begin(), nums.end(), 0);
// сумма: 16 (1 + 2 + 5 + 8)

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

Задание

Легко

Давайте создадим анализатор оценок, который обрабатывает коллекцию чисел с использованием алгоритмов STL. Вы создадите вспомогательные функции, которые демонстрируют, как sort, find, transform и accumulate работают вместе для анализа данных.

Вы организуете свой код в двух файлах:

ScoreAnalyzer.h: Определите вспомогательные функции, использующие алгоритмы STL для обработки векторов целых чисел.
Создайте функцию с именем sortScores, которая принимает std::vector<int>& и сортирует его по возрастанию с помощью std::sort.

Создайте функцию с именем findScore, которая принимает const std::vector<int>& и целевое значение int. Используйте std::find для поиска цели. Если значение найдено, верните индекс (расстояние от начала). Если не найдено, верните -1.

Создайте функцию с именем applyBonus, которая принимает const std::vector<int>& и сумму бонуса int. Используйте std::transform, чтобы создать и вернуть новый вектор, в котором к каждой оценке добавлен бонус.

Создайте функцию с именем calculateAverage, которая принимает const std::vector<int>& и возвращает среднее значение в виде double. Используйте std::accumulate для вычисления суммы, а затем разделите её на размер вектора.

Создайте функцию с именем printVector, которая принимает const std::vector<int>& и выводит все элементы, разделенные пробелами, за которыми следует символ новой строки.
main.cpp: Считайте шесть входных значений (каждое на отдельной строке):
1. Первая оценка (целое число)
2. Вторая оценка (целое число)
3. Третья оценка (целое число)
4. Четвертая оценка (целое число)
5. Оценка для поиска (целое число)
6. Сумма бонуса для применения (целое число)
Создайте вектор с четырьмя оценками и продемонстрируйте работу алгоритмов:
1. Выведите Original: , а затем содержимое вектора
2. Отсортируйте оценки и выведите Sorted: , а затем отсортированный вектор
3. Найдите целевую оценку в отсортированном векторе. Если она найдена, выведите Found <value> at index <index>. Если не найдена, выведите <value> not found
4. Примените бонус к отсортированным оценкам и выведите With bonus: , а затем новый вектор
5. Вычислите и выведите среднее значение исходных отсортированных оценок (до бонуса) в формате Average: <value> с одним знаком после запятой

Например, при входных данных 75, 90, 60, 85, 85 и 5:

Original: 75 90 60 85 
Sorted: 60 75 85 90 
Found 85 at index 2
With bonus: 65 80 90 95 
Average: 77.5

При входных данных 100, 80, 95, 70, 50 и 10:

Original: 100 80 95 70 
Sorted: 70 80 95 100 
50 not found
With bonus: 80 90 105 110 
Average: 86.2

Не забудьте включить <algorithm> для sort, find и transform, а также <numeric> для accumulate. Используйте std::fixed и std::setprecision(1) из <iomanip> для форматирования среднего значения.

Шпаргалка

Алгоритмы STL — это шаблонные функции из <algorithm> и <numeric>, которые работают с диапазонами, определяемыми итераторами.

std::sort упорядочивает элементы по возрастанию:

#include <algorithm>
#include <vector>

std::vector<int> nums = {5, 2, 8, 1};
std::sort(nums.begin(), nums.end());
// nums: {1, 2, 5, 8}

std::find ищет значение и возвращает итератор на первое совпадение или end(), если значение не найдено:

auto it = std::find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    std::cout << "Found at index: " << (it - nums.begin());
}

std::transform применяет операцию к каждому элементу и сохраняет результаты в целевом диапазоне:

std::vector<int> doubled(nums.size());
std::transform(nums.begin(), nums.end(), doubled.begin(),
               [](int x) { return x * 2; });
// doubled: {2, 4, 10, 16}

std::accumulate из <numeric> объединяет все элементы в одно значение:

#include <numeric>

int sum = std::accumulate(nums.begin(), nums.end(), 0);
// sum: 16 (1 + 2 + 5 + 8)

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

Попробуйте сами

#include <iostream>
#include <vector>
#include <iomanip>
#include "ScoreAnalyzer.h"

using namespace std;

int main() {
    // Считать шесть входных значений
    int score1, score2, score3, score4;
    int searchTarget, bonusAmount;
    
    cin >> score1;
    cin >> score2;
    cin >> score3;
    cin >> score4;
    cin >> searchTarget;
    cin >> bonusAmount;
    
    // TODO: Создать вектор с четырьмя оценками
    
    // TODO: Вывести "Original:", а затем содержимое вектора
    
    // TODO: Отсортировать оценки и вывести "Sorted:", а затем отсортированный вектор
    
    // TODO: Найти целевую оценку в отсортированном векторе
    // Если найдено, вывести "Found <value> at index <index>"
    // Если не найдено, вывести "<value> not found"
    
    // TODO: Применить бонус к отсортированным оценкам и вывести "With bonus:", а затем новый вектор
    
    // TODO: Вычислить и вывести среднее арифметическое отсортированных оценок (до бонуса)
    // Использовать fixed и setprecision(1) для форматирования
    // Вывести в формате "Average: <value>"
    
    return 0;
}