Obtaining item index in ranged based for on vector

Question

The C++11 introduced ranged-based for loop that is internally implemented using (const) iterators so this:

std::vector<std::string> vec;

for(std::string &str : vec)
{
//...
}

is basically equivalent to more verbose (yes, it could be simplified using auto):

for(std::vector<std::string>::iterator it = vec.begin(); it != vec.end(); ++it)
{
//...
}

However commonly one needs an index of the item as well. With the second approach that is easy:

auto index = it - vec.begin();

In ranged-based for it is not so straightforward. But I was wondering if this was ok and portable solution that avoids iterators altogether:

for(auto &str : vec)
{
    auto index = &str - &vec[0];
}

(const version will be the same but one needs to watch out not to mix non-const container with const reference which might not always be obvious.)

Obviously this relies on several assumptions:

• that iterator of vector is just a reference to an item (probably in the standard?)

• container is guaranteed contiguous (std::vector is...)

• the internal implementation of ranged based for (also probably in the standard)

Lactoscope

First loop is not equivalent - you copy every value while iterating. If you use auto anyway you better use auto for index rather than int – Bridgettebridgewater

@Bridgettebridgewater Fair points. I will update the OP accordingly. – Lactoscope

Technically, your proposed C++11 for loop copies every string in vec (other than with the iterator-based version). You should use for(std::string const& str : vec) or for(auto const& str : vec) for read-only access instead. – Discourse

Shameless plug for cppitertools iter::enumerate – Ethelstan

Answer 1

Yes, but I'd use vec.data() instead. A bonus of using .data() is that non-contiguous std containers don't have it, so your code reliably stops compiling when the container being iterated over doesn't work that way (like deque or std::vector<bool>). (There are other minor advantages, like std::addressof issues, and the fact it is well defined on empty containers, but those aren't as important especially here.)

Alternatively we write an index_t iterator-like wrapper:

template<class T>
struct index_t {
  T t;
  T operator*()const{ return t; }
  void operator++() { ++t; }
  friend bool operator==( index_t const& lhs, index_t const& rhs ) {
    return lhs.t == rhs.t;
  }
  friend bool operator!=( index_t const& lhs, index_t const& rhs ) {
    return lhs.t != rhs.t;
  }
};
template<class T>
index_t<T> index(T t) { return {t}; }

index_t<int> can be used to create counting for(:) loops.

index_t<iterator> can be used to create iterator-returning for(:) loops.

template<class It>
struct range_t {
  It b,e;
  It begin() const {return b;}
  It end() const {return e;}
};
template<class It>
range_t<It> range( It s, It f ) { return {s,f}; }

template<class T>
range_t<index_t<T>>
index_over( T s, T f ) {
  return {{{s}}, {{f}}};
}
template<class Container>
auto iterators_of( Container& c ) {
  using std::begin; using std::end;
  return index_over( begin(c), end(c) );
}

we can now iterator over iterators of a container.

for (auto it : iterators_of(vec))

live example.

---

The mentioned iterate-over-integers is:

for (int i : index_over( 0, 100 ) )

we can also directly get the indexes of the container:

template<class Container>
range_t< index_t<std::size_t> >
indexes_of( Container& c ) {
  return index_over( std::size_t(0), c.size() );
}
template<class T, std::size_t N>
range_t< index_t<std::size_t> >
indexes_of( T(&)[N] ) {
  return index_over( std::size_t(0), N );
}

which lets us:

for( auto i : indexes_of( vec ) )

where i varies from 0 to vec.size()-1. I find this is easier to work with sometimes than a zip iterator or the like.

---

Improvements omitted:

Make index_t a real input_iterator. Use std::move and/or std::forward as needed in making indexes and ranges. Support Sentinals on ranges. Make range_t interface richer (size, optional random-access [], empty, front, back, range_t range_t::without_front(n) const, etc.

Intuitivism

Answer 2

Yes, that's a valid solution. The underlying data is guaranteed to be contiguous (std::vector is supposed to be a dynamic array, more or less).

n4140 §23.3.6.1 [vector.overview]/1

The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size()

Ito

Interesting point there T is some type other than bool because iirc with bool std::vector becomes basically a bit array and my solution will likely NOT work then... – Lactoscope

Yes, vector<bool> is a mistake that we can't get rid of. It's a nice class, but it's not a vector. – Ito

I'm not sure why you wrote "smaller than an int can hold" when the solution OP asked about was auto index = &str - &vec[0];. Why does the difference of two pointers have to do with int? Wouldn't auto deduce to a std::ptrdiff_t? – Kareykari

@NirFriedman because when I was writing this post the OP stated int index = .... Fixed. – Ito

@NirFriedman It was pointed out that having int there was sub-optimal plus some other minor issue and I have corrected both, see comments to OP. – Lactoscope

@Ito my bad; +1'ed. – Kareykari