Re: Data Structure Issue
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<Node> myList;
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