8

Context:

I am trying to build a container that will behave as a wrapper around a multi-dimensional array of run time defined dimensions - in fact the underlying array is of course a 1D array of the total size. The main part is that operator [] returns a wrapper on the sub array.

As containers need iterators, I am currently implementing iterators on that container, both Container::iterator and Container::const_iterator. I try hard to mimic standard container iterators, and my implementation respects almost all requirements for a random access iterator except for:

Forward iterators [forward.iterators]

...
6 If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

The reason for not respecting it, is that operator * has to return a reference to a sub-container. So my implementation is a stashing iterator that contains a sub-container member that moves with the iterator, and operator * returns a reference to this member object

Over simplified implementation:

template <class T>
class SubArray {
    T *arr;
    size_t *sizes;
    size rowsize;
public:
    ...
    Iterator<T> begin() {
        return Iterator<T>(operator[](0));
    }
    ...
};

class Iterator<T> {
   SubArray elt;
public:
    Iterator(const SubArray<T>& pos): elt(pos) {}
    ...
    SubArray<T>& operator *() {
        return elt;
    ...
};

According to cppreference (and to source of different implementations) std::filesystem::path::iterator is also a stashing iterator.

Question

The iterator_category member of an iterator is supposed to help other classes to identify the type of an iterator from input iterator to random access. What should be the iterator_category of my stashing iterator, that fulfills almost all requirements for a random access iterator but fails for one point of forward iterator? Note: this is enough to make std::reverse_iterator not usable on it.

Remark:

I can confirm that std::filesystem::path::iterator contains for Clang implementation:

typedef bidirectional_iterator_tag iterator_category;

but also a marker to prevent std::reverve_iterator to try to use it

References:

  • full source for my container class on Code Review
  • question about std::reverse_iterator on a stashing container on SO
  • std::reverse_iterator on cppreference (see the note above the example code)
Community
  • 1
  • 1
Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
  • 2
    If the iterator doesn't meet the requirements to be a forward iterator, then it is, at most, an input iterator or an output iterator. – Pete Becker Jun 18 '18 at 12:44
  • Why do you have to return a reference to the sub array? Can't you just return a reference to the element the iterator points to? – NathanOliver Jun 18 '18 at 12:46
  • Wait... what happens if you try and modify `*it`? `auto arr = SubArray{/*2D array*/}; auto subarr = SubArray{/*1D array*/}; auto it = arr.begin(); *it = subarr;` – YSC Jun 18 '18 at 12:46
  • @YSC: I have never tested that! The default assignment operator for `SubArray` should replace `it.elt`, making `it` point to `subarr`. I think that I shall have to document this, at least as *don't* or *beware*... – Serge Ballesta Jun 18 '18 at 13:01
  • I'm not sure whether it is a bug of libc++. libstdc++ indeed [implements std::filesystem::path::iterator as a forward iterator](https://wandbox.org/permlink/7KTECZ2YbbYXDLVk), so it is reasonable to define its category as `bidirectional_iterator_tag`. However, libc++ [does not implement it as a forward iterator](https://wandbox.org/permlink/2QOFVyyyRTPE9o3C). – xskxzr Jun 18 '18 at 15:06

0 Answers0