C++Guns – RoboBlog


C++ Guns: Multi-Arraylist with C++17 P0184R0 Sentinel

Filed under: Allgemein — Tags: — Thomas @ 15:08

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, every list item is a single ID. Iterate over a list results in jumping around on the array.
I don't implement the part which insert new items in the list. Iterate over the lists is much more interesting.


#include <vector>
#include <iostream>

using namespace std;

const int noIDvalue = -1;

class MultiArrayList {
    MultiArrayList() {
        // fill with some test data
        data[0] = 9;
        data[1] = 3;
        data[2] = 1;
        data[3] = 8;
        data[4] = 7;
        data[5] = noIDvalue;
        data[6] = noIDvalue;
        data[7] = noIDvalue;
        data[8] = 5;
        data[9] = 4;

        startIDs[0] = 0;
        startIDs[1] = 2;
        startIDs[2] = 6;

    std::vector<int> data;
    std::vector<int> startIDs;

int main() {
    MultiArrayList multiList;
    // print list content
    for(int nextID : multiList.startIDs) {
        cout << "List content: ";
        while(nextID != sentinelID) {
            cout << nextID << " ";
            nextID = multiList.data[nextID];
        cout << "\n";

List content: 0 9 4 7
List content: 2 1 3 8 5
List content: 6

The hand crafted while loop is very ugly. I want something with a range. e.g.

    for(size_t i=0; i < multiList.size(); ++i) {
        cout << "List content: ";
        for(const int ID : multiList.at(i)) {
            std::cout << ID << " ";
        cout << "\n";

Lets see if I can implement this with the new C++17.
We need MultiArrayList::at which simply returns a MultiArrayListRange. The range provide function begin() and end(). And we need MultiArrayListIterator which implements the iterator logic and of course MultiArrayListSentinel .

    auto MultiArrayList::at(size_t id) const {
        return MultiArrayListRange(startIDs.at(i), data);

class MultiArrayListIterator {
    MultiArrayListIterator(const int startID, const std::vector<int>& data)
        : curID(startID), data(data)


    void operator++() {
        curID = data[curID];

    int operator*() const {
        return curID;

    int curID;
    const std::vector<int>& data;

template<int Delim>
struct MultiArrayListSentinel {


template<int Delim>
bool operator!=(const MultiArrayListIterator& lhs, const MultiArrayListSentinel<Delim>) {
    return *lhs != Delim;

class MultiArrayListRange {
    MultiArrayListRange(const int startID, const std::vector<int>& data)
        : startID(startID), data(data)


    auto begin() {
        return MultiArrayListIterator(startID, data);

    auto end() {
        return MultiArrayListSentinel<noIDvalue>();

    const int startID;
    const std::vector<int>& data;

Here we go. The core idea is the different return types of begin() and end(). One returns an iterator, the other a sentinel. The new operator!=() take both and check if the current ID is a noIDvalue, e.g. -1. If so, we are at the end of the list.

The end iterator is never incremented, decremented, or dereferenced. Requiring it to be an iterator serves no practical purpose.

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.

PS: operator!= with sentinel is faster, because the right hand side is a compile time constant. It saves one assembler instruction (25%).

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress