11.x – Резюме к главе 11 и небольшой тест

Добавлено 19 июня 2021 в 04:56

Краткое резюме

Еще одна глава пройдена! Следующая глава самая лучшая, и вы почти у цели! Остался только этот надоедливый тест...

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

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

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

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

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

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

Динамическая память выделяется в куче.

Стек вызовов отслеживает все активные функции (те, которые были вызваны, но еще не завершились) от начала программы до текущей точки выполнения. Локальные переменные размещаются в стеке. Стек имеет ограниченный размер. std::vector можно использовать для реализации стекового поведения.

Рекурсивная функция – это функция, которая вызывает сама себя. Все рекурсивные функции требуют условия завершения.

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

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

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

Небольшой тест

Вопрос 1

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

a) Функция с именем max(), которая принимает два значения double и возвращает большее из двух.

Ответ

double max(double x, double y);

b) Функция под названием swap(), которая меняет местами два числа int.

Ответ

void swap(int &x, int &y);

c) Функция с именем getLargestElement(), которая принимает динамически выделенный массив чисел int и возвращает наибольшее число таким образом, что вызывающий может изменить значение возвращаемого элемента (не забудьте параметр длины).

Ответ

// Примечание: в этом случае массив не может быть константным,
// потому что возврат неконстантной ссылки на константный элемент
// будет нарушением константности.
int& getLargestElement(int *array, int length);

Вопрос 2

Что не так с этими фрагментами кода?

int& doSomething()
{
    int array[]{ 1, 2, 3, 4, 5 };
    return array[3];
}

Ответ

doSomething() возвращает ссылку на локальную переменную, которая будет уничтожена при завершении работы doSomething.

int sumTo(int value)
{
    return value + sumTo(value - 1);
}

Ответ

Функция sumTo() не имеет условия завершения. Значение переменной в конечном итоге станет отрицательным, и функция будет бесконечно вызываться, пока стек не переполнится.

float divide(float x, float y)
{
    return x / y;
}
 
double divide(float x, float y)
{
    return x / y;
}

Ответ

Две функции divide не отличаются друг от друга, поскольку у них одинаковые имена и одинаковые параметры. Также существует вероятность проблемы деления на 0.

#include <iostream>
 
int main()
{
    int array[100000000]{};
 
    for (auto x: array)
        std::cout << x << ' ';
 
    std::cout << '\n';
 
    return 0;
}

Ответ

Массив слишком велик для размещения в стеке. Он должен быть размещен динамически.

#include <iostream>
 
int main(int argc, char *argv[])
{
    int age{ argv[1] };
    std::cout << "The user's age is " << age << '\n';
 
    return 0;
}

Ответ

argv[1] может не существовать. Если же он существует, argv[1] является строковым аргументом и не может быть преобразован в целое число с помощью присваивания.

Вопрос 3

Лучший алгоритм определения наличия значения в отсортированном массиве называется двоичным (бинарным) поиском.

Бинарный поиск работает следующим образом:

Найти центральный элемент массива (если в массиве четное количество элементов, округлить в меньшую сторону).
Если центральный элемент больше целевого элемента, отбросить верхнюю половину массива (или выполнить рекурсию для нижней половины)
Если центральный элемент меньше целевого элемента, отбросить нижнюю половину массива (или выполнить рекурсию для верхней половины).
Если центральный элемент равен целевому элементу, вернуть индекс центрального элемента.
Если отбрасывается весь массив, не найдя целевой элемент, вернуть контрольное значение, которое представляет «не найден» (в этом случае мы будем использовать -1, поскольку это недопустимый индекс массива).

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

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

Давайте посмотрим на пример того, как работает этот алгоритм, на массиве {3, 6, 7, 9, 12, 15, 18, 21, 24} и целевом значении 7. Сначала min = 0, max = 8, потому что мы ищем во всем массив (длина массива 9, поэтому индекс последнего элемента равен 8).

Шаг 1) Вычисляем среднюю точку min (0) и max (8), которая равна 4. Элемент № 4 имеет значение 12, которое больше нашего целевого значения. Поскольку массив отсортирован, мы знаем, что все элементы с индексом, равным или превышающим среднюю точку (4), должны быть слишком большими. Поэтому мы оставляем min неизменным и устанавливаем max равным 3.
Шаг 2) Мы вычисляем среднюю точку min (0) и max (3), которая равна 1. Элемент № 1 имеет значение 6, которое меньше нашего целевого значения. Поскольку массив отсортирован, мы знаем, что все элементы с индексом, равным или меньшим средней точки (1), должны быть слишком маленькими. Поэтому мы устанавливаем min на 2, а max не меняем.
Шаг 3) Мы вычисляем среднюю точку min (2) и max (3), которая равна 2. Элемент № 2 имеет значение 7, которое является нашим целевым значением. Итак, возвращаем 2.

Дан следующий код:

#include <iostream>
#include <iterator>
 
// array - это массив для поиска.
// target - это значение, которое мы пытаемся определить, есть оно или нет.
// min - это индекс нижней границы массива, в котором мы ищем.
// max - это индекс верхней границы массива, в котором мы ищем.
// binarySearch() должна возвращать индекс целевого элемента, если target найден, иначе -1
int binarySearch(const int *array, int target, int min, int max)
{
 
}
 
int main()
{
    constexpr int array[]{ 3, 6, 8, 12, 14, 17, 20, 21, 26, 32, 36, 37, 42, 44, 48 };
 
    // Мы собираемся протестировать набор значений, чтобы увидеть,
    // дают ли они ожидаемые результаты
    constexpr int numTestValues{ 9 };
    // Вот тестовые значения
    constexpr int testValues[numTestValues]{ 0, 3, 12, 13, 22, 26, 43, 44, 49 };
    // А вот ожидаемые результаты для каждого значения
    int expectedValues[numTestValues]{ -1, 0, 3, -1, -1, 8, -1, 13, -1 };
 
    // Перебираем все тестовые значения
    for (int count{ 0 }; count < numTestValues; ++count)
    {
        // Смотрим, есть ли наше тестовое значение в массиве
        int index{ binarySearch(array, testValues[count], 0, static_cast<int>(std::size(array)) - 1) };
        // Если результат соответствует ожидаемому, тогда отлично!
        if (index == expectedValues[count])
             std::cout << "test value " << testValues[count] << " passed!\n";
        else // иначе наша функция binarySearch() не работает
             std::cout << "test value " << testValues[count] << " failed.  There's something wrong with your code!\n";
    }
 
    return 0;
}

a) Напишите итеративную версию функции binarySearch.

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

Ответ

#include <cassert>
#include <numeric> // для std::midpoint
 
// array - это массив для поиска.
// target - это значение, которое мы пытаемся определить, есть оно или нет.
// min - это индекс нижней границы массива, в котором мы ищем.
// max - это индекс верхней границы массива, в котором мы ищем.
// binarySearch() должна возвращать индекс целевого элемента, если target найден, иначе -1
int binarySearch(const int *array, int target, int min, int max)
{
    assert(array); // убеждаемся, что массив существует
 
    while (min <= max)
    {
        // реализуем это итеративно
        int midpoint{ std::midpoint(min, max) };
        // до C++20
        // такой способ вычисления средней точки позволяет избежать переполнения
        // int midpoint{ min + ((max-min) / 2) };
 
        if (array[midpoint] > target)
        {
            // если array[midpoint] > target, то мы знаем, что число должно быть
            // в нижней половине массива
            // мы можем использовать midpoint - 1 в качестве верхнего индекса,
            // так как нам не нужно повторно тестировать среднюю точку на
            // следующей итерации
            max = midpoint - 1;
        }
        else if (array[midpoint] < target)
        {
            // если array[midpoint] < target, то мы знаем, что число должно быть
            // в верхней половине массива
            // мы можем использовать midpoint + 1 в качестве нижнего индекса,
            // так как нам не нужно повторно тестировать среднюю точку на
            // следующей итерации
            min = midpoint + 1;
        }
        else
        {
            return midpoint;
        }
    }
    
    return -1;
}

b) Напишите рекурсивную версию функции binarySearch.

Ответ

#include <cassert>
#include <numeric> // для std::midpoint
 
// array - это массив для поиска.
// target - это значение, которое мы пытаемся определить, есть оно или нет.
// min - это индекс нижней границы массива, в котором мы ищем.
// max - это индекс верхней границы массива, в котором мы ищем.
// binarySearch() должна возвращать индекс целевого элемента, если target найден, иначе -1
int binarySearch(const int *array, int target, int min, int max)
{
    assert(array); // убеждаемся, что массив существует
 
    // implement this recursively
 
    if (min > max)
        return -1;
 
    int midpoint{ std::midpoint(min, max) };
    // до C++20
    // такой способ вычисления средней точки позволяет избежать переполнения
    // int midpoint{ min + ((max-min) / 2) };
 
    if (array[midpoint] > target)
    {
        return binarySearch(array, target, min, midpoint - 1);
    }
    else if (array[midpoint] < target)
    {
        return binarySearch(array, target, midpoint + 1, max);
    }
    else
    {
        return midpoint;
    }
}

Совет

std::binary_search возвращает true, если значение присутствует в отсортированном списке.

std::equal_range возвращает итераторы к первому и последнему элементу с заданным значением.

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

C++ / CppLearnCppstd::vectorАлгоритмАргументДвоичный (бинарный) поискДля начинающихИтераторКомандная строкаКуча / HeapЛямбда / LambdaЛямбда-функцияОбучениеПрограммированиеРекурсияСтекСтек вызовов

Оглавление

Краткое резюме

Небольшой тест

Теги