Invisible <voi### [at] devnull> wrote:
> >> Heh, really? Most languages I work with can allocate new objects in O(1)
> >> time and using O(1) memory for bookkeeping. I'm not used to dynamic
> >> allocation being anything to worry about.
> >
> >    Last time I checked, 16 bytes is O(1) memory.

> You seem to suggest that there's 16 bytes of overhead /per object/. I'm 
> saying I'm used to there being a fixed number of bytes of overhead, 
> regardless of the number of objects. That's O(N) vs O(1).

  That's obviously impossible. The only way to achieve that would be
to allocate an array of objects (by value).

  If you allocate individual objects, the allocator has to know where they
are and if those memory blocks are free or not. At least if the allocator
ever wants to reuse freed memory blocks.

> >>>> Mmm, I hadn't even thought of using an /array/. I suppose the upper
> >>>> bound on the tree size is statically known, so why not?
> >>>
> >>>     The array doesn't necessarily have to be fixed in size.
> >
> >> It does if it's static. Either that or the source I'm reading is
> >> incorrect...
> >
> >    You don't have to use a static array.

> Sure. But then you're dynamically allocating again.

  You are allocating *an array* dynamically, not individual objects.
You are making like a couple of 'news' rather than thousands or millions.

> Right. I think I know how to redesign to avoid that. Should make things 
> a bit more coherent...

  If you are creating a dynamic binary tree, there's no avoiding memory
allocation. (One of the very few cases where you can avoid it is with
things like a heap. While a heap is a dynamic binary tree, it can be
implemented as a single array rather than each object being allocated
separately. In fact, the C++ standard library offers heap creation and
managing functions.)

  A possible approach is that the nodes themselves do not manage the
objects they are pointing to, but rather the data container module
itself. This is, for example, what std::set does (in other words,
the nodes in a std::set do not manage the other objects they are
pointing to, but it's the std::set class itself that takes care of
allocating and deleting them as needed.) Of course this requires a
careful design as well, in order to avoid leaks or double deletions.

-- 
                                                          - Warp

Post a reply to this message