iterate through std::vector ?

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

Quote:

---

Originally Posted by 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.

---

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

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:
  
  Code:

  ---

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

  ---

  But not that:
  
  Code:

  ---

  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.

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.

Quote:

---

Originally Posted by 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.

---

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.

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

Quote:

---

Originally Posted by 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).

---

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