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

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

Этот метод относится к внутриполосным данным, которые маркируют окончание данных при отсутствии внеполосной информации, например, явно указанной длины. Критически важно выбирать значение, гарантированно отличающееся от всех возможных обрабатываемых данных, чтобы избежать преждевременного сигнала о завершении. В некоторых контекстах используется термин «слон», происходящий из программистского фольклора, где слон символизирует завершающий элемент. В безопасных языках программирования сторожевые значения часто заменяются типами-опционами, обеспечивающими явную обработку граничных случаев.

В отдельных ситуациях более целесообразно возвращать нулевой указатель, null-значение или, при работе с опциональными типами, вариант none/null.

1. Примеры применения

Распространённые примеры сторожевых значений включают:

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

1. Разновидности метода

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

Например, при поиске определённого значения в неотсортированном списке каждый элемент последовательно сравнивается с искомым значением, и цикл завершается при успешном нахождении. Однако при отсутствии значения в списке требуется проверка после каждой итерации на неудачный исход поиска. Если добавить искомое значение в конец списка, исключается возможность неудачного завершения, и явная проверка становится излишней. После завершения поиска необходимо удостовериться, было ли найдено исходное значение или добавленное. Эта проверка выполняется единожды вместо проверки на каждой итерации. Дональд Кнут называет такое добавленное значение «фиктивными данными», отличая его от сторожевых или сигнальных значений.

1. 1. Практические реализации

1. 1. 1. Работа с массивами

Рассмотрим поиск значения в массиве на языке C. Прямая реализация может выглядеть следующим образом (обратите внимание на использование отрицательного значения для индикации неудачного поиска):

```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; // элемент не найден

} ```

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

```c int find(int arr[], size_t len, int val) {

   int i = 0;
   arr[len] = val; // добавление сторожевого значения
   while (arr[i] != val) {
       ++i;
   }
   return i < len ? i : -1;

} ```

Проверка `i < len` сохраняется, но выносится за пределы цикла, который теперь содержит только одну проверку на значение. Цикл гарантированно завершается благодаря сторожевому значению. Единоразовая проверка после цикла заменяет многократные проверки на каждой итерации.

Альтернативный подход предполагает временную замену последнего элемента массива сторожем:

```c int find(int arr[], size_t len, int val) {

   if (len == 0) {
       return -1;
   }
   int last = arr[len - 1];
   arr[len - 1] = val; // установка сторожевого значения

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

} ```

1. 1. Использование Null-значений

Пример возвращения nullptr и nullopt:

```cpp 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; // Сторожевое значение: не найдено

}

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; // Сторожевое значение: не найдено

} ```

1. См. также

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

1. Примечания

1. Литература

Категория:Связные списки Категория:Деревья (структуры данных)