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)

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` — Slava, Oct 11 '16 at 15:27
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. — Felix Lauer, Oct 11 '16 at 15:30
Shameless plug for [cppitertools `iter::enumerate`](https://github.com/ryanhaining/cppitertools#enumerate) — Ryan Haining, Oct 11 '16 at 22:19

Yakk - Adam Nevraumont · Accepted Answer · 2016-10-11T16:08:50.473

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.

krzaq · Answer 2 · 2016-10-11T15:35:01.727

6

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()

edited Oct 11 '16 at 15:35

answered Oct 11 '16 at 15:23

krzaq

16,240
4
46
61

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... – Resurrection Oct 11 '16 at 15:28
Yes, `vector` is a mistake that we can't get rid of. It's a nice class, but it's not a `vector`. – krzaq Oct 11 '16 at 15:31
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`? – Nir Friedman Oct 11 '16 at 15:34
@NirFriedman because when I was writing this post the OP stated `int index = ...`. Fixed. – krzaq Oct 11 '16 at 15:34
@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. – Resurrection Oct 11 '16 at 15:35
@krzaq my bad; +1'ed. – Nir Friedman Oct 11 '16 at 15:35

Obtaining item index in ranged based for on vector

2 Answers2

Linked

Related