Doubly-linked lists using references rather than pointers (C++)
Author
Just a thought; how would I implement a doubly-linked list where each node stores its previous and next nodes by reference? Since the references must be set in the node constructor, there is a two-way dependency between one node and the next, so the list's creator would need to construct all nodes simultaneously!
I guess I'm barking up the wrong tree and that you nice people will tell me to use pointers or smart pointers instead, but I shall ask anyway, just in case everything I know is wrong :)
Here you go..
Yes, this is a silly post.
template <class T>struct Reference { T &value Reference(T &v) : value(v) {}};template <class T>struct LinkedListNode { Reference<T> *left; Reference<T> *right; LinkedListNode() : left(NULL), right(NULL) {} void setLeft(T &v) { delete left; left = new Reference<T>(v); } void setRight(T &v) { delete right; right = new Reference<T>(v); } };Yes, this is a silly post.
Quote:Original post by rip-offUse a polymorphic node type [smile]
You couldn't implement a terminal value either - because a reference has to be valid.
Quote:Original post by ToohrVykQuote:Original post by rip-offUse a polymorphic node type [smile]
You couldn't implement a terminal value either - because a reference has to be valid.
Or a singleton....
struct Node { explicit Node(const Node & n) : next_(n) {} static const Node & null_node() { static Node instance; return instance; } bool has_next() const { return !(next_ == null_node().next_); } const Node & next() const { return next_; }private: friend bool operator==(const Node & lhs, const Node & rhs); Node() : next_(null_node()) {} const Node & next_;};bool operator==(const Node & lhs, const Node & rhs) { return (&lhs.next_ == &rhs.next_);}int count(const Node & n) { return n.has_next() ? (count(n.next()) + 1) : 1;}int main(int argv, char **){ Node a(Node::null_node()); Node b(a); Node c(b); Node d(c); std::cout << count(d) << std::endl;}Quote:Original post by hymerman
how would I implement a doubly-linked list where each node stores its previous and next nodes by reference?
Storing things by reference is very seldomly a good idea. You aren't meant to hold on to references. Use pointers.
References were introduced into the language to support operator overloading for user-defined types better, so you could write expressions like b + c instead of *b + *c.
Arg... that looks dangerously close to undefined behaviour Antheus. It seems like you are using a reference before it is initialised, because we are still in the process of initialising it.
I am probably wrong though.
But I will concede that it is a beautiful method, undefined behaviour or not!
I am probably wrong though.
struct Node { explicit Node(const Node & n) : next_(n) {} static const Node & null_node() { static Node instance; if(!finished) { std::cout << "returning a reference to an uninitialised value\n"; } return instance; } bool has_next() const { return !(next_ == null_node().next_); } const Node & next() const { return next_; }private: friend bool operator==(const Node & lhs, const Node & rhs); Node() : next_(null_node()) { finished = true; } const Node & next_; static bool finished;};bool Node::finished = false;bool operator==(const Node & lhs, const Node & rhs) { return (&lhs.next_ == &rhs.next_);}int count(const Node & n) { return n.has_next() ? (count(n.next()) + 1) : 1;}int main(int argv, char **){ Node a(Node::null_node()); Node b(a); Node c(b); Node d(c); std::cout << count(d) << std::endl;}But I will concede that it is a beautiful method, undefined behaviour or not!
Author
Fair enough, I figured that was probably the case! I'll stick to pointers in this case.
Why is that, exactly? Holding on to either is dangerous in exactly the same way (can point to invalid object), what makes references worse? I prefer references since they can't be NULL and are guaranteed to be initialised.
Quote:Original post by DevFred
Storing things by reference is very seldomly a good idea. You aren't meant to hold on to references. Use pointers.
Why is that, exactly? Holding on to either is dangerous in exactly the same way (can point to invalid object), what makes references worse? I prefer references since they can't be NULL and are guaranteed to be initialised.
I would guess it depends. If the code guarantees that the reference stays valid for the lifetime of the object it might be OK (e.g a member of a class has a reference to the instance that contains it).
Be warned, though, that through programmer errors it is perfectly possible to obtain invalid and uninitialized references.
Be warned, though, that through programmer errors it is perfectly possible to obtain invalid and uninitialized references.
int& a = a; This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
