iterate through std::vector ?

[Butterfly]

As I see in C++ books, all of them using != operator to check that the vector is end or not.
example:

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

Is it possible if we use itr < vec.end() instead ????

[Kheun]

You shouldn't even if it works. This is because different implementation of STLs may choose to return different values to indicate the end.

[Kheun]

In addition, it will not work for container like list and map because they are not using contiguous memory.

[Ejaz]

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

int main()
{
vector< int> vec;
vec.push_back( 1 );
vec.push_back( 2 );
vec.push_back( 3 );

std::vector<int>::iterator itr;
for ( itr = vec.begin(); itr < vec.end(); ++itr )
{
cout << *itr << endl;
}

return 0;
}

This code will output the vector contents correctly. vec.begin(), returns _First, and vec.end() returns _Last. As vector is a sequential container, so iterating it the way you want, will work here, but as Kheun stated that you shouldn't adopt this practice, as some other container may not work like that, which kills the reason to use standard practices at the first place.

[treuss]

You shouldn't even if it works. This is because different implementation of STLs may choose to return different values to indicate the end.Not sure, this is correct. As "iter-n" is defined for random access iterators (e.g. vector::iterator), your statement would mean, that end()-1 has not defined behavior (assuming there is at least one element in the vector). I don't think that's true.
So I would state, that using it<end() is safe to use for std::vector, but it is bad practice due to the reason that it will not work with other containers.

[Kheun]

May be I am wrong but for assumption that "iter < end()", it requires the end() to greater than the rest of the valid iterator range. Since we can't take for granted that iterator in vector is being implemented as pointer, I don't think we can assume "iter < end()" is always true. It's all dependent on how the vendor choose to implement it.

I am not sure what's the correct behavior. Probably someone with the C++ Standard can enlighten me.

[laserlight]

Looking through section 23.1 of the C++ Standard (ISO/IEC 14882:2003), it seems that part of the container requirements specifies that for a container a, a.size() has operational semantics of "a.end()-a.begin()", and "begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container. If the container is empty, then begin() == end();"

That seems to guarantee that a.end() returns an iterator exactly one past the end value for container a. If not, it may be possible that a.size() == (a.end() - a.begin()) evaluates to false.

[treuss]

Found the following example from Josuttis book:
// Iterate through every second element
for (vector<int>::iterator it = v.begin(); it < v.end(); it += 2 )So that seems to confirm that it is safe.

[laserlight]

There's more to it, I think. For iterators, operator< is only defined for random access iterators, so while it may be safe in Josuttis' example, using operator!= is better in that it applies for all input iterators. In treuss' words, "it is bad practice due to the reason that it will not work with other containers" (that dont support random access iterators).

[treuss]

For iterators, operator< is only defined for random access iterators, so while it may be safe in Josuttis' example, using operator!= is better in that it applies for all input iterators.The example will not work for containers which provide bidrectional iterators only, as +=(int) is not defined for those, and using != instead of < max actually result in a program crash if the number of elements is odd.

[Kheun]

Thank guys! :thumb:

[Butterfly]

I've heard that operator < only works with random-access iterators, whereas != works with other iterator types. But in this case, vector is not random access but why when we use operator <, it works.

[Kheun]

See the quote from MSDN.


The STL vector class is a template class of sequence containers that arrange elements of a given type in a linear arrangement and allow fast random access to any element. They should be the preferred container for a sequence when random-access performance is at a premium.

[SuperKoko]

I've heard that operator < only works with random-access iterators, whereas != works with other iterator types. But in this case, vector is not random access but why when we use operator <, it works.

std::vector is a random access container.
And std::vector::iterator is a random access iterator.


The example will not work for containers which provide bidrectional iterators only, as +=(int) is not defined for those, and using != instead of < max actually result in a program crash if the number of elements is odd.

It is less likely to crash with <, but it may also crash.
Because adding two to an iterator equal to end()-1, may crash or yield an invalid iterator (it is like incrementing end()).
With trivial implementations of vector, it is unlikely (except if the vector has a max address equal to 2^32-1).
But, with std::deque it is very likely to happen.

[treuss]

It is less likely to crash with <, but it may also crash.
Because adding two to an iterator equal to end()-1, may crash or yield an invalid iterator (it is like incrementing end()).
With trivial implementations of vector, it is unlikely (except if the vector has a max address equal to 2^32-1).
But, with std::deque it is very likely to happen.Good point :thumb:
I actually quoted wrongly, the example is for (pos = coll.begin(); pos < coll.end()-1; pos += 2) and Josuttis explicitly stated that coll need to contain at least one argument for coll.end()-1 to be defined.

One should never close a book and then quote from it ;).

[NMTop40]

It is also better not to call end() at every iteration, because you should not rely on the compiler optimising away the extra calls.

[SuperKoko]

It is also better not to call end() at every iteration, because you should not rely on the compiler optimising away the extra calls.

It make me think about many, many C programs contain such code:

int i;
char* str="hello, world!";
for(i=0 ; i < strlen(str) ; i++){
// do something
}

And, just assumed the compiler will "optimize" it.
Of course these same programmers could say... whouaa ! My compiler std::string are ten/hundred/thousand time faster than C strings!

It is true that the compiler can optimize it, because strlen, as other functions of the standard library, is a reserved name in the global namespace (or namespace std in C++).
Thus, the compiler know that this invocation calls the "true" strlen.

However:

Few compilers do that (GCC do that optimization).
If the string is modified in that loop, the compiler is really very unlikely to optimize the function call, because the string length may change.
For example GCC 4.0.2, optimize that:

void DoWork(char* p)
{
int i;
for(i=0;i<strlen(p);i++);

But not that:

void DoWork(char* p)
{
int i;
for(i=0;i<strlen(p);i++){
p[i]='A';
}

Even if a human understand that it is optimizable.


I don't say that you should hand code all optimizations.
But, if there is an optimization unlikely to be done by all compilers, and that without this optimization the code is very very inefficient, you should not rely on this optimization.
If this optimization does not change significantly the speed, then, you don't need to matter.

[treuss]

I would say, there is quite a difference between calling end() and strlen() in the loop. strlen() is O(n), while I believe end() is guaranteed to be O(1). It is also very likely, that end() can be inlined, thus making the hand-optimization futile.

[SuperKoko]

I would say, there is quite a difference between calling end() and strlen() in the loop. strlen() is O(n), while I believe end() is guaranteed to be O(1). It is also very likely, that end() can be inlined, thus making the hand-optimization futile.

I did not said that it was bad to use end() inside the condition loop. I was talking about strlen.
The NMTop40 statement brought that to my mind.

However, even inlined, it is probable that one indirection may be saved with most compilers, if the body of the for loop contains any external function call or things that may the compiler think that the vector size has been modified.
Indeed it cannot save much CPU.

[NMTop40]

end() being O(1) simply means that it is not dependent on the size of the collection.

It doesn't mean that calling it N times is O(1).

[SuperKoko]

end() being O(1) simply means that it is not dependent on the size of the collection.

It doesn't mean that calling it N times is O(1).

Yes, it is O(N), but any non-empty for loop has a complexity at least equal to O(N).
Thus, it does not change complexity.

However O(1) does not mean that it is optimally fast.
There may need thousand CPU cycles to access the size.

However, you can assume that it is nearly optimal... the compiler is a friend, it does not volountary make things slow.
And, a variable access is also O(1), and can also be slow if the compiler does not play fairly... :D