Iterator in permutation value order

Question

I have a simple struct for permutation:

struct Permutation
{
   vector<string> items; // ["val_0", "val_1", "val_2", "val_3", "val_4"]
   vector<short> permutationValue;  // Let's say value is [4, 2, 0, 1, 3]
}

I want to be able to use it in range loop, like that

for(string item: permutation){
{ 
    cout << item << endl;
}

end expected output should be:

val_4
val_2
val_0
val_1
val_3

What methods should I implement in Permutation class to achive it?

Answer 1

You will need to do a little bit of work. You need to implement your own custom iterator class, and begin() and end():

struct Permutation
{
    std::vector<std::string> items;
    std::vector<short> permutationValue;

    class iterator;

    iterator begin();
    iterator end();

};

Your iterator class will be a random access iterator:

#include <iterator>

class Permutation::iterator : public std::iterator<std::random_access_iterator_tag, std::string>
{


};

It is important to inherit from std::iterator, in order for your custom iterator to work correctly with <algorithm>.

There are several possible ways to implement the iterator. But the general idea is that your iterator will store a pointer to its permutation object, and its current index position, in its private class members:

private:
    Permutation *p;
    size_t pos;

Its operator* is obvious:

public:
    std::string &operator*() const
    {
         return p->items[p->permutationValue[pos]];
    }

You will need to implement all other iterator operators, that increment/decrement advance the random access iterator, operators ++, --, +, -, +=, -=, simply by adding or subtracting pos.

You will also need to implement all the comparison operators for your iterator class: <, >, =, !=, <=, and >=, simply by comparing pos.

These bits will be a little bit tedious, but inavoidable.

Now, all you have to do is implement begin() and end() by constructing this iterator instance, setting the initial pos to either 0, or items.size();. You're done. Now you can use range iteration.

For extra credit, you can also implement const_iterator.

In conclusion: it's going to be a little bit of work, but it's not very complicated.