Data Structure Issue

[Alexander Adam]

Hello folks,

I got a few question on some basic data structure stuff. Sorry if
those questions might sound too easy or such but after googling a lot
I didn't find a real answer to all those questions so appreciate any
help.

I need to keep a very efficient data-tree structure (parent, previous,
next, first child, last child) within the memory which can be filled
up with billions of records. A struct place into the tree (I am using
the tree implementation of kp) is looking like this:

struct Node {
unsigned char type;
unsigned char code;
??? data;
??? unsigned char* content;
}

Now the first question is this -- the *data* property can be of a
single byte property or taking a full unsigned int or even more..
what'd be the best way to always keep the smallest size in memory?
(E.g. when having only a byte value then allocate only one byte in
memory for this property).

The next question is if it makes sense to allocate and deallocate the
content property within the constructor/destructor of the struct but I
fear that a constructor and destructor will add another couple of
bytes to each record in the memory.

The next issue I have is this -- the implementation I am using is
returning an iterator object, a function looks like this:

iterator parent(...) {}

Now what is this return value all about? I mean, its not a pointer so
it should be only valid until it goes out of scope within the parent
caller, is that assumptation correct? What I need is to keep the
iterator during lifetime and assign it to my objects so what's the
best way to keep it valid all time, assuming the std::list or tree
(whatever, they're compatible) gets inserts and delete statements a
lot?

Also there's a point I don't really understand. Say if I have
something like

std::list<NodemyList;

then what's the real difference in accessing an item either by

Node& node = *myList.begin()

or by

Node node = *myList.begin() ?

I've always thought that the first one would just get the reference to
the original struct the iterator is pointing to and the second one
creates a copy of it in the heap? If so, the first method should be
more efficient is that correct, too?

Basically, I need to obtain a most perfomant tree-like data structure
keeping a struct like the one mentioned before. What'd be the best way
to go, assuming that I have a lot of inserts, deletes and traversions
and that I need the parent, prev sibling, next sibling and first
child / last child access by hand without any time loss anytime?

Hopefully someone would be so kind to answer those questions in
detail, I'd appreciate very much to gather as much experience as
possible in good C++ Development.

Thanks & warm regards
Alexander

[Alexander Adam]

Hi!

Sorry, there's one thing I've forgotten to ask -- how can it be
avoided to have an additional allocation/deallocation when adding a
new record to my std::list or whatever container I am using? I mean,
doing something like

Node myNode;
....
myList.push_back(myNode);

will lead to create a myNode var on the heap, then making a copy of it
for the list and finally let it go out of scope. This seems quite too
inefficient to me though so is there a better way around except
creating your own pointer to Node?

Thanks!
Alexander

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

On 2007-07-04 06:45, Alexander Adam wrote:

Hello folks,

I got a few question on some basic data structure stuff. Sorry if
those questions might sound too easy or such but after googling a lot
I didn't find a real answer to all those questions so appreciate any
help.

I need to keep a very efficient data-tree structure (parent, previous,
next, first child, last child) within the memory which can be filled
up with billions of records. A struct place into the tree (I am using
the tree implementation of kp) is looking like this:

struct Node {
unsigned char type;
unsigned char code;
??? data;
??? unsigned char* content;
}

Type should probably be an enum, perhaps code also.

Now the first question is this -- the *data* property can be of a
single byte property or taking a full unsigned int or even more..
what'd be the best way to always keep the smallest size in memory?
(E.g. when having only a byte value then allocate only one byte in
memory for this property).

If all the nodes in the tree will have the same size of data then you
can parameterise Node to that type:

template<typename T>
struct Node {
// ...
T data;
// ...
};

By the way, what's the difference between data and content?

The next question is if it makes sense to allocate and deallocate the
content property within the constructor/destructor of the struct but I
fear that a constructor and destructor will add another couple of
bytes to each record in the memory.

Adding a constructor/destructor might add a few extra bytes to the code,
but should not affect the runtime size of a Node-object.

The next issue I have is this -- the implementation I am using is
returning an iterator object, a function looks like this:

iterator parent(...) {}

Now what is this return value all about? I mean, its not a pointer so
it should be only valid until it goes out of scope within the parent
caller, is that assumptation correct? What I need is to keep the
iterator during lifetime and assign it to my objects so what's the
best way to keep it valid all time, assuming the std::list or tree
(whatever, they're compatible) gets inserts and delete statements a
lot?

I guess that the iterator is a standard iterator to either an object in
a list or a map (or such) in which case the iterator will be valid so
long as the Node is still in the list. For standard containers which are
node-based the validity of iterators is not affected by any operations
on the container unless the operation affects the node the iterator
refers to.

Also there's a point I don't really understand. Say if I have
something like

std::list<NodemyList;

then what's the real difference in accessing an item either by

Node& node = *myList.begin()

or by

Node node = *myList.begin() ?

I've always thought that the first one would just get the reference to
the original struct the iterator is pointing to and the second one
creates a copy of it in the heap? If so, the first method should be
more efficient is that correct, too?

Yes.

Basically, I need to obtain a most perfomant tree-like data structure
keeping a struct like the one mentioned before. What'd be the best way
to go, assuming that I have a lot of inserts, deletes and traversions
and that I need the parent, prev sibling, next sibling and first
child / last child access by hand without any time loss anytime?

I'd probably do something like this:

template<typename T>
struct Node {
NodeType type; // enum
NodeCode code; // enum
Node* parent;
Node* previous;
Node* next;
Node* left; // left child
Node* right; // right child
T data;
unsigned char* content; // ???
};

and store them in a std::list<Node*>, this way inserts and deletes are
very cheap. However you still have to create the objects using new and
delete them when you are done. Also don't forget to fix any pointers in
other nodes when inserting and deleting. You might also want to use a
specialised allocator for the nodes.

For some usages this scheme might not be possible to use, but I don't
know how you are going to use the tree so I can't give anything but
general advice. It might also be possible to get rid of the std::list,
and just have the Nodes.

--
Erik Wikström

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

On 2007-07-04 06:47, Alexander Adam wrote:

Hi!

Sorry, there's one thing I've forgotten to ask -- how can it be
avoided to have an additional allocation/deallocation when adding a
new record to my std::list or whatever container I am using? I mean,
doing something like

Node myNode;
...
myList.push_back(myNode);

will lead to create a myNode var on the heap, then making a copy of it
for the list and finally let it go out of scope. This seems quite too
inefficient to me though so is there a better way around except
creating your own pointer to Node?

Actually this first creates a Node-object on the stack, then a copy will
be made (probably on the heap) by the list. And then the object on the
stack will go out of scope and destroyed. To avoid this insert just
pointers:

Node* myNode = new Node();

myList.push_back(myNode);

This way only a pointer will be copied. There are some drawbacks with
this scheme though, and you might want to use some kind of smart pointer.

--
Erik Wikström

[Jon Harrop]

Alexander Adam wrote:

I need to keep a very efficient data-tree structure (parent, previous,
next, first child, last child) within the memory which can be filled
up with billions of records.

That's a graph. If you want memory efficiency, remove all of the non-tree
pointers.

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/product...ournal/?usenet