{"id":3634,"date":"2018-08-03T15:39:52","date_gmt":"2018-08-03T14:39:52","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=3634"},"modified":"2018-08-06T15:49:58","modified_gmt":"2018-08-06T14:49:58","slug":"c-guns-sentinel-part-1-c17-p0184r0","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=3634","title":{"rendered":"C++ Guns: Multi-Arraylist with C++17 P0184R0 Sentinel"},"content":{"rendered":"

P0184R0<\/a> Differing begin and end types in range-based for. <\/p>\n

Sentinel - value to terminate a loop after it was read<\/p><\/blockquote>\n

Let me try something. A list implemented as array - Multiple lists stored in a single array.
\nThis can be helpful if the lists are very short e.g. less than 10 items.
\nFor this example, every list item is a single ID. Iterate over a list results in jumping around on the array.
\nI don't implement the part which insert new items in the list. Iterate over the lists is much more interesting.<\/p>\n

Example:<\/p>\n

\r\n#include <vector>\r\n#include <iostream>\r\n\r\nusing namespace std;\r\n\r\nconst int noIDvalue = -1;\r\n\r\nclass MultiArrayList {\r\npublic:\r\n    MultiArrayList() {\r\n        \/\/ fill with some test data\r\n        data.resize(10);\r\n        data[0] = 9;\r\n        data[1] = 3;\r\n        data[2] = 1;\r\n        data[3] = 8;\r\n        data[4] = 7;\r\n        data[5] = noIDvalue;\r\n        data[6] = noIDvalue;\r\n        data[7] = noIDvalue;\r\n        data[8] = 5;\r\n        data[9] = 4;\r\n\r\n        startIDs.resize(3);\r\n        startIDs[0] = 0;\r\n        startIDs[1] = 2;\r\n        startIDs[2] = 6;\r\n    }\r\n\r\n\r\n    std::vector<int> data;\r\n    std::vector<int> startIDs;\r\n};\r\n\r\nint main() {\r\n    MultiArrayList multiList;\r\n    \/\/ print list content\r\n    for(int nextID : multiList.startIDs) {\r\n        cout << "List content: ";\r\n        while(nextID != sentinelID) {\r\n            cout << nextID << " ";\r\n            nextID = multiList.data[nextID];\r\n        }\r\n        cout << "\\n";\r\n    }\r\n}\r\n<\/pre>\n
List content: 0 9 4 7
\nList content: 2 1 3 8 5
\nList content: 6\n<\/p><\/blockquote>\n
The hand crafted while loop is very ugly. I want something with a range. e.g.<\/p>\n
\r\n    for(size_t i=0; i < multiList.size(); ++i) {\r\n        cout << "List content: ";\r\n        for(const int ID : multiList.at(i)) {\r\n            std::cout << ID << " ";\r\n        }\r\n        cout << "\\n";\r\n    }\r\n<\/pre>\n
Lets see if I can implement this with the new C++17.
\nWe need MultiArrayList::at<\/em> which simply returns a MultiArrayListRange<\/em>. The range provide function begin()<\/em> and end()<\/em>. And we need MultiArrayListIterator<\/em> which implements the iterator logic and of course MultiArrayListSentinel<\/em> .<\/p>\n
\r\n    auto MultiArrayList::at(size_t id) const {\r\n        return MultiArrayListRange(startIDs.at(i), data);\r\n    }\r\n\r\nclass MultiArrayListIterator {\r\npublic:\r\n    MultiArrayListIterator(const int startID, const std::vector<int>& data)\r\n        : curID(startID), data(data)\r\n    {\r\n\r\n    }\r\n\r\n    void operator++() {\r\n        curID = data[curID];\r\n    }\r\n\r\n    int operator*() const {\r\n        return curID;\r\n    }\r\n\r\nprivate:\r\n    int curID;\r\n    const std::vector<int>& data;\r\n};\r\n\r\ntemplate<int Delim>\r\nstruct MultiArrayListSentinel {\r\n\r\n};\r\n\r\ntemplate<int Delim>\r\nbool operator!=(const MultiArrayListIterator& lhs, const MultiArrayListSentinel<Delim>) {\r\n    return *lhs != Delim;\r\n}\r\n\r\nclass MultiArrayListRange {\r\npublic:\r\n    MultiArrayListRange(const int startID, const std::vector<int>& data)\r\n        : startID(startID), data(data)\r\n    {\r\n\r\n    }\r\n\r\n    auto begin() {\r\n        return MultiArrayListIterator(startID, data);\r\n    }\r\n\r\n    auto end() {\r\n        return MultiArrayListSentinel<noIDvalue>();\r\n    }\r\n\r\nprivate:\r\n    const int startID;\r\n    const std::vector<int>& data;\r\n};\r\n<\/pre>\n
Here we go. The core idea is the different return types of begin()<\/em> and end()<\/em>. One returns an iterator, the other a sentinel. The new operator!=()<\/em> take both and check if the current ID is a noIDvalue<\/em>, e.g. -1. If so, we are at the end of the list. <\/p>\n
The end iterator is never incremented, decremented, or dereferenced. Requiring it to be an iterator serves no practical purpose.<\/p>\n
As always: storing references is a bad idea. But everybody knows, iterators and now ranges are short-lived temporary objects which gets invalidated, so this is okay.<\/p>\n
PS: operator!= with sentinel is faster, because the right hand side is a compile time constant. It saves one assembler instruction (25%).<\/p>\n","protected":false},"excerpt":{"rendered":"
P0184R0 Differing begin and end types in range-based for. Sentinel - value to terminate a loop after it was read Let me try something. A list implemented as array - Multiple lists stored in a single array. This can be helpful if the lists are very short e.g. less than 10 items. For this example, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-3634","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3634","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3634"}],"version-history":[{"count":8,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3634\/revisions"}],"predecessor-version":[{"id":3648,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3634\/revisions\/3648"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3634"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3634"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3634"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}