C++Guns – RoboBlog

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.

Example:

#include <vector>
#include <iostream>

using namespace std;

const int noIDvalue = -1;

class MultiArrayList {
public:
    MultiArrayList() {
        // fill with some test data
        data.resize(10);
        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.resize(3);
        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 {
public:
    MultiArrayListIterator(const int startID, const std::vector<int>& data)
        : curID(startID), data(data)
    {

    }

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

    int operator*() const {
        return curID;
    }

private:
    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 {
public:
    MultiArrayListRange(const int startID, const std::vector<int>& data)
        : startID(startID), data(data)
    {

    }

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

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

private:
    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%).