Re: [Boost-users] vector vs list speed test

On Wed, Jul 12, 2006 at 03:33:43PM +1000, bringiton bringiton wrote:

On 7/12/06, bringiton bringiton wrote:

...

I'm just wondering what your thoughts are on my findings.

I need a container that meets the following: - forward iteration only - insert to end only - no random access - delete from any position - average size of list will be 64 items

I would first say use list over vector. because no random access and delete from any position. I ran some performance tests, which proved otherwise.

The test builds a list by inserting to end. And then removes all items from the front until size == 0. (note: removing from index [0] should provide worst case linear complexity for vector)

Here are my finding for containers of size 64, 256 and 1024. first result uses vector, 2nd uses list. i ran the test in release mode in ms vc++ 6.

Test build/remove 64 0.062 0.234 Test build/remove 256 0.422 0.938 Test build/remove 1024 5.844 3.75

I played some more and tried a deque. I used your code, just replacing vector, by deque. These are my timings (third value is deque) Test build/remove 64 0.06 0.17 0.06 Test build/remove 256 0.31 0.72 0.23 Test build/remove 1024 2.97 2.82 0.91 So maybe you should go for a deque?