Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Basic design question, about data structures

Reply
Thread Tools

Basic design question, about data structures

 
 
JSeb
Guest
Posts: n/a
 
      02-12-2008
Hi there gurus,

This is a design question. Hope I'll get some insights!

Trying to get back in shape with C++, I'm writing a nice BST class. So
I have a nice class TreeNode:

template <typename T> class TreeNode
{
private:
T* mpData;
const TreeNode<T>* mpLeftChild;
const TreeNode<T>* mpRightChild;

TreeNode(const T& aData)
: mpData(&aData), mpLeftChild(NULL), mpRightChild(NULL)
{ }

// ...
};

Type T can be a huuuuuge class, so when I initialize a node with data
of this type, I make mpData point directly to the original data. That
is, I don't call type T's copy constructor.

Q1: Is that the usual approach (avoid copy constructors) when writing
a data structure?

Actually, I initially wrote
const T* const mpData;
in the declaration above. This seemed a sensible thing to do, because
I don't want the data to change while it is in the tree. Otherwise,
the tree property might become violated.

But that didn't do it. Consider for instance:

MyType data = MyType();
TreeNode<MyType> node = TreeNode(data)
data.modify()

The last line modifies the content of data, so the tree (that will
eventually contain node) might become invalid...

Q2: How does one typically deal with that king of situation? It seems
we would want the content of the data structure to be "frozen", but
only while it is in the data structure...

I think I might have a couple more seemingly basic questions, but I'll
stop here and wait for now.

Thank you!
 
Reply With Quote
 
 
 
 
Jeff Schwab
Guest
Posts: n/a
 
      02-12-2008
JSeb wrote:
> Hi there gurus,
>
> This is a design question. Hope I'll get some insights!
>
> Trying to get back in shape with C++, I'm writing a nice BST class. So
> I have a nice class TreeNode:
>
> template <typename T> class TreeNode
> {
> private:
> T* mpData;
> const TreeNode<T>* mpLeftChild;
> const TreeNode<T>* mpRightChild;
>
> TreeNode(const T& aData)
> : mpData(&aData), mpLeftChild(NULL), mpRightChild(NULL)
> { }
>
> // ...
> };
>
> Type T can be a huuuuuge class, so when I initialize a node with data
> of this type, I make mpData point directly to the original data. That
> is, I don't call type T's copy constructor.
>
> Q1: Is that the usual approach (avoid copy constructors) when writing
> a data structure?


Nope. Copy T directly. If copies are expensive, it's up to the client
code to declare TreeNode<SomeType*> rather than TreeNode<SomeType>.
(You still might want to specialize for pointer types.)

> Actually, I initially wrote
> const T* const mpData;
> in the declaration above. This seemed a sensible thing to do, because
> I don't want the data to change while it is in the tree. Otherwise,
> the tree property might become violated.


Yep, that gets tricky. A similar issue arose re. the std::set class:
http://std.dkuug.dk/jtc1/sc22/wg21/d...fects.html#103

> But that didn't do it. Consider for instance:
>
> MyType data = MyType();
> TreeNode<MyType> node = TreeNode(data)
> data.modify()
>
> The last line modifies the content of data, so the tree (that will
> eventually contain node) might become invalid...


But that's because the pointers are const, and has nothing to do with
whether the payloads are constant. Rather than "T const* const",
consider "T const*". Since the payload-pointer (mpData) is private, you
have a chance to review all attempts to modify the pointer, and can
reject them (or update your tree) as necessary.

> Q2: How does one typically deal with that king of situation? It seems
> we would want the content of the data structure to be "frozen", but
> only while it is in the data structure...
>
> I think I might have a couple more seemingly basic questions, but I'll
> stop here and wait for now.
>
> Thank you!

 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      02-12-2008
JSeb wrote:

> Hi there gurus,
>
> This is a design question. Hope I'll get some insights!
>
> Trying to get back in shape with C++, I'm writing a nice BST class. So
> I have a nice class TreeNode:
>
> template <typename T> class TreeNode
> {
> private:
> T* mpData;
> const TreeNode<T>* mpLeftChild;
> const TreeNode<T>* mpRightChild;
>
> TreeNode(const T& aData)
> : mpData(&aData), mpLeftChild(NULL), mpRightChild(NULL)
> { }
>
> // ...
> };
>
> Type T can be a huuuuuge class, so when I initialize a node with data
> of this type, I make mpData point directly to the original data. That
> is, I don't call type T's copy constructor.
>
> Q1: Is that the usual approach (avoid copy constructors) when writing
> a data structure?


Not for container like classes. All standard containers copy the objects so
that they can destruct their contents properly without worrying. Also, your
code is more generic if you use T instead of T* internally: if you want
pointers, just instantiate the template like

TreeNode< SomeBigClass* >


> Actually, I initially wrote
> const T* const mpData;
> in the declaration above. This seemed a sensible thing to do, because
> I don't want the data to change while it is in the tree. Otherwise,
> the tree property might become violated.


Well, then do

TreeNode< SomeBigClass const * >

>
> But that didn't do it. Consider for instance:
>
> MyType data = MyType();
> TreeNode<MyType> node = TreeNode(data)
> data.modify()
>
> The last line modifies the content of data, so the tree (that will
> eventually contain node) might become invalid...


Huh? Invalid in what sense? Note:


int dummy = 5;
int const * ip = &dummy;
dummy = 6;

There is nothing invalid about ip after the last line. It will happily point
to the int dummy, which now has value 6. The const modifier does not render
it invalid to modify an non-const object, it only prevents modification
through the "access route" that was declared const.


> Q2: How does one typically deal with that king of situation?


What kind of situation? It is not really clear what the underlying problem
is that you are trying to solve. Without background information, it is hard
to tell you what best practices would be.

> It seems
> we would want the content of the data structure to be "frozen", but
> only while it is in the data structure...


Huh?


[snip]


Best

Kai-Uwe Bux
 
Reply With Quote
 
JSeb
Guest
Posts: n/a
 
      02-12-2008
> Huh? Invalid in what sense? Note:
>
> int dummy = 5;
> int const * ip = &dummy;
> dummy = 6;


I was referring to the fact that the tree property might get violated
if some of the data contained in the tree is modified (without the
tree being aware of it).

Thanks for the info. I appreciate it. So I'll copy the data into the
nodes, and consider using TreeNode<MyType const*> when the copy
constructor is impractical.

I appreciate the answers guys! Jeff:I will check the link you
provided. I'll come back with other stuff that make me scratch my
head.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      02-12-2008
JSeb wrote:
> template <typename T> class TreeNode
> {
> private:
> T* mpData;
> const TreeNode<T>* mpLeftChild;
> const TreeNode<T>* mpRightChild;
>
> TreeNode(const T& aData)
> : mpData(&aData), mpLeftChild(NULL), mpRightChild(NULL)
> { }
>
> // ...
> };


There are many problems in storing just a pointer to the data. The
most prominent one is that it's very unsafe, as it requires the user to
be very careful about how he creates and stores the data. For instance,
giving the TreeNode constructor a temporary would cause a malfunction
(which the compiler probably doesn't even detect). Likewise giving it a
local instance of an object which will go out of scope sooner than the
tree will also cause malfunction.

Another problem is the one of responsibility: Who is responsible for
freeing the data, the user or this data container? There would be
advantages and disadvantages in both solutions. For example, if the
responsibility for freeing the data is left to the data container, it's
handier from the point of view of the user, and makes the code slightly
safer (as mistakes are less likely to happen). OTOH, it ties the hands
of the user: He *must* always allocate the data with 'new'. He can't,
for example, have an array of the data and give pointers to the data
elements to the tree (because then the tree would try to delete the
individual elements of the data, which is undefined behavior, afaik).
OTOH, if managing the data is left to the user then it becomes more
error-prone, as the user must be very careful when and how he deletes
the data.
Using smart pointers can alleviate this problem a bit, but OTOH it
would still be impossible to give temporaries or elements of an array to
the data container.

And of course there's the slight problem of memory usage (although
it's not such a big problem with a binary tree, as it's already using
quite a log of ancillary memory for each node): If you force the user to
allocate each object with 'new', that consumes additional RAM, compared
to the case where the object is directly stored in the tree node.

The approach of the STL containers is that they store copies of the
data objects in the data structure elements. It solves most
responsibility problems and in many cases it's much more
memory-efficient (std::vector and std::deque being good examples), and
it allows giving temporaries and local objects to the container. If
copying the objects is very heavy, the responsibility of making it
lighter is left to the user. (He can, for example, make the STL
container store pointers instead of instances if he wants.)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Foundations- Introduction to Program Design and Data Structures-project solutions available now. Contact instructors.team[at]gmail.com Pearson & prentice hall solutions C++ 0 06-20-2009 02:59 PM
Basic data structures question Justin To Ruby 2 06-10-2008 02:05 AM
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Design decisions on data structures asm C Programming 1 10-05-2004 01:38 AM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM



Advertisments