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

From: Boris Breidenbach (Boris.Breidenbach_at_[hidden])
Date: 2006-07-12 05:37:21

On Wed, Jul 12, 2006 at 03:33:43PM +1000, bringiton bringiton wrote:
> On 7/12/06, bringiton bringiton <kneeride_at_[hidden]> 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?