The fastest way to iterate through a collection of objects

First to give you some background: I have some research code which performs a Monte Carlo simulation, essential what happens is I iterate through a collection of objects, compute a number of vectors from their surface then for each vector I iterate through the collection of objects again to see if the vector hits another object (similar to ray tracing). The pseudo code would look something like this

for each object {
    for a number of vectors {
        do some computations
        for each object {
            check if vector intersects
        }
    }
}

As the number of objects can be quite large and the amount of rays is even larger I thought it would be wise to optimise how I iterate through the collection of objects. I created some test code which tests arrays, lists and vectors and for my first test cases found that vectors iterators were around twice as fast as arrays however when I i开发者_如何学Gomplemented a vector in my code in was somewhat slower than the array I was using before.

So I went back to the test code and increased the complexity of the object function each loop was calling (a dummy function equivalent to 'check if vector intersects') and I found that when the complexity of the function increases the execution time gap between arrays and vectors reduces until eventually the array was quicker.

Does anyone know why this occurs? It seems strange that execution time inside the loop should effect the outer loop run time.

What you are measuring is the difference of overhead to access element from an array and a vector. (as well as their creation/modification etc... depending on the operation you are doing).

EDIT: It will vary depending on the platform/os/library you are using.

It probably depends on the implementation of vector iterators. Some implementations are better than others. (Visual C++ — at least older versions — I'm looking at you.)

I think the time difference I was witnessing was actually due to an error in the pointer handling code. After making a few modifications to make the code more readable the iterations were taking around the time (give or take 1%) regardless of the container. Which makes sense as all the containers have the same access mechanism.

However I did notice the vector runs a bit slower in an OpenMP architecture this is probably due to the overhead in each thread maintaining its own copy of the iterator.