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