Inherit all functions from user-defined iterator in reverse_iterator

Question

I am writing a JSON class for C++11, see http://github.com/nlohmann/json. My central data structure is a class wrapping the JSON value types (null, array, object, string, bool, number) in a union and offering it in via a nice C++ interface. As arrays (implemented via std::vector) and objects (std::map) come with their own iterators, I implemented a "wrapper" iterator which delegates calls to operator++ or operator-> to the respective member variables. Furthermore, I implemented two additional functions std::string key() to access keys of a JSON object and reference value() as an alias to operator*().

So far, so good (see https://github.com/nlohmann/json/blob/master/src/json.hpp for the complete source code)...

Then I wanted to implement reverse_iterator and const_reverse_iterator. And here the problems begin.

• If I realize them via using reverse_iterator = std::reverse_iterator<iterator>; and using const_reverse_iterator = std::reverse_iterator<const_iterator>;, everything is fine, but the functions key() and value() are not available with reverse_iterator or const_reverse_iterator objects.
• If I implement my own class reverse_iterator like class reverse_iterator : public std::reverse_iterator<typename basic_json::iterator>, I need to implement the whole class again. It is not sufficient to give an implementation for key() and value(), but also for operator++() and all the other stuff which I hope to have gotten for free using the std::reverse_iterator adaptor.

I spent quite some time searching for answers, but all references I found either scratching the surface of incomplete toy examples or come to the conclusion that iterators are hard work and one should move to Boost...

So here are my questions:

1. How can I create a reverse_iterator from my customized class iterator so that it inherits as much functions as possible?
2. If inheriting behavior beyond the standard stuff does not work automatically, how can I write a reverse_iterator without repeating myself completely?

Any help is greatly appreciated!

Answer 1

Unfortunately, I did not receive an answer, so here is what I did. Maybe an ugly solution provokes someone to post something nicer :-)

Background

So the first thing I learned is that std::reverse_iterator does nothing more than to encapsulate a "normal" iterator (called current, accessible via base()) and to establish the relationship of the reverse iterator being "one element more to the left" than the "normal" iterator.

(image from cppreference.com)

Generic solution

As long as the "normal" iterator has the standard interface and does not use any additional functions, the lines

using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

are sufficient to automagically convert your own iterator class into a reverse iterator.

And with the member functions

reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); }
const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); }

reverse iteration is possible, for instance code like

for (my_container::reverse_iterator rit = c.rbegin(); rit != c.rend(); ++it)
{
   // rit will iterator container c in reverse order
}

works.

Adding more functionality to iterators

As I wrote in the question, I extended the iterator class with two additional members, key() and value(). The former allows quick access to the key of a JSON object during iteration. The latter is an alias to write it.value() rather than *it. Unfortunately, the above approach does not inherit these function to reverse_iterator.

To enrich the user-defined reverse iterators, we need to inherit from std::reverse_iterator<iterator> and delegate calls to the base iterator. Unfortunately, I found no other approach than to do this manually. For the mentioned functions, this looks as follows:

class reverse_iterator : public std::reverse_iterator<iterator>
{
  ...

  std::string key() const
  {
      auto it = --this->base();
      return it.key();
  }

  reference value() const
  {
      auto it = --this->base();
      return it.operator * ();
  }  
}

The most tricky part is that you need to implement the "off-by-one" relationship manually:

1. Retrieve the base iterator via base().
2. Decrement it to point to the "right" (left, actually...) element.
3. Call the desired function.

And with that, we're nearly done. Nearly, because of the ... in the code above. What is left to do is to delegate all other calls to functions like operator++ to the base class. I found now way to let someone else to this boring delegation.

So the class contains code like

using base_iterator = std::reverse_iterator<iterator>;

reverse_iterator operator++(int)
{
    return base_iterator::operator++(1);
}

reverse_iterator& operator++()
{
    base_iterator::operator++();
    return *this;
}

(Note the definition of base_iterator.)

That's it. We now have user-defined reverse iterators which allow us to code

for (my_container::reverse_iterator rit = c.rbegin(); rit != c.rend(); ++it)
{
   std::cout << rit.key() << '\n';
}

Cleaning up

In a discussion on Github, gregmarr proposed to combine the reverse_iterator and the const_reverse_iterator classes into a single template class like

template<typename Base>
class json_reverse_iterator : public std::reverse_iterator<Base>
{
  public:
    /// shortcut to the reverse iterator adaptor
    using base_iterator = std::reverse_iterator<Base>;
    /// the reference type for the pointed-to element
    using reference = typename Base::reference;

    /// create reverse iterator from iterator
    json_reverse_iterator(const typename base_iterator::iterator_type& it)
        : base_iterator(it) {}

    /// create reverse iterator from base class
    json_reverse_iterator(const base_iterator& it) : base_iterator(it) {}

...
}

This allows to write

using reverse_iterator = json_reverse_iterator<iterator>;
using const_reverse_iterator = json_reverse_iterator<const_iterator>;

and to be happy.

Full example

See here for the complete code.

I'd still like to see a solution that avoids repeating most functionality, but this one is good enough for me. And as I haven't found anything better in quite a while, I decided to share it.