The Artima Developer Community
Sponsored Link

Weblogs Forum
A Faster Growable Array ( Indexable Stack ) for C++

18 replies on 2 pages. Most recent reply: Nov 17, 2005 11:08 PM by Christopher Diggins

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 18 replies on 2 pages [ « | 1 2 ]
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: I'm glad I didn't answer last night Posted: Nov 17, 2005 1:21 PM
Reply to this message Reply
Advertisement
> However, I recognize that while random access in this
> Growable Array is O(1), it does steps similar to
> std::vector's at() method (which is O(1), but expected to
> be slower than operator[] O(1)). I'm kind of curious how
> this container compares to std::vector's random access
> methods.

The following are the results comparing operator:

benchmarking : test_vector_indexing(v) 577 mseconds
benchmarking : test_array_indexing(a) 1077 mseconds

So according to my results, accessing an element using the growable array is a little less than twice as slow for a call to std::vector::operation[].

I should point out that in the case of a predetermined initial size for the growable array, the growable array will perform much faster (but still not as fast as the vector). The data structure was designed so that the initial buffer size can be determined at construction.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Thanks for the benchmarks Posted: Nov 17, 2005 3:58 PM
Reply to this message Reply
/* So according to my results, accessing an element using the growable array is a little less than twice as slow for a call to std::vector::operation[].
*/

Nothing wrong with that. It's all about trade-offs. I believe that the growable array has the safety of std::vector::at, which operator[] does not.

Bob Dobalina

Posts: 16
Nickname: hiredgoon
Registered: Apr, 2005

Re: A Faster Growable Array ( Indexable Stack ) for C++ Posted: Nov 17, 2005 11:02 PM
Reply to this message Reply
> There is no realloc new because most of the time you are
> allocating objects. The concept of growing an object
> makes no sense.

Not realloc "new", realloc "new[]" (with brackets on the end) for arrays of objects, where growing does make a bit of sense.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: A Faster Growable Array ( Indexable Stack ) for C++ Posted: Nov 17, 2005 11:08 PM
Reply to this message Reply
> If C++ new[] = malloc, would a new[] equivalent of
> realloc() solve the vector performance problem?
>
> Why isn't there a realloc new[]?

I believe std::allocator class is supposed to provide realloc semantics semantics through the hint parameter of the allocate member function:

pointer allocate(size_type n, allocator<void>::const_pointer hint = 0);

Flat View: This topic has 18 replies on 2 pages [ « | 1  2 ]
Topic: Rich Web Apps Beyond the Browser: Macromedia Central Previous Topic   Next Topic Topic: C++ Cookbook from O'Reilly


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us