The Erased Iterator

C++ operators can get nasty pretty quickly. One of their many vexing quirks is how, despite there being a relatively deep inheritance hierarchy of the manifold different iterator types (with the legendary input_or_output_iterator root being a favorite of mine) there isn’t actually any type erased iterator. Which is to say: much like std::any or std::function store their precious data in their tiny little hearts while we only get see the external interface.

The idea is quite simple, but the implementation turned out not to be. I’m not entirely sure if my current implementation is optimal, correct, but it is definitely not elegant.

The general idea is to first classify iterators based on their capabilities, namely: destructibility, copyability, comparability with ==, <, >, being dereferentiable (all should be but hey), incrementability, decrementability, distance (ie. {ptr - ptr} -> ptrdiff_t or whatever) and being able to it += diff. With these we can build the remaining operations.

Thus, we define a type struct iter_capability_y with a factory templated over iterator types, presumably (maybe we could restrict it to an iterator concept).

We then get to the spicy part, which I’m most unhappy with, which is a very verbose partial interface. I’ll leave a fragment of it here for your viewing pleasure:

template <iter_capability_t Cap>
struct iter_destroy {
	virtual ~iter_destroy() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.destroy)
struct iter_destroy<Cap> {
	virtual ~iter_destroy() = default;
	virtual void destroy(void*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.destroy)
template <typename Iter> struct iter_destroy<Cap>::model: virtual iter_destroy {
	void destroy(void* ptr) const override {
		iter_table_t<Iter>::destroy()(static_cast<Iter*>(ptr));
	}
};

Ostensibly, what is going on here is (besides the gratuitous use of virtual inheritance) is the following: iter_destroy is a capability enabled interface which may or may not provide a base function for destroying the underlying/stored type-erased iterator. It is implemented by a model, which is potentially empty, or otherwise is templated over the iterator type to retrieve the appropriate destruction operation (it’s a function that returns the pointer to a function, it’s a whole ordeal).

These are all collated into a big iterator “vtable”, which can be made concrete through a big templated model. This is what controls the behavior of the iterator class.

The iterator class itself is rather simple, takes, besides a Value, Reference, and Pointer Difference types, a capability non-type template parameter. This parameter is used to enable certain member and friend functions, using a void* to store the underlying iterator it receives, and passing it through our dodgy vtable which knows how to operate on the underlying type.

The choice of default capability being those of a std::unordered_set is mostly due to convenience.

Improvements

The fragmentary Rockefeller hyper-inheritance type dynasty is obviously an eyesore and quite tricky to employ. The main problem here is that virtual methods cannot be disabled with a requires clause; which means we cannot have the whole general interface which simply disables some of its methods when the capability requirements are not met.

The only reason we get away with it on the (only mentioned in the snippet) auxiliary class _::iter_table_t<Iter> is because it is fully concrete, absent of any inheritance nonsense.

Since the underlying iter_vtable_t is already templated on capabilities, Value type, Reference type and Difference type, the immediate solution (which didn’t occur to me when I was excreting this code because I was chasing an obscure bug owing to corrupted pointers :D) is to make the iterator vtable class have non-virtual methods, instead storing pointers to functions that do the heavy lifting as private members, and exposing them through concrete functions which then can be properly restricted by the capability parameter.

This also makes it possible to project/weaken iterators from one set of capabilities to a looser set of capabilities, which is a desirable feature. I’ll make a new post when I have that implemented.