Decrementable requirements of general end iterators vs container `end()`

user_616460 0
Viewed 126

I am working on a ReversibleContainer and its associated LegacyRandomAccessIterators. They wrap a pre-existing data structure that represents a directly-indexable collection of objects. I decided to allow the iterators to exist standalone, and to make default-constructed iterators represent the "end":

// constructs an iterator that provides a view of 'data'
the_iterator (thedata *data, difference_type index = 0);

// constructs an iterator representing the end
the_iterator ();

So I can do e.g.:

std::for_each(the_iterator(data), the_iterator(), ...);

The iterators do all the work. The container is pretty lightweight. I implemented the container's begin() and end() like this:

struct the_container {
    the_data *data; // <- object wrapped by this container
    the_iterator begin () { return the_iterator(data); }
    the_iterator end () { return the_iterator(); }
};

I've got it working just fine, but in testing I realized that I messed up and it does not meet the basic Container requirements because:

  • As it turns out, for containers with bidirectional iterators, end() is required to return a decrementable iterator when the container is non-empty, but
  • My default-constructed end iterator doesn't store any information about any thedata, and so it can't be decremented because it isn't aware of what the "last element" of any particular collection is.

So I've got to fix the container now. The solution I'm thinking of is (let data->number_of_items contain the item count):

  • Continue to allow default-constructed iterators to represent the "end".
  • Also let the_iterator(data, data->number_of_items) represent the "end", in line with container requirements. This iterator would be decrementable.

Then the container would do:

struct the_container {
    the_data *data; // <- object wrapped by this container
    the_iterator begin () { return the_iterator(data, 0); }
    the_iterator end () { return the_iterator(data, data->number_of_items); }
};

Now, that's fine, and it satisfies all the Container requirements. However, I'm now left wondering if my default-constructed iterators are allowed to exist at all.

So, my question, then, is: While Container puts decrementability requirements on the iterator that it returns from end(), are there similar requirements for iterators that just represent the "end" of some data but aren't involved with the container's end()?

More formally, if:

  • j is a bidirectional iterator
  • container.empty() == false
  • ( j == container.end() ) == true

Then does --j need to be valid and need to end up pointing to the last element of the container? An example of that situation in my case is:

the_container container(data); // <- assume data->number_of_items > 0
the_iterator b = container.begin();
the_iterator e = container.end();
the_iterator j;

assert(container.empty() == false);
assert(e == j);
assert(distance(b, e) == distance(b, j));

-- e;  // <- this is required to be well-defined
-- j;  // <- but is this??

So, yeah, that's my question. I'm worried that maybe some implementation of something or other in e.g. <algorithm> might assume that one of my "end" iterators is decrementable, or that I'm breaking something subtle that I don't understand.

c++17 language-lawyer iterator containers c++
2 Answers

As a frame challenge, what you have here is a sentinal. A sentinal is something you can compare iterators to, but is not an iterator.

The motivating example is a type that when compared with a char pointer just checks if the dereference of the char pointer is null. You can use this to write C-level "read string until null" while still using for(:) loops and the like.

The ranged based for(:) loop was augmented to allow begin and end to have distinct types to allow sentinals to exist and be maximally efficient.

Consider replacing your default constructed iterator trick with an end sentinal. This doesn't work with many pre-ranges-v2 algorithms, but at least you are uwing tried and true patterns.

And no, I don't think your end iterator violates the rules. As an example, iterators from two containers can have non sense == results under the standard. Your end iterator can be treated as an iterator from another container with a predictable == behaviour.

Now, what happens when you pass it to an algorithm? That probably makes your program ill-formed; the algorithm can detect what guarantees you give with traits, and your fake end iterator is not a valid bidirectional iterator into the same container as the begin iterator.

user_17746670

Then does --j need to be valid and need to end up pointing to the last element of the container?

For any bidirectional iterator, --j must be well defined as long as its pre-conditions are satisfied. And the pre-condition is that there exists another iterator s for which j == ++s. And for your container the iterator to the last valid element is such iterator

As such, I don't believe that your iterator would satisfy the requirements of a bidirectional iterator and thus the container would not be reversible.

If you want to define a sentinel for a bidirectional iterator, it can be done by using a separate type so that iterator requirements won't apply to it. There is a caveat though that most standard algorithms don't support separate iterator and sentinel types. std::ranges algorithms do.

Alternatively, you could specify that the default initialised iterator is singular i.e. it isn't associated with any container. In such case -- j wouldn't have any requirements (nor would j == e). But then b, j wouldn't be a valid range and you still wouldn't be allowed to pass such pair into standard algorithms.

user_20793030
Related