Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Obtaining item index in ranged based for on vector

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)

like image 242
Resurrection Avatar asked Oct 11 '16 15:10

Resurrection


2 Answers

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.

like image 160
Yakk - Adam Nevraumont Avatar answered Sep 21 '22 12:09

Yakk - Adam Nevraumont


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

like image 33
krzaq Avatar answered Sep 19 '22 12:09

krzaq