Re: Implementing vector (resizable array) with n-ary tree

<spookyoldtree@xxxxxxxxx> wrote in message
news:1177454046.400199.113200@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.


you can make the vector increase in smaller steps and you can make it shrink.

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.


wrong. it takes 4 constant-time lookups to reach an element only if all vectors
(at all levels) have the same size.

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.


do you plan to add new elements only at the end of your structure or at any
arbitrary position?

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.



I don't understand what you want to improve with your implementation. Why can't
you just use vector?


.

Relevant Pages

  • Implementing vector (resizable array) with n-ary tree
    ... I'm planning to use a fixed-size n-ary tree structure to implement a ... What I need is a vector (resizable array) class with the following ... I am going to make an array of 1024 pointers. ...
    (comp.programming)
  • Re: Differance between Array and Pointers
    ... Well, except that arrays tend to be much larger than pointers, and the ... An array is a contiguous region of memory containing N elements of M ... indexing vs. a loop). ...
    (comp.arch.embedded)
  • [RFCv2][PATCH] flexible array implementation
    ... I call it a flexible array. ... storage for pointers to the second level. ... all locking must be provided by the caller. ... make sure to pass in &ptr instead of ptr. ...
    (Linux-Kernel)
  • [RFC][PATCH] flexible array implementation v4
    ... I call it a flexible array. ... so never does an order>0 allocation. ... storage for pointers to the second level. ... all locking must be provided by the caller. ...
    (Linux-Kernel)
  • Re: [RFC][PATCH] flexible array implementation v4
    ... I call it a flexible array. ... so never does an order>0 allocation. ... storage for pointers to the second level. ... all locking must be provided by the caller. ...
    (Linux-Kernel)