Sentinel value

Some examples of common sentinel values and their uses:

• Null character for indicating the end of a null-terminated string.
• Null pointer for indicating the end of a linked list or a tree.
• A set most significant bit in a stream of equally spaced data values, for example, a set 8th bit in a stream of 7-bit ASCII characters stored in 8-bit bytes indicating a special property (like inverse video, boldface or italics) or the end of the stream.
• A negative integer for indicating the end of a sequence of non-negative integers.

A related practice, used in slightly different circumstances, is to place some specific value at the end of the data, in order to avoid the need for an explicit test for termination in some processing loop, because the value will trigger termination by the tests already present for other reasons. Unlike the above uses, this is not how the data is naturally stored or processed, but is instead an optimization, compared to the straightforward algorithm that checks for termination. This is typically used in searching.

For instance, when searching for a particular value in an unsorted list, every element will be compared against this value, with the loop terminating when equality is found; however, to deal with the case that the value should be absent, one must also test after each step for having completed the search unsuccessfully. By appending the value searched for to the end of the list, an unsuccessful search is no longer possible, and no explicit termination test is required in the inner loop. After the search, one must decide whether a true match was found, but this test needs to be performed only once rather than at each iteration. Knuth calls the value so placed at the end of the data, a dummy value rather than a sentinel.

Examples

Array

For example, if searching for a value in an array in C, a straightforward implementation is as follows; note the use of a negative number (invalid index) to solve the semipredicate problem of returning "no result":

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 }

However, this does two tests at each iteration of the loop: whether the value has been found and whether the end of the array has been reached. This latter test is what is avoided by using a sentinel value. Assuming the array can be extended by one element (without memory allocation or cleanup; this is more realistic for a linked list, as below), this can be rewritten as:

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

The test for i < len is still present, but it has been moved outside the loop, which now contains only a single test (for the value), and is guaranteed to terminate due to the sentinel value. There is a single check on termination if the sentinel value has been hit, which replaces a test for each iteration.

It is also possible to temporarily replace the last element of the array by a sentinel and handle it, especially if it is reached:

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 values

This is an example of returning null pointers and null options.

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 }