Re: Data Structure Issue
On Jul 4, 6:45 am, Alexander Adam <cont...@emiasys.com> wrote:
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.
So space efficiency is more important than runtime efficiency.
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).
It's hard to say. A struct cannot contain anything with a
variable size, so you may have to use an additional dynamic
allocation for it. (Don't forget, however, that dynamic
allocation has its own overhead---8 additional bytes, on my
machine. And of course, the struct must then contain at least a
pointer.)
One solution might be to use a union, e.g.:
union DataType
{
char chData ;
unsigned int uiData ;
???* otherData ;
} ;
You'll need to be able to discriminate from outside of the
union, but if e.g. type or code are enough to tell you what the
type of data is, then this would seem to be an appropriate
solution. The otherData field, of course, would have to be
dynamically allocated. (And with this, I'd suggest a set of
constructors and a destructor. And depending on how often the
Nodes are copied, perhaps reference counting for the otherData,
although deep copy will usually be simpler and sufficient.)
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.
Constructor and destructor typically won't add anything to the
object's footprint. Virtual functions will. But don't forget
the overhead for dynamic allocation. If at all possible, make
"content" a value member, and avoid allocating it as a separate
object at all.
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?
Return by value.
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?
Whatever you're actually returning, yes. The semantics of
return by value is that a copy is made. Depending on what you
do with the return value, that copy is then copied to the final
destination. The standard explicitly allows the compiler to
assume that the copy constructor only copies, and the destructor
only destructs, and to elide any number of these copies; most
compilers do.
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?
That's largely up to the container. std::list guarantees that
its iterators are valid as long as the element they designate
isn't removed from the list. Other containers make weaker
guarantees---an insertion may invalidate an iterator into an
std::vector, for example. For non-standard containers, it's up
to the author of the container to decide what he wants to
guarantee, and what not, and to document it.
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?
On the stack. (More correctly, wherever the compiler puts its
local variables. But the way scope works requires the semantics
of a stack, and all of the widespread implementations do
maintain a very simple stack, separate from the heap, and put
the local variables there.)
Other than that, you're correct. Note, however, that if you
make context part of the struct, and the data hasn't been
dynamically allocated, the copy will be very rapid. Not
anything to worry about, until the profiler says otherwise. I'd
base the choice on the desired semantics; if I just want a
value, the copy is best, but if I want to modify the value in
the list, I must use the reference.
If so, the first method should be
more efficient is that correct, too?
Maybe. It depends on how much copying the object costs.
Typically, unless the object is very big, there's no real
difference. Accessing through a reference is typically slightly
slower, so whatever you might gain by not copying, you loose in
the accesses. Unless the object is extremely expensive to copy,
you're wasting your time worrying about it. If it does turn out
to be a problem, it's easy enough to fix once the profiler says
you have to.
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?
Lots of pointers directly in the data structure:-).
In my pre-standard DLList class, I used something like:
struct BasicNode
{
BasicNode* next ;
BasicNode* prec ;
BasicNode()
: next( this )
, prec( this )
{
}
} ;
template< typename T >
struct Node : public BasicNode
{
T data ;
} ;
All you really need to do is add a lot of additional pointers to
the BasicNode, and define the instantiation type for the Node
template to contain the necessary data (probablly using the
union above).
If this really is a one-off situation, you can forgo the
template. You might even forge the base class, and put the
pointers directly in the Node, although I like the separation of
concerns here (but note that it does involve some downcasting).
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34