Speed of iterating through STL containers

Which is slower, in general, using std::iterators or using operator[], when available.

e.g., say you have an std::vector<int> int_vector, you could loop through in a couple of different ways:

PHP Code:

---


for(int i = 0; i , int_vector.size(); i++)
{
    int this_int = int_vector[i]; //same as int_vector.at(i)
}

...

for(std::vector<int>::iterator ptr = int_vector.begin(); ptr != int_vector.end(); ptr++)
{
   int this_int = *ptr;
} 


---

Tests using both high and low resolution timers give inconsistent results. Which is typically seen as the "better" method to use? My guess is they're both ultimately pretty much the same thing under the hood.

For using vectors it should not matter. It's like using a pointer vs a subscript for looking through an array. Litterally, that's all you'd be doing.

For deque I'd immagine iterators would be faster, because an itterator would have a pointer to the element itself, and not require the two levels of indirection as with operator[].

I'm inclined to believe iterators are faster due to the fact the [] operator makes a copy of the value, while the iterator type does not.

for a vector the two methods are pretty much equivalent. The second method is more generic (you could easily replace vector with list, if you felt it was a better choice), but the first is probably more readable to the average C++ programmer.

As a minor nit, it's better not to call .size() as the loop condition (unless the size can change in the loop).

in this case operator [] easier

for (i = 0; i < nSize; ++i)
[i]

Kuphryn

Uh, why is it easier?

And I expect the average C++ programmer to be so familiar with iterators that it would be actually more intuitive to them than an index loop.

Mario F. is wrong: [] does not make a copy. It returns a reference (const reference for const containers).

Advantages of iterators:
1) More universally applicable.
2) Sometimes better debugging behaviour.
3) Potentially easier to optimize for the compiler. But only potentially; making assumptions about optimization behaviour is rarely a good idea.

Disadvantages:
1) Tends to be a bit longer to type.

One more thing: vector::at() and vector::operator[] are not the same! at() performs an additional index check and is thus slower, but safer.

>> due to the fact the [] operator makes a copy of the value.
No, it doesn't, it returns a reference.

I'd use the iterators unless you never use any other standard containers or algorithms in your code since it would be more consistent. If you have mostly C-style code, the array syntax might be more consistent.

Yes. I was actually just checking my sources. The responses seemed to go against my... *cough* theory. So I wanted to check back on what I believed I read about iterators compared to subscripting.

I'm deeply wrong. I apologize :)

Quote:

---

As a minor nit, it's better not to call .size() as the loop condition (unless the size can change in the loop).

---

Thank you, I did not know that!

Quote:

---

As a minor nit, it's better not to call .size() as the loop condition (unless the size can change in the loop).

---

Wait, don't you mean unless the size is guaranteed to stay the same during the loop?

If there is a chance that the size of the container will change in the loop, then size() is actually protecting you, since it will return the current size. A fixed value won't update by itself. Though it is a good idea to cache the size in a variable if it isn't going to change.

I test against size() all the time. If I'm going to use it a lot in a function, I stick the value in a temp variable and use it throughout the function.

As far as the question I really don't think there is a major performance diff between the two methods. At least not one worth worrying about.

I normally use iterators only when I have to such as map::find() and other STL functions requiring an iterator. Usually I use array subscript for everything else.

Correct me if I'm wrong, but doesn't [] involve a multiplication (for objects of greater size than 1 at least)?

Code:

---

Array[i]

---

would be assembled to using the address (each iteration):

Code:

---

Array + (TypeSize * i).

---

While the iterator would just increment each iteration.

If you really want to be sure the best thing to do is to not guess, and write a program to measure. I did exactly that, and it turns out that [] is much faster than an iterator. Makes sense to me, that's what [] was supposed to do faster than anything else.

Quote:

---

I did exactly that, and it turns out that [] is much faster than an iterator. Makes sense to me, that's what [] was supposed to do faster than anything else.

---

According to BobMcGee123, "Tests using both high and low resolution timers give inconsistent results."

It probably depends on the implementation, level of optimisation, exact usage etc. And doesnt really matter unless it is the performance bottleneck, which I find rather unlikely.

Quote:

---

Originally Posted by Magos

Correct me if I'm wrong, but doesn't [] involve a multiplication (for objects of greater size than 1 at least)?

---

Yes, but
1) The compiler might optimize that away by incrementing the counter by the byte size every iteration.
2) The compiler might optimize it away by converting the whole loop to a pointer-increment loop.
3) The compiler might optimize it away by using a specialized memory addressing instruction, which most CPUs (even RISC) have, and which typically are just as fast as the direct instructions.
4) Since types are typically aligned at power-of-two-boundaries, the multiplication is just a shift anyway.

So that's not going to make a real difference.

citizen: Have you tested this in release mode? Debug iterators often have a lot of overhead.

I can promise you I don't use debug builds for testing things.

Curiously enough, my test also shows subscripting to be faster.

Code:

---

#include <cstdlib>
#include <iostream>
#include <vector>
#include <iterator>
#include <ctime>

using namespace std;

int main()
{

    vector<int> vec(10000000, 1);
    vector<int> vec2(10000000, 3);
    vector<int>::iterator iter = vec.begin();
    vector<int>::iterator iter2 = vec2.begin();
    clock_t start_iter, end_iter;

    start_iter = clock();
    cout << "Iterators ----\nStart: " << start_iter << flush;
    for(; iter != vec.end(); ++iter) {
        for (; iter2 != vec2.end(); ++iter2) {
            ;
        }
    }
    end_iter = clock();
    cout << "\nEnd: " << end_iter << "\nClock: " << end_iter - start_iter << endl;

    start_iter = clock();
    cout << "\nSubscripting ----\nStart: " << start_iter << flush;
    for(unsigned long i = 0; i != vec.size(); ++i) {
        for(unsigned long j = 0; j != vec2.size(); ++j) {
            ;
        }
    }
    end_iter = clock();
    cout << "\nEnd: " << end_iter << "\nClock: " << end_iter - start_iter << endl;

    system("pause");

    return EXIT_SUCCESS;
}

---

Quote:

---

Curiously enough, my test also shows subscripting to be faster.

---

hmm... but all your code does is compare incrementing iterators to incrementing unsigned longs.

Very true.

However, changing the null statements to int some_int = *iter + *iter2 and [I]int some_int = vec + vec2[j] respectively, shows subscripting to be much, much slower than iterators this time...

There does not seem to be a behavior justifying the "shouldn't matter" thesis, in any case.

When I changed to *iter = *iter2 and [I]vec = vec2[j] to test assignment, the results seemed consistent with subscripting being much, much, slower.

It seems subscripting is only faster if one only traverses the container and does not read from or write to it.

Quote:

---

There does not seem to be a behavior justifying the "shouldn't matter" thesis, in any case.

---

Well, if the number of element accesses is relatively small, improving other factors may make much more of a difference.

Quote:

---

It seems subscripting is only faster if one only traverses the container and does not read from or write to it.

---

If there's no accessing of the elements, the subscript has not been used.