How to iterate over a vector?

Question

I need to iterate over a vector strictly in the order the elements were pushed back into it. For my particular case it's better use iterators than iterating though the for-each loop as follows:

std::vector<int> vector;
for(int i = 0; i < vector.size(); i++)
   //not good, but works

My question is if it's realiably to iterate over the vector through iterator like that:

std::vector<int> v;
for(typename std::vector<int>::iterator i = v.iterator(); i != v.end(); i++)
   //good, but I'm not strictly sure about the iterating order.

So, can I use iterators safely with my requirements? Is it standartized?

Answer 1

This is an overly complex solution.

First, we start with an index type. It can store anything that models iterator and/or integral (basically, supports + scalar, delta to scalar, copy, destruction and equality):

template<class T,
  class Category=std::random_access_iterator_tag,
  class Delta=decltype(std::declval<T>()-std::declval<T>())
>
struct index:
  std::iterator<Category, T, Delta, T*, T>
{
  T t;
  T operator*()const{ return t; }
  index& operator++(){++t; return *this;}
  index operator++(int){index tmp = *this; ++t; return tmp;}
  index& operator--(){--t; return *this;}
  index operator--(int){index tmp = *this; --t; return tmp;}
  T operator[](size_t i)const{return t+i;}
  friend bool operator<(index const& lhs, index const& rhs) {
    return rhs.t-lhs.t>0;
  }
  friend bool operator>(index const& lhs, index const& rhs) {
    return rhs<lhs;
  }
  friend bool operator<=(index const& lhs, index const& rhs) {
    return !(lhs>rhs);
  }
  friend bool operator>=(index const& lhs, index const& rhs) {
    return !(lhs<rhs);
  }
  friend bool operator==(index const& lhs, index const& rhs) {
    return lhs.t==rhs.t;
  }
  friend bool operator!=(index const& lhs, index const& rhs) {
    return lhs.t!=rhs.t;
  }
  friend Delta operator-(index const& lhs, index const& rhs) {
    return lhs.t-rhs.t;
  }
  friend index& operator+=(index& lhs, Delta rhs) {
    lhs.t+=rhs;
    return lhs;
  }
  friend index& operator-=(index& lhs, Delta rhs) {
    lhs.t-=rhs;
    return lhs;
  }
  friend index operator+(index idx, Delta scalar) {
    idx+=scalar;
    return idx;
  }
  friend index operator+(Delta scalar, index idx) {
    idx+=scalar;
    return idx;
  }
  friend index operator-(index idx, Delta scalar) {
    idx-=scalar;
    return idx;
  }
};

most of which isn't needed, but I wanted to be complete. Note that this claims to be a random access iterator by default, but it lies, as its reference type is not a reference. I consider the lie worthwhile.

With index we can both create an iterator-over-integrals, and an iterator-over-iterators. Here is how we create an iterator-over-iterators:

using it_category=typename std::iterator_traits<It>::iterator_category;

template<class It, class Category=it_category<It>>
index<It, Category> meta_iterator( It it ) { return {it}; }

Next, we want to be able to take some iterators, and iterate over the range. This means we want a range type:

template<class It>
struct range {
  It b, e;
  range(It s, It f):b(s),e(f){}
  range():b(),e(){}
  It begin()const{return b;}
  It end()const{return e;}
  bool empty()const{return begin()==end();}
  template<class R>
  range(R&& r):range(std::begin(r),std::end(r)){}
};

This is a trait that takes an iterable range (not only a range, but also any container) and gets the iterator type out. Note that a superior ADL-enabled one would be a good idea:

template<class R>
using iterator=decltype(std::begin(std::declval<R&>()));

Random helpers:

template<class R,class It=iterator<R>>
range<It> make_range(R&&r){ return {std::forward<R>(r)}; }
template<class It
range<It> make_range(It s, It f){return {s,f};}

Here is a useful helper that solves our problem:

template<class R>
range<meta_iterator<iterator<R>> iterators_into( R&& r ){
  return {meta_iterator(std::begin(r)), meta_iterator(std::end(r))};
}

and we are done:

std::vector<int> v;
for(auto it: iterators_into(v)) {
}

returns an iterator for each element of v.

For industrial quality, you'd want to ADL-improve things. Also, dealing with rvalue storage of input ranges lets you chain range-adaptors better in for(:) loops.

Answer 2

If you have access to C++11 you can use range-based for loops

for (auto i : v)

Otherwise you should use begin() and end()

for (std::vector<int>::iterator i = v.begin(); i != v.end(); ++i)

You can also use std::begin and std::end (these require C++11 as well)

for (std::vector<int>::iterator i = std::begin(v); i != std::end(v); ++i)

begin will return an iterator to the first element in your vector. end will return an iterator to one element past the end of your vector. So the order in which you get the elements iterating this way is both safe and defined.

Answer 3

if you want to use iterators, your approach is fine

for(auto it = v.begin(); it != v.end(); ++it)

the iteration order depends in fact on the container and the actual used iterator. for a std::vector this code iterates always over the elements in their order in the vector. if you'd use v.rbegin() or v.rend() instead, the order would be reversed. for another container the order is different, for a std::set the very same code would iterate the elements in ascending order of their sorting criterion.