Сторожевое значение

Сторожевое значение (англ. sentinel value, может подаваться также как флаговое значение, значение блокировки = англ. trip value, признак конца = англ. rogue value, сигнальное значение или фиктивные данные = англ. dummy data) — это специальное значение в контексте алгоритма, который использует его присутствие как условие прекращения, обычно в цикле или рекурсивных алгоритмах.

Сторожевое значение является видом внутриполосных данных^[a], которые позволяют зафиксировать конец данных, когда нет внеполосных данных (например, не указана явно длина). Значение должно быть выбрано таким образом, чтобы гарантировать отличие от возможных рассматриваемых данных, в противном случае может поступить преждевременный сигнал о конце данных. Сторожевое значение иногда известно как «Слон в Каире», термин из шутки, в которой слон используется как образец для завершения работы^[b]. В безопасных языках большинство сторожевых значений можно заменить вариантными типами, которые обеспечивают явную обработку исключительного случая.

Иногда имеет больше смысла вернуть null (неопределённый) указатель или null значение, или, при работе с вариантными типами, вернуть вариант none/null.

Некоторые примеры общеупотребительных сторожевых значений и их применения:

• Символ Null для обозначения конца нуль-терминированной строки.
• Указатель Null для обозначения конца связного списка или дерева.
• Установка старшего двоичного разряда в потоке одинакового размера данных, например, установка 8-го бита в потоке 7-битных ASCII символов, записанных в 8-битные байты, что означает специальное свойство (например, негативное видео, жирный шрифт или курсив) или конец потока.
• Отрицательное число для обозначения конца неотрицательных целых чисел.

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

Например, если ищем какое-то определённое значение в несортированном списке, каждый элемент будет сравниваться с этим значением и цикл завершится, если нужное значение будет найдено. Однако, значение в списке может отсутствовать и нужно проверять после каждого шага, что поиск завершился неуспешно. Если записать искомое значение в конец списка, неуспешное завершение поиска становится невозможным и никакого явного завершения цикла не требуется. После завершения поиска необходимо проверить, действительно ли найдено значение или это было добавленное значение. Но этот тест осуществляется только один раз, а не на каждой итерации^[3]. Дональд Кнут назывет это добавленное значение фиктивными данными (англ. dummy data), а не сторожевыми или сигнальными значениями (англ. sentinel).

Например, если ищем значение в массиве на языке C, прямой реализацией будет следующая (заметим использование отрицательного значения (отрицательного индекса) во избежание проблемы неопределённости («не найдено»)):

int find(int arr[], size_t len, int val) {
    for (int i = 0; i < len; i++) {
        if (arr[i] == val) {
            return i;
        }
    }
    return -1; // not found
}

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

int find(int arr[], size_t len, int val) {
    int i = 0;
    arr[len] = val; // add sentinel value
    while (arr[i] != val) {
        ++i;
    }
    return i < len ? i : -1;
}

Проверка i < len осталась, но она ушла из цикла, который теперь содержит только одну проверку (на значение), и цикл гарантированно завершится вследствие сторожевого значения. Имеется одна проверка, когда обнаружится сторожевое значение, и эта проверка заменяет проверку на каждой итерации.

Если нет возможности (или нежелательно) выделять и освобождать память для ещё одного элемента - можно временно заменить последний элемент массива на стража (sentinel):

int find(int arr[], size_t len, int val) {
    if (len == 0) {
        return -1;
    }
    int last = arr[len - 1];
    arr[len - 1] = val; // add sentinel value

    int i = 0;
    while (arr[i] != val) {
        ++i;
    }
    arr[len - 1] = last;
    return arr[i] == val ? i : -1;
}

Здесь пример возвращения null-указателей и null вариантных типов.

import std;

using std::nullopt;
using std::optional;
using std::string;
using std::string_view;
using std::vector;

struct User {
private:
    string name;
public:
    explicit User(string_view name):
        name{name} {}

    void setName(string_view s) noexcept {
        name = s;
    }

    [[nodiscard]]
    string getName() const noexcept {
        return name;
    }
};

[[nodiscard]]
User* findUserByName(vector<User>& users, string_view name) noexcept {
    for (size_t i = 0; i < users.size(); ++i) {
        if (users[i].getName() == name) {
            return &users[i];
        }
    }
    return nullptr; // Sentinel value: not found
}

[[nodiscard]]
optional<int> findIndex(string_view name, const vector<User>& users) noexcept {
    for (size_t i = 0; i < users.size(); ++i) {
        if (users[i].getName() == name) {
            return i;
        }
    }
    return nullopt; // Sentinel value: not found
}

• Предохранитель (программирование) Одним из методов защиты от переполнения буфера является использование специальных маркеров (canaries), которые размещаются рядом с буфером. Если злоумышленник перепишет данные за пределы буфера, маркер будет поврежден, что позволит программе обнаружить ошибку
• Проблема полупредикативности
• Слон в Каире
• Магическое число (программирование)
• Магическая строка
• Null object (шаблон проектирования)
• Баги форматирования и хранения дат