How to implement operator-> for an iterator that constructs its values on-demand?

Question

I have a C++ class that acts like a container: it has size() and operator[] member functions. The values stored "in" the container are std::tuple objects. However, the container doesn't actually hold the tuples in memory; instead, it constructs them on-demand based on underlying data stored in a different form.

std::tuple<int, int, int>
MyContainer::operator[](std::size_t n) const {
    // Example: draw corresponding elements from parallel arrays
    return { underlying_data_a[n], underlying_data_b[n], underlying_data_c[n] };
}

Hence, the return type of operator[] is a temporary object, not a reference. (This means it's not an lvalue, so the container is read-only; that's OK.)

Now I'm writing an iterator class that can be used to traverse the tuples in this container. I'd like to model RandomAccessIterator, which depends on InputIterator, but InputIterator requires support for the expression i->m (where i is an iterator instance), and as far as I can tell, an operator-> function is required to return a pointer.

Naturally, I can't return a pointer to a temporary tuple that's constructed on-demand. One possibility that comes to mind is to put a tuple instance into the iterator as a member variable, and use it to store a copy of whichever value the iterator is currently positioned on:

class Iterator {
private:
    MyContainer *container;
    std::size_t current_index;

    // Copy of (*container)[current_index]
    std::tuple<int, int, int> current_value;
    // ...
};

However, updating the stored value will require the iterator to check whether its current index is less than the container's size, so that a past-the-end iterator doesn't cause undefined behavior by accessing past the end of the underlying arrays. That adds (a small amount of) runtime overhead — not enough to make the solution impractical, of course, but it feels a little inelegant. The iterator shouldn't really need to store anything but a pointer to the container it's iterating and the current position within it.

Is there a clean, well-established way to support operator-> for iterator types that construct their values on-demand? How would other developers do this sort of thing?

(Note that I don't really need to support operator-> at all — I'm implementing the iterator mainly so that the container can be traversed with a C++11 "range for" loop, and std::tuple doesn't have any members that one would typically want to access via -> anyway. But I'd like to model the iterator concepts properly nonetheless; it feels like I'm cutting corners otherwise. Or should I just not bother?)

operator-> doesn't have to return a pointer. It just has to return something on which * can be applied. — Kerrek SB
– Kerrek SB, Commented Dec 20, 2014 at 18:00
Hmm, so I could return a "fake pointer" that holds a value and returns that value when "dereferenced"? I'm not sure whether that's more or less awkward than storing the value in the iterator itself. :-) But at least (with inlining) there'd be zero run-time overhead. — Wyzard
– Wyzard, Commented Dec 20, 2014 at 18:03
In any case, to model ForwardIterator you must meet this requirement: "If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object." That generally means iterators returning a proxy or containing the value within themselves can only be InputIterators — Jonathan Wakely
– Jonathan Wakely, Commented Dec 20, 2014 at 18:07
@KerrekSB, looks like the returned value actually has to support ->, not *. A fake-pointer class with its own operator-> (that returns a real pointer) works, but implementing just operator*() in the fake pointer doesn't work. — Wyzard
– Wyzard, Commented Dec 20, 2014 at 18:42
[over.ref]/1: "An expression x->m is interpreted as (x.operator->())->m for a class object x of type T if T::operator->() exists and if the operator is selected as the best match function by the overload resolution mechanism (13.3)." — Columbo
– Columbo, Commented Dec 20, 2014 at 18:44

Yakk - Adam Nevraumont · Accepted Answer · 2014-12-20 19:57:46Z

3

template<class T>
struct pseudo_ptr {
  T t;
  T operator*()&&{return t;}
  T* operator->(){ return &t; }
};

then

struct bar { int x,y; };
struct bar_iterator:std::iterator< blah, blah >{
  // ...
  pseudo_ptr<bar> operator->() const { return {**this}; }
  // ...
};

This relies on how -> works.

ptr->b for pointer ptr is simply (*ptr).b.

Otherwise it is defined as (ptr.operator->())->b. This evaluates recursively if operator-> does not return a pointer.

The pseudo_ptr<T> above gives you a wrapper around a copy of T.

Note, however, that lifetime extension doesn't really work. The result is fragile.

answered Dec 20, 2014 at 19:57

Yakk - Adam Nevraumont

280k31 gold badges367 silver badges585 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

kec · Accepted Answer · 2014-12-20 19:05:52Z

2

Here's an example relying on the fact that operator-> is applied repeatedly until a pointer is returned. We make Iterator::operator-> return the Contained object as a temporary. This causes the compiler to reapply operator->. We then make Contained::operator-> simply return a pointer to itself. Note that if we don't want to put operator-> in the Contained on-the-fly object, we can wrap it in a helper object that returns a pointer to the internal Contained object.

#include <cstddef>
#include <iostream>

class Contained {
    public:
        Contained(int a_, int b_) : a(a_), b(b_) {}
        const Contained *operator->() {
            return this;
        }
        const int a, b;
};

class MyContainer {
    public:
        class Iterator {
                friend class MyContainer;
            public:
                friend bool operator!=(const Iterator &it1, const Iterator &it2) {
                    return it1.current_index != it2.current_index;
                }
            private:
                Iterator(const MyContainer *c, std::size_t ind) : container(c), current_index(ind) {}
            public:
                Iterator &operator++() {
                    ++current_index;
                    return *this;
                }
                // -> is reapplied, since this returns a non-pointer.
                Contained operator->() {
                    return Contained(container->underlying_data_a[current_index], container->underlying_data_b[current_index]);
                }
                Contained operator*() {
                    return Contained(container->underlying_data_a[current_index], container->underlying_data_b[current_index]);
                }
            private:
                const MyContainer *const container;
                std::size_t current_index;
        };
    public:
        MyContainer() {
            for (int i = 0; i < 10; i++) {
                underlying_data_a[i] = underlying_data_b[i] = i;
            }
        }
        Iterator begin() const {
            return Iterator(this, 0);
        }
        Iterator end() const {
            return Iterator(this, 10);
        }
    private:
        int underlying_data_a[10];
        int underlying_data_b[10];
};

int
main() {
    MyContainer c;

    for (const auto &e : c) {
        std::cout << e.a << ", " << e.b << std::endl;
    }
}

edited Dec 20, 2014 at 19:05

answered Dec 20, 2014 at 18:58

kec

2,15912 silver badges18 bronze badges

5 Comments

user743382 Over a year ago

Of course, be careful: something like const int &a = it->a; would normally work, but won't here, as the temporary object will already be destroyed by the time a gets used.

Wyzard Over a year ago

Any particular reason for having Contained hold the individual values directly, as opposed to holding a std::tuple (and returning its address from operator->)?

kec Over a year ago

@Wyzard: You could use a tuple, but then you'd have to wrap it, since std::tuple doesn't have -> overloaded for it.

Wyzard Over a year ago

But if the tuple is a member of Contained , you could just return the address of that member variable. Contained is the wrapper. (Or am i missing something?)

kec Over a year ago

@Wyzard: Yes, in which case Contained is the wrapper, though of course you would probably rename it.

Collectives™ on Stack Overflow

How to implement operator-> for an iterator that constructs its values on-demand?

2 Answers 2

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related