{"id":6370,"date":"2022-05-31T19:36:30","date_gmt":"2022-05-31T19:36:30","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/sentinels-and-concepts\/"},"modified":"2023-09-27T16:56:59","modified_gmt":"2023-09-27T16:56:59","slug":"sentinels-and-concepts","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/sentinels-and-concepts\/","title":{"rendered":"Sentinels and Concepts with Ranges Algorithms"},"content":{"rendered":"

The ranges library in C++20 supports sentinels. Sentinels stand for the end of a range and can be regarded as generalized end iterators.<\/p>\n

<\/p>\n

\"\"<\/p>\n

A range provided by a begin iterator and an end sentinel specifies a group of items you can iterate over. The containers of the STL are ranges because their end iterator marks the end of the range.<\/p>\n

Sentinel<\/h2>\n
\n
The following example uses sentinels for a C-string and a std::vector<int><\/code>.<\/div>\n
<\/div>\n

<\/p>\n

\n
\/\/ sentinel.cpp<\/span>\n\n#include <iostream><\/span>\n#include <algorithm><\/span>\n#include <compare><\/span>\n#include <vector><\/span>\n\nstruct<\/span> Space {                        \/\/ (1)<\/span><\/em>\nbool<\/span> operator<\/span>==<\/span> (auto<\/span> pos) const<\/span> {\n        return<\/span> *<\/span>pos ==<\/span> ' '<\/span>; \n    }\n};\n\nstruct<\/span> NegativeNumber {               \/\/ (2)<\/span><\/em>\n    bool<\/span> operator<\/span>==<\/span> (auto<\/span> num) const<\/span> {\n        return<\/span> *<\/span>num <<\/span> 0<\/span>;   \n    }\n};\n\nstruct<\/span> Sum {                          \/\/ (7)<\/span><\/em>\n    void<\/span> operator<\/span>()(auto<\/span> n) { sum +=<\/span> n; }\n    int<\/span> sum{0<\/span>};\n};\n\nint<\/span> main<\/span>() {\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    const<\/span> char<\/span>*<\/span> rainerGrimm =<\/span> \"Rainer Grimm\"<\/span>;\n   \n    std::<\/span>ranges::<\/span>for_each(rainerGrimm, Space{}, [] (char<\/span> c) { std::<\/span>cout <<<\/span> c; });  \/\/ (3)<\/span>\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n    for<\/span> (auto<\/span> c:<\/span> std::<\/span>ranges::<\/span>subrange{rainerGrimm, Space{}}) std::<\/span>cout <<<\/span> c;      \/\/ (4)<\/span>\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>ranges::<\/span>subrange rainer{rainerGrimm, Space{}};                            \/\/ (5)<\/span>\n    std::<\/span>ranges::<\/span>for_each(rainer, [] (char<\/span> c) { std::<\/span>cout <<<\/span> c <<<\/span> ' '<\/span>; });         \/\/ (6)<\/span>\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n    for<\/span> (auto<\/span> c:<\/span> rainer) std::<\/span>cout <<<\/span> c <<<\/span> ' '<\/span>;\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n  \n\n    std::<\/span>cout <<<\/span> \"<\/span>\\n<\/span>\"<\/span>;\n\n\n    std::<\/span>vector<<\/span>int<\/span>><\/span> myVec{5<\/span>, 10<\/span>, 33<\/span>, -<\/span>5<\/span>, 10<\/span>};\n\n    for<\/span> (auto<\/span> v:<\/span> myVec) std::<\/span>cout <<<\/span> v <<<\/span> \" \"<\/span>;\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    auto<\/span> [tmp1, sum] =<\/span> std::<\/span>ranges::<\/span>for_each(myVec, Sum{});\n    std::<\/span>cout <<<\/span> \"Sum: \"<\/span> <<<\/span> sum.sum <<<\/span> '\\n'<\/span>;                                   \/\/ (8)<\/span>\n<\/em>\n    auto<\/span> [tmp2, sum2] =<\/span> std::<\/span>ranges::<\/span>for_each(std::<\/span>begin(myVec), NegativeNumber{}, \n                                              Sum{} );            \n    std::<\/span>cout <<<\/span> \"Sum: \"<\/span> <<<\/span> sum2.sum <<<\/span> '\\n'<\/span>;                                   \/\/ (9)<\/span><\/em>\n\n    std::<\/span>ranges::<\/span>transform(std::<\/span>begin(myVec), NegativeNumber{},                 \/\/ (10)<\/span><\/em>\n                           std::<\/span>begin(myVec), [](auto<\/span> num) { return<\/span> num *<\/span> num; });\n    std::<\/span>ranges::<\/span>for_each(std::<\/span>begin(myVec), NegativeNumber{},                  \/\/ (11)<\/span><\/em>\n                          [](int<\/span> num) { std::<\/span>cout <<<\/span> num <<<\/span> \" \"<\/span>; });\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n    for<\/span> (auto<\/span> v:<\/span> std::<\/span>ranges::<\/span>subrange{ std::<\/span>begin(myVec), NegativeNumber{}}) { \/\/ (12)<\/span><\/em>\n        std::<\/span>cout <<<\/span> v <<<\/span> \" \"<\/span>;\n    }\n\n    std::<\/span>cout <<<\/span> \"<\/span>\\n\\n<\/span>\"<\/span>;\n    \n}\n<\/pre>\n<\/div>\n<\/div>\n
\n
The program defines two sentinels: Space (line 1) and NegativeNumber<\/code> (line 2). Both define the equal operator. Thanks to the <compare><\/code> header, the compiler auto-generates the non-equal operator. The non-equal operator is required when using algorithms such as std::ranges_for_each<\/code> or std::ranges::transform<\/code> with a sentinel. Let me start with the sentinel Space<\/code>.<\/div>\n
Line (3) applies the sentinel Space{}<\/code> directly onto the string “rainerGrimm<\/code>“. Creating a std::ranges::subrange<\/code> (line 4) allows it to use the sentinel in a range-based for-loop. You can also define a std::ranges::subrange<\/code> and use it directly in the algorithm std::ranges::for_each (line 5) or in a range-based for-loop (line 6).<\/div>\n
My second example uses a std::vector<int><\/code>, filled with the values {5, 10, 33, -5, 10}<\/code>. The sentinel NegativeNumber<\/code> checks if a number is negative. First, I sum up all values using the function object Sum<\/code> (line 7). std::ranges::for_each<\/code> returns a pair (it, func)<\/code>.\u00a0 it<\/code> is the successor of the sentinel and func<\/code> the function object applied to the range. Thanks to the structured binding, I can directly define the variables sum <\/code>and sum2 <\/code>and display their values (lines 8 and 9). std::ranges::for_each<\/code> uses the sentinel NegativeNumber<\/code>. Consequently, sum2<\/code> has the sum up to the sentinel. The call std::ranges::transform<\/code> (line 10) transforms each element to its square: [](auto num){ return num * num}<\/code>. The transformation stops with the sentinel NegativeNumber.<\/code> Line 11 and line 12 display the transformed values.<\/div>\n
Finally, here is the output of the program.<\/div>\n
\"sentinel\"<\/div>\n<\/div>\n
You may ask yourself, should I use a classical algorithm of the STL or the ranges pendant on a container? Let me answer this question by comparing both.<\/p>\n
std<\/code> Algorithms versus std::ranges<\/code> Algorithms<\/h2>\n
Before I dive into the details in my comparison, I want to provide the big picture:<\/p>\n
\"AlgorithmsComparison\"<\/p>\n
Range does not support numeric<\/h3>\n
The ranges does support the functions of the functional<\/code><\/a>, and the algorithm <\/code><\/a>header, but the function of the numeric<\/code> <\/a>header.\u00a0 The\u00a0numeric<\/code> <\/a>header includes <\/code>mathematical functions such as\u00a0 std::gcd, std::midpoint, std::iota,<\/code> or std::accumulate.<\/code><\/p>\n
Let me write about more interesting differences.<\/p>\n
Concept support<\/h3>\n
The std::ranges<\/code> algorithms are the poster child for concepts.<\/p>\n
\n
Let’s start with a comparison of the classical std::sort<\/code> and the new std::ranges::sort<\/code>. std::sort<\/code> and std::ranges::sort<\/code> require a random-access iterator that can access each range element in constant time. Here are the two relevant overloads for std::sort<\/code> and std::ranges::sort<\/code>.<\/div>\n
<\/div>\n