C++

A simple question...

is it better to traverse a std::vector like this:

std::vector<int> myvec;
//populate the vector
for(int i = 0; i < myvec.size(); ++i){
    myvec[i] += 1;
}

or is better like this?

std::vector<int> myvec;
typedef std::vector<int>::iterator IT_int;
for(IT_int it = myvec.begin(); it != myvec.end(); ++it){
     *it += 1;
}

#include <iostream>
#include <vector>
#include <ctime>

int main (int argc, char * const argv[]) {
    std::vector<int> myvec;
    for (int i = 0; i < 100000000; ++i) {
        myvec.push_back(i);
    }
    typedef std::vector<int>::iterator IT_int;
   
    clock_t start,end;
   
    start = std::clock();
    for (IT_int it = myvec.begin(); it != myvec.end(); ++it) {
        *it += 1;
    }
    end = std::clock();
   
    std::cout << end - start << std::endl;
   
    start = std::clock();
    for (int i = 0; i < myvec.size(); ++i) {
        myvec[i] += 1;
    }
    end = std::clock();
   
    std::cout << end - start << std::endl;
   
    return 0;
}

output:

1st try:
2858863
1135227

2nd try:
2461235
1139648

3rd try:
2618116
1133062

compiled with XCode 3.2.5, GCC 4.2

Just use an array.

>>1
Strictly speaking you should use iterators. It has the advantage of just being a pointer, but that said, I think C++ ideologies like these are just plain silly.

#include <iostream>
#include <vector>
#include <ctime>

#define SIZETOTEST 100000

int main (int argc, char * const argv[]) {
   
    std::vector<int> myvec;
    int myarray[SIZETOTEST];
   
    for (int i = 0; i < SIZETOTEST; ++i) {
        myvec.push_back(i);
        myarray[i] = i;
    }
    typedef std::vector<int>::iterator IT_int;
   
    clock_t start,end;
   
    start = std::clock();
    for (IT_int it = myvec.begin(); it != myvec.end(); ++it) {
        *it += 1;
    }
    end = std::clock();
   
    std::cout << "iterator it:   " << end - start << std::endl;
   
    start = std::clock();
    for (int i = 0; i < myvec.size(); ++i) {
        myvec[i] += 1;
    }
    end = std::clock();
   
    std::cout << "int i:         "<< end - start << std::endl;
   
    start = std::clock();
    for (int i = 0; i < SIZETOTEST; ++i) {
        myarray[i] = myarray[i] + 1;
    }
    end = std::clock();
    std::cout << "c-style array: " << end - start << std::endl;
   
    return 0;
}

a little deeper analysis:
in debug mode (no or really few optimization):

iterator it:   2430
int i:         1141
c-style array: 561

in release mode:

iterator it:   108
int i:         160
c-style array: 2

amazing... the iterator get faster than the normal access... (the c_style array optimization is also crazy...)

>>5
With the vector, you're potentially doing 100,000 reallocs and bounds checks, but with the array, you're just storing at an offset to a register.

>>6
push_back has order one amortized time according to the best resource to seeples on the internat http://www.cplusplus.com but I agree that it should be avoided in favor of performing a single call to resize and then modification by the [] operator.

>>5
one way to implement a vector iterator would be a direct pointer to a place in the vector's array. And then the tests, it == vec.end() can be performed by comparing the value of the pointer to the address just after the end of the used part of the array. If you were to use indexing on a C array, the compiler can handle optimizing away the index if necessary.

http://en.wikipedia.org/wiki/Loop-invariant_code_motion


std::vector<int> myvec;
for(std::vector<int>::iterator it = myvec.begin(); it != myvec.end(); ++it){
     *it += 1;
}

Frivolous typedef considered UNREADABLE

>>5
the iterator get faster than the normal access

Because the optimizer can treat it as a pointer in some cases.

If you don't need vector functionality, then it's stupid to use them instead of C arrays.

>>9
That's really sad. There's no reason for vector iteration to be so much more inefficient than c array iteration. Although, to be fair, >>5 should do a test with a non statically allocated array. And >>5 should check the assembly output to see if the compiler is just culling out the c array iteration code, because the compiler might know that the code doesn't do anything meaningful or used later, whereas with the vector it might not be able to figure that out.

should be

for(std::vector<int>::iterator i = myvec.begin(), e = myvec.end(); i < e; i++) {

but it doesn't matter for the other one. This will probably make a difference even in release mode since myvec.end() isn't guaranteed to be invariant between calls (mutation by other threads, &c)

>>11
er, obviously i != e there instead