tags:

views:

141

answers:

3

Perhaps this question is trivial, but thinking a second time about it I wonder how to do the following really the right way:

std::vector<K> v = ...;
for(T i=0; i<v.size(); ++i) {
  const K& t = v[i];
  // use t *and i*
}

What type should T be? int, unsigned int, int32_t, size_t (which would be the type of v.size()) or any other suggestions? Please try to consider portability, error-proneness and performance and be objective in your answer.

Edit: I did not choose iterators, because it would also like to use the index number i explicitly.

+6  A: 

The type of i should be the same as the return value of size(), which is std::vector<K>::size_type. However, in practice, size_t will do just fine. If you use a signed integer type, then your compiler will probably warn about a signed/unsigned mismatch in the less-than comparison.

Normally you would use an iterator for this anyway:

std::vector<K> v = ...;
for (std::vector<K>::iterator i = v.begin(); i != v.end(); ++i) {
  const K& t = *i;
  // use t
}

Or, in C++0x:

std::vector<K> v = ...;
for (auto i = v.begin(); i != v.end(); ++i) {
  const K& t = *i;
  // use t
}

In response to your comment about using the vector index with iterators, consider the std::distance() function which is constant time operation for vector iterators:

std::vector<K> v = ...;
for (auto i = v.begin(); i != v.end(); ++i) {
  const K& t = *i;
  size_t index = std::distance(v.begin(), i);
  // use t and index
}
Greg Hewgill
Or, in C++0x: `for (auto i:v) { .. }` (N2930) :-)
Luther Blissett
Now my question would be, what is faster/clearer/portable: using an integer to iterate (and having it as index directly) or using an iterator and the distance function to compute the index?
Danvil
@Danvil: most likely, it doesn't matter. Both consist of a simple increment and either an add or a subtract. And in both cases, those two statements cannot be parallized. I expect that the solution to increment both i and the iterator separately will be slightly faster as it can be parallized. However, I doubt the difference is measurable in practice.
Sjoerd
+3  A: 

The type returned by v.size and expected by v[] is std::vector<K>::size_type.

However, consider using iterators instead : the risk of going out of bounds is lower, and you can use the standard library algorithms.

Victor Nicollet
+3  A: 
KennyTM
And how to know the position of the element in theses cases? Do you thing that iterators and extra counting are better than using a number to iterate?
Danvil
@Danvil: Usually I'll keep 2 variables, the counter and the iterator. This is needed if you want to traverse non-vector structures. But for vectors, `t = v[i]` and `i = distance(cit, begin)` have similar performance, and both involve only pointer arithmetic and bit shifts.
KennyTM
If I would use int as iterator type, considering the fact, that size() is size_t which is usually unsigned, isn't it slower to compare signed to unsigned integers? Additionally the compiler prduces one of these annoying warnings about comparing signed to unsigned integers.
Danvil
I would expect ++i, ++cit to be slightly faster as it is parallizable by the CPU.
Sjoerd
@Danvil: On x86-64, g++ 4.2, comparing unsigned with signed or unsigned makes no difference. Comparing signed with signed use 2 less opcodes.
KennyTM