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
Name:
Anonymous2012-04-11 18:05
Just use an array.
Name:
Anonymous2012-04-11 18:11
>>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.
>>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.
Name:
Anonymous2012-04-12 0:16
>>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.
>>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)
>>17 is just screaming please give me some toilets to scrub!
Name:
Anonymous2012-04-12 6:46
>>15
Too bad it has GC. Haskell is not the best. GC is shit.
Name:
Anonymous2012-04-12 7:24
would someone bugger me?
Name:
Anonymous2012-04-12 8:25
Wow. I'm surprised that there is really difference in speed between these versions. I thought optimizers in -O3 already could optimize out differences. Alas.
Well, anyway I prefer iterator approach as in debug mode it checks ranges.
Name:
Anonymous2012-04-12 8:45
Well, anyway I prefer index approach as in /prog/ mode it checks dubs.
Name:
Anonymous2012-04-12 12:58
What kind of shitty compilers are you using to get results like that?
With gcc traversing a vector with an iterator or an unsigned int as well as traversing an array are all equally fast. Iterating with signed int is about 20% slower which I guess is because gcc doesn't change the < comparison to != then, and equality comparisons are often a bit faster.
Name:
Anonymous2012-04-12 13:42
>>23 equality comparisons are often a bit faster.
Stop it, I'm crying.
>>29
that can actually be O(log(n)) where n is the number of bits, by using a balanced tree of or gates. And the same applies to x == y operation, except you would use and gates.
Name:
Anonymous2012-04-12 22:54
>>35 I'm gonna pursue my BA in toilet scrubbing at anywhere that will hire me forever.