16

Generally speaking C++ doesn't allow comparing iterators between different containers. For example:

int main() {
  std::vector<int> v = {1, 2, 3};
  std::vector<int> w = {4, 5, 6};
  std::cout << v.end() == w.end() << std::endl;  // undefined!
}

But is this true also for subspans created with std::span::subspan()? For example:

int main() {
  int a[4] = { 1, 2, 3, 4};
  std::span<int> s(a);
  std::span<int> t = s.subspan(1, 2);
  std::cout << t.begin() - s.begin() << std::endl;
}

This prints 1, which is expected, because internally iterators are probably just pointer to the underlying array. The question is: does the standard guarantee that this works correctly?

And if so, more generally, can I also compare iterators from any spans that come from the same contiguous object in memory? For example:

int main() {
  int a[5] = { 1, 2, 3, 4, 5};
  std::span<int> s(a);
  std::cout << (s.subspan(1, 1).end() < s.subspan(3, 1).begin()) << std::endl;
}
Aamir
  • 1,974
  • 1
  • 14
  • 18
Maks Verver
  • 661
  • 4
  • 14
  • 3
    Added language-lawyer tag, per "does the standard guarantee" – Brian61354270 Jul 26 '23 at 16:37
  • 1
    Relevant draft section: [24.7.2.2.7 / span.iterators](https://eel.is/c++draft/span.iterators) – Brian61354270 Jul 26 '23 at 16:44
  • Compare iterators on different objets is a U.B. Trying this code with MSVC, gives the error "cannot compare incompatible span iterators" in debug, but because their are raw pointers in release the code runs fine. – dalfaB Jul 26 '23 at 19:39
  • 3
    Another interesting question would be whether subspan iterators can be compared to iterators from the underlying container – Ben Voigt Jul 26 '23 at 19:58

1 Answers1

3

I don't think the standard allows this.

According to the description of Cpp17ForwardIterator in [forward.iterators]:

The domain of == for forward iterators is that of iterators over the same underlying sequence.

This means that the equality and inequality operations of two iterators are only defined over the same underlying sequence.

In your example, the underlying sequences of the two iterators being compared are different, because they have different start points and different sizes, which makes comparisons no longer well-defined when one of the iterators is outside the bounds of the other sequence.

As mentioned in the comments, your example will trigger an assert in MSVC-STL's debug mode, which was explained by the maintainer in #1435. Similar issues are also discussed in the Cpp Core Guidelines, see #1157.

康桓瑋
  • 33,481
  • 5
  • 40
  • 90
  • Does `std::ranges::subrange` suffer from the same issue as `std::span::subspan`? I am not sure whether I should ask a new question, but occasionally I want to do `std::prev(subrange.begin())` when I know that `subrange.begin()` does not equal the `begin()` of underlying range. Is that allowed? – Weijun Zhou Jul 27 '23 at 06:29
  • 1
    I think `std::prev(subrange.begin())` is ok, because `subrange.begin()` is specified to return the underlying *original* iterator. The validity of the operation on the original iterator will not change. – 康桓瑋 Jul 27 '23 at 12:06
  • 1
    "underlying sequences of the two iterators being compared are different" - that requires citation. It is plausible that the wording is that span's underlying sequence remains the original buffer, with begin/end of the span itself being a subsequence. It would depend on how the standard is worded. – Yakk - Adam Nevraumont Jul 27 '23 at 20:53
  • 1
    @Yakk-AdamNevraumont I don't think the current standard clearly defines what the underlying sequence of an iterator is. There was one in C++17: "*An iterator j is called reachable from an iterator `i` if and only if there is a finite sequence of applications of the expression `++i` that makes `i == j`. If `j` is reachable from `i`, they refer to elements of the same sequence*" but I think it could still be interpreted differently in the current context. – 康桓瑋 Jul 28 '23 at 02:20