{"id":8541,"date":"2023-10-30T09:15:20","date_gmt":"2023-10-30T09:15:20","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=8541"},"modified":"2023-10-30T09:15:20","modified_gmt":"2023-10-30T09:15:20","slug":"the-ranges-library-in-c20-design-choices","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/the-ranges-library-in-c20-design-choices\/","title":{"rendered":"The Ranges Library in C++20: Design Choices"},"content":{"rendered":"\n

Thanks to the ranges library, working with the Standard Template Library (STL) is much more comfortable and powerful. First of all, the algorithms of the ranges library are lazy, can work directly on the container, and can be composed. Additionally, the ranges library made a few unique design choices, you must know.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Before I dive deep into the ranges library in C++20, I want to recap in a few sentences the three main features of the ranges: The algorithms of the ranges can directly operate on the container, evaluate their arguments lazily, and can be composed.<\/p>\n\n\n\n

Direct on the Container<\/h2>\n\n\n\n

The ranges library enables a container such as std::ranges::sort<\/code> can directly operate on the container:<\/p>\n\n\n\n

\/\/ sortRanges.cpp<\/span>\n\n#include <algorithm><\/span>\n#include <iostream><\/span>\n#include <vector><\/span>\n\nint<\/span> main<\/span>()  {\n\n    std::<\/span>vector<<\/span>int<\/span>><\/span> myVec{-<\/span>3<\/span>, 5<\/span>, 0<\/span>, 7<\/span>, -<\/span>4<\/span>};\n    std::<\/span>ranges::<\/span>sort(myVec);                  \/\/ (1)<\/span>\n    for<\/span> (auto<\/span> v:<\/span> myVec) std::<\/span>cout <<<\/span> v <<<\/span> " "<\/span>; \/\/ -4, -3, 0, 5, 7<\/span>\n\n}\n<\/pre><\/div>\n\n\n\n
On the contrary, the classic std::sort operates on a range defined by two iterators: std:sort(myVec.begin(), myVec.end()<\/code>).<\/p>\n\n\n\n
The ranges algorithms are lazy and can be composed.<\/p>\n\n\n\n
Lazy Evaluation and Function Composition<\/h2>\n\n\n\n
The following program primesLazy.cpp<\/code> applies both features. It creates the first ten prime numbers, starting with one million.<\/p>\n\n\n\n
\/\/ primesLazy.cpp<\/span>\n\n#include <iostream><\/span>\n#include <ranges><\/span>\n\n\nbool<\/span> isPrime<\/span>(int<\/span> i) {\n    for<\/span> (int<\/span> j=<\/span>2<\/span>; j*<\/span>j <=<\/span> i; ++<\/span>j){\n        if<\/span> (i %<\/span> j ==<\/span> 0<\/span>) return<\/span> false<\/span>;\n    }\n    return<\/span> true<\/span>;\n}\n\nint<\/span> main<\/span>() {\n                                        \n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n                                         \n    auto<\/span> odd =<\/span> [](int<\/span> i){ return<\/span> i %<\/span> 2<\/span> ==<\/span> 1<\/span>; };\n\n    for<\/span> (int<\/span> i:<\/span> std::<\/span>views::<\/span>iota(1<\/span>'<\/span>000<\/span>'<\/span>000<\/span>) |<\/span> std::<\/span>views::<\/span>filter(odd) \n                                            |<\/span> std::<\/span>views::<\/span>filter(isPrime) \n                                            |<\/span> std::<\/span>views::<\/span>take(10<\/span>)) {\n        std::<\/span>cout <<<\/span> i <<<\/span> " "<\/span>;  \n    }\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre><\/div>\n\n\n\n
You have to read the function composition from left to right: I create an infinite data stream starting with 1\u2019000\u2019000 (std::views::iota(1'000'000)<\/code>) and apply two filters. Each filter needs a predicate. The first filter let odd elements pass (std::views::filter(odd)<\/code>), and the second filter lets the prime numbers pass (std::views::filter(isPrime)<\/code>). To end the infinite data stream, I stop after ten numbers (std::views::take(10)<\/code>).  Finally, here are the first ten prime numbers starting with one million.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
You may ask: Who starts the processing of this data pipeline? Now, it goes from right to left. The data sink (std::views::take(10)<\/code>) want to have the next value and ask its predecessor. This request continues until the range-based for-loop produces the next value. The range-based for-loop can produce an infinite data stream, but it only produces values on request. This is lazy evaluation. <\/p>\n\n\n\n
This was my short recap. When you want to read more about the ranges library, including sentinels, projection, and concepts,  read my previous posts:<\/p>\n\n\n\n
    \n
  1. The Ranges Library<\/a><\/li>\n\n\n\n
  2. Functional Pattern with the Ranges Library<\/a><\/li>\n\n\n\n
  3. The Ranges Library in C++20: More Details<\/a><\/li>\n\n\n\n
  4. Projections with Ranges<\/a><\/li>\n\n\n\n
  5. Sentinels and Concepts with Ranges Algorithms<\/a><\/li>\n\n\n\n
  6. Improved Iterators with Ranges<\/a><\/li>\n\n\n\n
  7. Pythonic with the Ranges Library<\/a><\/li>\n\n\n\n
  8. Pythons range Function, the Second<\/a><\/li>\n\n\n\n
  9. Pythons map Function<\/a><\/li>\n<\/ol>\n\n\n\n
    Now, let me write about something new.<\/p>\n\n\n\n
    Design Choices<\/h2>\n\n\n\n
    For efficiency reasons, the ranges library has some unique design choices. It’s important to know and follow theses.<\/p>\n\n\n\n
    When you study the begin <\/code>member function of std::ranges::filter_view<\/code>, you find code equivalent to the following one:<\/p>\n\n\n\n
    if<\/span> constexpr (!<\/span>ranges::<\/span>forward_range<<\/span>V><\/span>)\n    return<\/span> \/* iterator *\/<\/span>{*<\/span>this<\/span>, ranges::<\/span>find_if(base_, std::<\/span>ref(*<\/span>pred_))};\nelse<\/span>\n{\n    if<\/span> (!<\/span>begin_.has_value())\n        begin_ =<\/span> ranges::<\/span>find_if(base_, std::<\/span>ref(*<\/span>pred_)); \/\/ caching<\/span>\n    return<\/span> \/* iterator *\/<\/span>{*<\/span>this<\/span>, begin_.value())};\n}\n<\/pre><\/div>\n\n\n\n
    Let’s analyze the nested if <\/code>clause. First, the compiler checks if begin_.has_value() <\/code>is true<\/code>. If not, it determines begin_<\/code>. This means that this member function caches the result within the std::ranges::filter_view<\/code> object for use on subsequent calls. This caching has interesting consequences. Let me exemplify this with a code snippet.<\/p>\n\n\n\n
    \/\/ cachingRanges.cpp<\/span>\n\n#include <numeric><\/span>\n#include <iostream><\/span>\n#include <ranges><\/span>\n#include <vector><\/span>\n \nint<\/span> main<\/span>() {\n\n    std::<\/span>vector<<\/span>int<\/span>><\/span> vec(1<\/span>'<\/span>000<\/span>'<\/span>000<\/span>);\n    std::<\/span>iota(vec.begin(), vec.end(), 0<\/span>);\n\n    for<\/span> (int<\/span> i:<\/span> vec |<\/span> std::<\/span>views::<\/span>filter([](auto<\/span> v) { return<\/span> v ><\/span> 1000<\/span>; }) \n                    |<\/span> std::<\/span>views::<\/span>take(5<\/span>)) {\n                        std::<\/span>cout <<<\/span> i <<<\/span> " "<\/span>;  \/\/ 1001 1002 1003 1004 1005<\/span>\n                    }\n    \n}\n<\/pre><\/div>\n\n\n\n
    The first call of std::views::filter([](auto v) { return v > 1000; })<\/code> determines the begin iterator and reuses it in subsequent calls. The benefit of this caching is obvious. Many subsequent iterations of the pipeline are spared. But there are also severe drawbacks: cache issues and constness issues.<\/p>\n\n\n\n
    Cache<\/h3>\n\n\n\n
    Here are the two important cache rules for ranges:<\/p>\n\n\n\n
      \n
    • Don’t use a view on modified ranges.<\/li>\n\n\n\n
    • Don’t copy a view.<\/li>\n<\/ul>\n\n\n\n
      Let me play with the previous program cachingRanges.cpp<\/code> and break both rules:<\/p>\n\n\n\n
      \/\/ cachingIssuesRanges.cpp<\/span>\n\n#include <concepts><\/span>\n#include <forward_list><\/span>\n#include <iostream><\/span>\n#include <numeric><\/span>\n#include <ranges><\/span>\n#include <vector><\/span>\n\nvoid<\/span> printElements<\/span>(std::<\/span>ranges::<\/span>input_range auto<\/span>&&<\/span> rang) {\n    for<\/span> (int<\/span> i:<\/span> rang) {\n        std::<\/span>cout <<<\/span> i <<<\/span> " "<\/span>;  \n    }\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n}\n \nint<\/span> main<\/span>() {\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>vector<<\/span>int<\/span>><\/span> vec{-<\/span>3<\/span>, 10<\/span>, 4<\/span>, -<\/span>7<\/span>, 9<\/span>, 0<\/span>, 5<\/span>, -<\/span>5<\/span>};                            \/\/ (1)<\/span>\n    std::<\/span>forward_list<<\/span>int<\/span>><\/span> forL{-<\/span>3<\/span>, 10<\/span>, 4<\/span>, -<\/span>7<\/span>, 9<\/span>, 0<\/span>, 5<\/span>, -<\/span>5<\/span>};                     \/\/ (2)<\/span>\n\n    auto<\/span> first5Vector =<\/span> vec |<\/span> std::<\/span>views::<\/span>filter([](auto<\/span> v) { return<\/span> v ><\/span> 0<\/span>; })   \/\/ (3)<\/span>\n                            |<\/span> std::<\/span>views::<\/span>take(5<\/span>);\n\n    auto<\/span> first5ForList =<\/span> forL |<\/span> std::<\/span>views::<\/span>filter([](auto<\/span> v) { return<\/span> v ><\/span> 0<\/span>; }) \/\/ (4) <\/span>\n                              |<\/span> std::<\/span>views::<\/span>take(5<\/span>);            \n\n    printElements(first5Vector);           \/\/ 10 4 9 5                           \/\/ (5)<\/span>\n    printElements(first5ForList);          \/\/ 10 4 9 5                           \/\/ (6)<\/span>\n    \n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    vec.insert(vec.begin(), 10<\/span>);\n    forL.insert_after(forL.before_begin(), 10<\/span>);\n\n\n    printElements(first5Vector);           \/\/ -3 10 4 9 5<\/span>\n    printElements(first5ForList);          \/\/ 10 4 9 5<\/span>\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    auto<\/span> first5VectorCopy{first5Vector};                                        \/\/ (7)<\/span>\n    auto<\/span> first5ForListCopy{first5ForList};                                      \/\/ (8)<\/span>\n\n    printElements(first5VectorCopy);       \/\/ -3 10 4 9 5<\/span>\n    printElements(first5ForListCopy);      \/\/ 10 10 4 9 5<\/span>\n    \n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre><\/div>\n\n\n\n
      To make it easier to follow the problem, I wrote the output directly in the source code. The program does the following steps with a std::vector <\/code>and a std::forward_list<\/code>. First, both containers are initialized with the initializer list {-3, 10, 4, -7, 9, 0, 5, -5<\/code>} (lines 1 and 2). Then, I create two views (lines 3 and 4). Both views first5Vector<\/code> and first5ForList<\/code> consist of the first 5 elements greater than 0. Lines (5) and (6) display the corresponding values.<\/p>\n\n\n\n
      Now, I break the first rule: “Don’t use a view on modified ranges.” I insert 10<\/code> at the beginning of both containers. Afterward, first5Vector<\/code> displays the -3<\/code> and first5ForList<\/code> ignores the added 10<\/code>.  After the break of the second rule, “Don’t copy a view.” in lines (7) and (8), the cache of first5ForListCopy<\/code> is invalidated. first5VectorCopy<\/code> still shows the wrong numbers. Finally, here is the output of the program.<\/p>\n\n\n\n
      \"\"<\/figure>\n\n\n\n
      Here is a simple rule of thumb: Use views directly after you have defined them.<\/strong><\/p>\n\n\n\n
      You may have noticed that the function printElements<\/code> takes it arguments by universal reference, aka forwarding reference.<\/p>\n\n\n\n
      What’s next?<\/h2>\n\n\n\n
       Let me write in my next post, why a function should take an arbitrary view by universal reference.<\/p>\n\n\n\n
      Here is a Note on my Behalf<\/h2>\n\n\n\n
      I am sorry to inform you that I have ALS, a very serious progressive nerve condition. Therefore, I am unsure how long I can continue this blog. Currently, I can only travel to trainings or conferences with the help of my wife. We (my family and I) have decided to deal aggressively with this challenge. Therefore, it was important for me to let you, my loyal readers, in on my illness.<\/p>\n\n\n\n
      Additionally, if you know anything about a clinical trial or some new treatment, please write me an e-mail. In Germany, the only medicament is Riluzol.<\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      Modernes C++<\/p>\n\n\n\n
      \"\"<\/figure>\n","protected":false},"excerpt":{"rendered":"
      Thanks to the ranges library, working with the Standard Template Library (STL) is much more comfortable and powerful. First of all, the algorithms of the ranges library are lazy, can work directly on the container, and can be composed. Additionally, the ranges library made a few unique design choices, you must know. Before I dive […]<\/p>\n","protected":false},"author":21,"featured_media":8543,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[375],"tags":[413],"class_list":["post-8541","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-20","tag-ranges"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8541","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=8541"}],"version-history":[{"count":19,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8541\/revisions"}],"predecessor-version":[{"id":8582,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8541\/revisions\/8582"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/8543"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=8541"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=8541"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=8541"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}