Implementing vector (resizable array) with n-ary tree
- From: spookyoldtree@xxxxxxxxx
- Date: 24 Apr 2007 15:34:06 -0700
I'm planning to use a fixed-size n-ary tree structure to implement a
resizable array. I'll describe it in some detail below. The thing
is, it's a simple idea and surely many others have done it before me,
but I don't know what it's called. If anyone could fill me in (and
perhaps point me to references) that would be much appreciated!
To give some context, I am thinking of this as a replacement for the
STL vector class, to be used in a C++ application I'm writing. But
the general idea is not specific to C++. It would apply to any
language that can implement resizable arrays.
What I need is a vector (resizable array) class with the following
properties:
1. Small, constant element access time.
2. Small, constant time to resize the array.
3. Does not use too much extra space.
The standard C++ vector class is typically implemented as a linear
array. Whenever it runs out of space, a new array is allocated with
significantly larger size (say, a multiple of 2), the elements are
copied to the new array, and the old array is deallocated. This
satisfies #1 for sure. It also satisfies #2, if you consider the
resizing expense to be amortized -- in other words, resizing usually
costs O(1), and occasionally costs a whopping O(n), but the big cost
is infrequent enough that the average resize time is still O(1).
My problem with standard vector is that it does not satisfy #3. My
application cannot predict in advance how many elements will be
needed. So it will be repeatedly resizing the vector. What if there
are only a few elements left, the vector is using half of the
available memory, and then suddenly it runs out of space internally
and therefore doubles its size!? That's a lot of memory wasted on
account of a few additional elements.
So here's my idea. I have decided that I will never conceivably need
more than 1024^4 == 1,099,511,627,776 elements in my array. That will
be my fixed upper limit. (I realize it is no longer truly a general
purpose array, but come on, give me a break. 1 trillion ought to be
enough for anyone ;-)
I am going to make an array of 1024 pointers. When the array is
empty, each pointer is null. When it has data in it, some of the
pointers point to other arrays of 1024 pointers. Some of these in
turn point to more arrays. The structure goes 4 deep. So the fourth
level contains the real elements of my vector. Thus, it takes 4
constant-time lookups to reach an element.
To put it another way, each array is a node of a 1024-ary tree, with
depth 4. The leaves of the tree are the elements of the (logical)
vector. As the (logical) vector grows, the tree gets more leaves and
branches, growing from left to right, getting closer to its maximum
size.
Yes, I am wasting memory for up to 4*1024 pointers. But I can live
with this fixed-size cost. For my application, I consider it to be a
one-time, relatively small overhead.
I am also increasing the element lookup time, but it is still small
and still constant time.
So, does anyone know what this approach is called? (Even better, does
anyone know of existing open-source C++ implementations?) Thanks in
advance!
Sincerely,
Clay Enga
.
- Follow-Ups:
- Re: Implementing vector (resizable array) with n-ary tree
- From: SucMucPaProlij
- Re: Implementing vector (resizable array) with n-ary tree
- From: Ben Pfaff
- Re: Implementing vector (resizable array) with n-ary tree
- Prev by Date: Re: Change for a Dollar
- Next by Date: Re: Implementing vector (resizable array) with n-ary tree
- Previous by thread: Change for a Dollar
- Next by thread: Re: Implementing vector (resizable array) with n-ary tree
- Index(es):
Relevant Pages
|
