c++: Is it valid to subtract an iterator from an element pointer to get a valid index?

Question

I came across the following code:

for (int i = 0; i < subspan.size(); i++) {
  ...
  int size = size_table[&(subspan[i]) - fullspan.begin()];
  ...
}

subspanand fullspan are both of type std::span (actually absl::Span from Google's Abseil library, but they seem to be pretty much the same as std::span) and are views into the same data array (with fullspan spanning the entire array).

Is this valid and well defined code? It seems to depend on the iterator being converted to the corresponding pointer value when the - operator is applied together with a lhs pointer.

It depends - so you'll need to read documentation to find out. There are a few possibilities, depending on what `absl::Span` is, what type the `.begin()` member returns, what type the result of `&(subspan[i])` is (e.g. is the `&` the "address-of" operator, or does it result in a call of a unary `operator&()` that returns something else?) — Peter, Nov 23 '21 at 13:04
I'd rather go the safe way by `&*fullspan.begin()` to make sure both are pointers of the same type – or operate on iterators right away, any reason for not using an iterator based for loop – or even a range based one? — Aconcagua, Nov 23 '21 at 13:21
@Aconcagua I don't know, not my code. Just trying to understand if it's well defined — matthias_buehlmann, Nov 23 '21 at 14:12
@Aconcagua `or operate on iterators right away` The iterators are from separate spans, so I wouldn't consider it to be safer; That would be more likely to compile, but possibly fail at runtime if the iterator type validates the range. `&*fullspan.begin()` is OK with the assumption that the spans are indeed to the same array. — eerorika, Nov 23 '21 at 15:18

eerorika · Answer 1 · 2021-11-23T13:01:19.173

Is it valid to subtract an iterator from an element pointer to get a valid index?

It could be, depending on how the iterator is defined. For example, it works if the iterator is a pointer of the same type, and points to an element of the same array.

However, no generic iterator concept specifies such operation, and so such operation isn't guaranteed to work with any standard iterator. Hence, it's not a portable assumption that it would work in generic code.

Is this valid and well defined code?

The iterator type in question is defined to be the pointer type, so that condition is satisfied. Abseil is neither thoroughly documented nor specified, so it's hard to say whether that's an intentional feature, or incidental implementation detail. If it's latter, then the code may break in future versions of Abseil.

score 0 · Answer 2 · answered Nov 23 '21 at 12:51

Reading the implementation of absl::Span, we have:

template <typename T>
class Span {
...
 public:
  using element_type = T;
  using pointer = T*;
  using const_pointer = const T*;
  using reference = T&;
...
  using iterator = pointer;
...
  constexpr iterator begin() const noexcept { return data(); }
  constexpr reference operator[](size_type i) const noexcept { return *(data() + i); }
...
}

So your expression boils down to plain pointer arithmetic. Note that there is no check on whether both spans refer to the same base span, but you asserted that was not the case.

I wouldn't rely on the implementation to tell you this. It should be documented whether this is a safe assumption. — chris, Nov 23 '21 at 13:07

c++: Is it valid to subtract an iterator from an element pointer to get a valid index?

2 Answers2