Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Are raw pointers acceptable when used only internally within a class implementation?
75 views
Skip to first unread message
kurt krueckeberg
Sep 11, 2014, 6:04:27 PM9/11/14
to
I have implemented a 2 3 4 tree using raw pointers. The Node234 class has a Node234 *parent member variable. Is there any reason to use managed pointer is the raw pointers are only used internally and never exposed to clients. The class looks like this. shared_ptr<Node234> seems like needless overhead?
template<typename K> class Tree234 {
protected:
class Node234; // forward declaration of nested class.
Node234 *root;
void split(Node234 *node); // called during insert to split 4-nodes
void DestroyTree(Node234 *root);
Node234 *convertTwoNode(Node234 *node);
Node234 *fuseSiblings(Node234 *parent, int node2_id, int sibling_id);
Node234 *doRotation(Node234 *parent, int node2_id, int sibling_id);
// snip...
class Node234 {
private:
friend class Tree234<K>;
static int MAX_KEYS;
Node234 *parent;
int totalItems; /* If 1, two node; if 2, three node; if 3, four node. */
K keys[3];
Node234 *children[4];
Node234(K small);
Node234(K small, K larger);
Node234(K small, K middle, K large);
void connectChild(int childNum, Node234 *child);
bool searchNode(K key, int& index, Node234 *&next);
Node234 *disconnectChild(int child_index);
void insertChild(int childNum, Node234 *pChild);
// snip ...
public:
int getTotalItems() const;
bool isLeaf() const;
//.. snip...
};
public:
Tree234() { root = nullptr; }
~Tree234();
bool search(K key);
template<typename Functor> void traverse(Functor f);
template<typename Functor> void postOrderTraverse(Functor f);
void insert(K key);
bool remove(K key);
};
template<typename K> class Tree234 {
protected:
class Node234; // forward declaration of nested class.
Node234 *root;
void split(Node234 *node); // called during insert to split 4-nodes
void DestroyTree(Node234 *root);
Node234 *convertTwoNode(Node234 *node);
Node234 *fuseSiblings(Node234 *parent, int node2_id, int sibling_id);
Node234 *doRotation(Node234 *parent, int node2_id, int sibling_id);
// snip...
class Node234 {
private:
friend class Tree234<K>;
static int MAX_KEYS;
Node234 *parent;
int totalItems; /* If 1, two node; if 2, three node; if 3, four node. */
K keys[3];
Node234 *children[4];
Node234(K small);
Node234(K small, K larger);
Node234(K small, K middle, K large);
void connectChild(int childNum, Node234 *child);
bool searchNode(K key, int& index, Node234 *&next);
Node234 *disconnectChild(int child_index);
void insertChild(int childNum, Node234 *pChild);
// snip ...
public:
int getTotalItems() const;
bool isLeaf() const;
//.. snip...
};
public:
Tree234() { root = nullptr; }
~Tree234();
bool search(K key);
template<typename Functor> void traverse(Functor f);
template<typename Functor> void postOrderTraverse(Functor f);
void insert(K key);
bool remove(K key);
};
Mr Flibble
Sep 11, 2014, 6:12:33 PM9/11/14
to
On 11/09/2014 23:04, kurt krueckeberg wrote:
> Is there any reason to use managed pointer is the raw pointers are only used internally and never exposed to clients.
No.
> Is there any reason to use managed pointer is the raw pointers are only used internally and never exposed to clients.
/Flibble
Christopher Pisz
Sep 11, 2014, 6:18:16 PM9/11/14
to
because they exist. I've encountered as many circular reference leaks as
I have leaks from raw pointers. Either way, understand and verify when
memory is allocated and when memory is released, even if using a ref
counting or shared pointer, verify it actually got released.
Martijn Lievaart
Sep 12, 2014, 3:25:22 AM9/12/14
to
On Thu, 11 Sep 2014 15:04:01 -0700, kurt krueckeberg wrote:
> I have implemented a 2 3 4 tree using raw pointers. The Node234 class
> has a Node234 *parent member variable. Is there any reason to use
> managed pointer is the raw pointers are only used internally and never
> exposed to clients. The class looks like this. shared_ptr<Node234> seems
> like needless overhead?
It would have masked the problem. Using unique_ptr<> would have exposed
> I have implemented a 2 3 4 tree using raw pointers. The Node234 class
> has a Node234 *parent member variable. Is there any reason to use
> managed pointer is the raw pointers are only used internally and never
> exposed to clients. The class looks like this. shared_ptr<Node234> seems
> like needless overhead?
the problem more.
>
> template<typename K> class Tree234 {
> protected:
> public:
> Tree234() { root = nullptr; }
> ~Tree234();
Where is operator=() ??
> Tree234() { root = nullptr; }
> ~Tree234();
M4
R. Schubert
Sep 12, 2014, 7:56:56 AM9/12/14
to
Smart pointers make sense whenever a pointer owns the resource they point to (i.e. whenever it would be used in a call to delete later on), whether it is a single owner expressed through the use of unique_ptr or shared ownership using shared_ptr.
For automatic resource management, you could make root and children unique_ptr, if, which I am guessing is the case, they will only belong to one tree.
The parent pointer, however, does not own the pointed-to resource, so it should be a plain pointer. Since we expect the parent to always outlive its children, you should not encounter any dangling pointers there, assuming they are correctly tracked through rotations and the like.
Also, as Martijn Lievaart pointed out, whenever you have (owning) pointer members, you should really think about copy behaviour, either forbidding it (by deleting the copy constructor and assignment operator), making a exlicit deep copy or by doing whatever else is appropriate.
Using smart pointers here would also tackle this issue, as they would inject their default behavior into your class: making root a unique_ptr implicitly forbids copying and assignment because its own copy constructor and assignment operator are deleted, while making it a shared_ptr would share it among copies.
For automatic resource management, you could make root and children unique_ptr, if, which I am guessing is the case, they will only belong to one tree.
The parent pointer, however, does not own the pointed-to resource, so it should be a plain pointer. Since we expect the parent to always outlive its children, you should not encounter any dangling pointers there, assuming they are correctly tracked through rotations and the like.
Also, as Martijn Lievaart pointed out, whenever you have (owning) pointer members, you should really think about copy behaviour, either forbidding it (by deleting the copy constructor and assignment operator), making a exlicit deep copy or by doing whatever else is appropriate.
Using smart pointers here would also tackle this issue, as they would inject their default behavior into your class: making root a unique_ptr implicitly forbids copying and assignment because its own copy constructor and assignment operator are deleted, while making it a shared_ptr would share it among copies.
CHIN Dihedral
Sep 12, 2014, 1:48:57 PM9/12/14
to
to replace the old boring tree opererations in C++?
kurt krueckeberg
Sep 12, 2014, 1:49:05 PM9/12/14
to
> > Tree234() { root = nullptr; }
>
> > ~Tree234();
>
> Where is operator=() ??
>
I didn't bother to implement operator=() or a copy constructor.
>
> > ~Tree234();
>
> Where is operator=() ??
>
CHIN Dihedral
Sep 14, 2014, 1:35:47 PM9/14/14
to
On Friday, September 12, 2014 6:04:27 AM UTC+8, kurt krueckeberg wrote:
with at most 4 son-nodes.
Us an unsigned char string that
could be extended in the string length,
and 2 bits per level of tree from
the translated key 0 as the root node.
I wrote that long time ago in C.
0 new messages