Is pointer-difference a valid way to find the index of an element in a vector within a range-based for loop?

user_2726892 0
Viewed 75

Is it valid to use pointer-difference to find the index of an element within a range-based for loop?

A number of questions have been asked here concerning using indices and range-based loops together, but they almost all say to not use range-based loops if you also need the index of an element. But it seems like, at least for std::vector, std::array, and other containers which are contiguous in memory, you could use pointer differences to find the index of the element, provided you're iterating over element references. For example:

// Prints the indices of all elements for which Foo::bar is true.
void Example(const std::vector<Foo>& v) {
  for (const auto& e : v) {
    if (e.bar()) {
      auto index = &e - v.data(); // Valid???
      std::cout << index << std::endl;
    }
  }
}

The above code compiles and runs correctly, but I'm not completely certain of its validity. Can any language lawyers confirm or deny whether this is an acceptable method to find the index of the element?

In addition, is it safe to assume that if a container has a data() member, then its elements are contiguous in memory, and is therefore safe to use with this approach?

language-lawyer c++
2 Answers

If the underlying iterator meets the requirements of the LegacyContiguousIterator (C++17), then yes. This requirement indicates that *(itr + n) is equivalent to *(addressof(*itr)+n).

This is from https://en.cppreference.com/w/cpp/named_req/ContiguousIterator

C++20 replaced it with the contiguous_iterator concept.

The Cppreference page indicates vector<bool> does not meet the above concepts, but all other vectors do. As do string, string_view, array, and the iterators for the begin/end overloads for valarray.

user_8622310 
auto index = &e - v.data(); // Valid???

Unless Foo is an alias to bool, yes.

&e and v.data() having pointer type, [expr.add]/5 applies:

When two pointer expressions P and Q are subtracted, the type of the result is an implementation-defined signed integral type; this type shall be the same type that is defined as std​::​ptrdiff_­t in the <cstddef> header ([support.types.layout]).

(5.2) Otherwise, if P and Q point to, respectively, array elements i and j of the same array object x, the expression P - Q has the value i−j.

So, unless e or v.data() are not part of the same array object, this is well-defined. This could happen if Foo is an alias for bool, otherwise this condition is met per vector.overview/2 ensuring [container.requirements.general], itself ensuring [iterator.concept.contiguous]/2:

Let a and b be dereferenceable iterators and c be a non-dereferenceable iterator of type I such that b is reachable from a and c is reachable from b, and let D be iter_­difference_­t<I>. The type I models contiguous_­iterator only if

(2.2) to_­address(b) == to_­address(a) + D(b - a), and
(2.3) to_­address(c) == to_­address(a) + D(c - a).

In addition, is it safe to assume that if a container has a data() member, then its elements are contiguous in memory, and is therefore safe to use with this approach?

We could construct weird situations where it weren't safe, but unless you do some really exotic things you're safe to go!

user_54705960
Related