Iteration Over Std::Vector: Unsigned VS Signed Index Variable

Iteration over std::vector: unsigned vs signed index variable

For iterating backwards see this answer.

Iterating forwards is almost identical. Just change the iterators / swap decrement by increment. You should prefer iterators. Some people tell you to use std::size_t as the index variable type. However, that is not portable. Always use the size_type typedef of the container (While you could get away with only a conversion in the forward iterating case, it could actually go wrong all the way in the backward iterating case when using std::size_t, in case std::size_t is wider than what is the typedef of size_type):

---

Using std::vector

Using iterators

for(std::vector<T>::iterator it = v.begin(); it != v.end(); ++it) {
    /* std::cout << *it; ... */
}

Important is, always use the prefix increment form for iterators whose definitions you don't know. That will ensure your code runs as generic as possible.

Using Range C++11

for(auto const& value: a) {
     /* std::cout << value; ... */

Using indices

for(std::vector<int>::size_type i = 0; i != v.size(); i++) {
    /* std::cout << v[i]; ... */
}

---

Using arrays

Using iterators

for(element_type* it = a; it != (a + (sizeof a / sizeof *a)); it++) {
    /* std::cout << *it; ... */
}

Using Range C++11

for(auto const& value: a) {
     /* std::cout << value; ... */

Using indices

for(std::size_t i = 0; i != (sizeof a / sizeof *a); i++) {
    /* std::cout << a[i]; ... */
}

Read in the backward iterating answer what problem the sizeof approach can yield to, though.

What should be the index type when iterating over the elements of a vector?

You should use std::vector<T>::size_type¹. Its unsigned integral type. Its usually same as size_t.

To know the difference between size_type and size_t, see this topic:

• C++ for-loop - size_type vs. size_t

^{1. Similarly, you can use std::string::size_type, std::list<T>::size_type, std::deque<T>::size_type, std::set<T>::size_type, and so on. Almost all standard containers define a nested type called size_type.}

---

One can argue that you should use iterator instead of index. But I also see that sometime iterator makes the for-loop very wide horizontally, see this :

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

It doesn't look. It in fact irritates sometimes. In such situations, some programmers prefers index over iterator.

In C++0x, iterator has been made more idiomatic. Now you can use iterator without making the syntax cumbersome:

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

Or even better, using range-based for loop:

for(auto & item : v)
{
}

Iterate through a C++ Vector using a 'for' loop

Is there any reason I don't see this in C++? Is it bad practice?

No. It is not a bad practice, but the following approach renders your code certain flexibility.

Usually, pre-C++11 the code for iterating over container elements uses iterators, something like:

std::vector<int>::iterator it = vector.begin();

This is because it makes the code more flexible.

All standard library containers support and provide iterators. If at a later point of development you need to switch to another container, then this code does not need to be changed.

Note: Writing code which works with every possible standard library container is not as easy as it might seem to be.

acceptable fix for majority of signed/unsigned warnings?

I made this community wiki... Please edit it. I don't agree with the advice against "int" anymore. I now see it as not bad.

Yes, i agree with Richard. You should never use 'int' as the counting variable in a loop like those. The following is how you might want to do various loops using indices (althought there is little reason to, occasionally this can be useful).

Forward

for(std::vector<int>::size_type i = 0; i < someVector.size(); i++) {
    /* ... */
}

Backward

You can do this, which is perfectly defined behaivor:

for(std::vector<int>::size_type i = someVector.size() - 1; 
    i != (std::vector<int>::size_type) -1; i--) {
    /* ... */
}

Soon, with c++1x (next C++ version) coming along nicely, you can do it like this:

for(auto i = someVector.size() - 1; i != (decltype(i)) -1; i--) {
    /* ... */
}

Decrementing below 0 will cause i to wrap around, because it is unsigned.

But unsigned will make bugs slurp in

That should never be an argument to make it the wrong way (using 'int').

Why not use std::size_t above?

The C++ Standard defines in 23.1 p5 Container Requirements, that T::size_type , for T being some Container, that this type is some implementation defined unsigned integral type. Now, using std::size_t for i above will let bugs slurp in silently. If T::size_type is less or greater than std::size_t, then it will overflow i, or not even get up to (std::size_t)-1 if someVector.size() == 0. Likewise, the condition of the loop would have been broken completely.

Why unordered_map not showing correct index values of a vector?

your for loop has a wrong range. You start at element 1 and because of <= only stop at the size of codeforces + 1, which is out of bounds.

When iterating arrays the index starts at 0 and should end at size() - 1. This can be easily achieved by saying < size() as the less operator will result in false if the index is at size() - therefore size() - 1 is the last iteration step.

---

You have two options, either go from 1 to size() and access [i - 1]

for(int i = 1; i <= x.size(); i++){
    data[x[i - 1]].push_back(i);
}

or go from 0 to size() - 1 and push_back(i + 1)

for(int i = 0; i < x.size(); i++){
    data[x[i]].push_back(i + 1);
}

I recommend the latter, as it's the common way to iterate arrays.

---

read here why you should avoid writing using namespace std;.

Slow performance using std::distance to get std::map index

std::map is a tree structure. It's not random access, and elements don't have indices, and the only way to advance through the tree is to follow the links, one at a time. Because of this, std::map::iterator is a BidirectionalIterator. That means it only supports increment and decrement operations. It doesn't support any sort of difference operation. To get the difference between two of them you have to repeatedly increment the start iterator until it's equal to the end iterator. Something like this:

template <typename Iterator>
size_t distance(Iterator start, Iterator end)
{
    size_t dist = 0;
    while (start != end) {
        ++dist;
        ++start;
    }
    return dist;
}

Looking at that function, you can probably see why your loop is slow. Every time through the loop, std::distance has to walk through the tree and count how far from the beginning it is. If you really need an index to go with your map, you'll need to maintain it yourself. std::map doesn't seem like the right structure in that case though, since the indices will change as new elements are added.

C++, fast removal of elements from vector by binary index

Unfortunately there is no automatism for this. You simply have to implement a custom erase function yourself:

auto widx = numbers.begin();
for (auto ridx = numbers.cbegin(), auto bidx = idxs.cbegin();
     ridx != numbers.end;
     ++ridx, ++bidx) {
  if (*bidx) *widx++ = *ridx;
}
numbers.erase(widx, numbers.end());

---

Related Topics