Summary
I have just developed a growable array class as part of the OOTL, which outperforms std::vector on calls to push_back() by a factor of 2.5 on my installation of GCC.

The std::vector class from the STL is an example of a very useful data type: the growable array. The problem with most implementations of std::vector when used as indexable stacks is that when they reach the reserved memory capacity, a new block is allocated, and all of the data is copied. Or something like that. Correct me if I've made mistakes, I promise not to bite.

An alternate implementation is to create a reversed linked list of buffers which have exponentially increasing size. This allows you to grow the array without reallocation, and can save you an enormous amount of time. The results from my tests, which you can download at OOTL.org, using GCC 3.4 are as follows:

benchmarking : grow_vector(v, 42, count)
1719 mseconds
benchmarking : grow_array(a, 42, count)
641 mseconds
benchmarking : grow_vector(v, "hello", count / 10)
6077 mseconds
benchmarking : grow_array(a, "hello", count / 10)
4406 mseconds

I found that iteration over the list was just as fast as for a std::vector, by using the for_each member function (the growable_array is a model of the Iterable concept).

This implementation also retains the characteristics of average O(1) individual element access. Half of the elements are in the first list node, one quarter are in the next, and so on. In the worst case -- which is accessing the first element ironically enough -- the complexity is O(Log N). That entails a traversal of the linked list of buffers.

Anyway the code is public domain, so have fun with it!

Talk Back!

Have an opinion? Readers have already posted 18 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Christopher Diggins adds a new entry to his weblog, subscribe to his RSS feed.

Digg | del.icio.us | Reddit

About the Blogger

Christopher Diggins is a software developer and freelance writer. Christopher loves programming, but is eternally frustrated by the shortcomings of modern programming languages. As would any reasonable person in his shoes, he decided to quit his day job to write his own ( www.heron-language.com ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at www.cdiggins.com.