Sign in to follow this  

Doubly-linked lists using references rather than pointers (C++)

This topic is 3281 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 :)

Share this post


Link to post
Share on other sites
Here you go..



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.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by rip-off
You couldn't implement a terminal value either - because a reference has to be valid.
Use a polymorphic node type [smile]


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;
}

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

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!

Share this post


Link to post
Share on other sites
Fair enough, I figured that was probably the case! I'll stick to pointers in this case.

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.

Share this post


Link to post
Share on other sites
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.


int& a = a;

Share this post


Link to post
Share on other sites
Yeah ... this post right here used to be the home of a real stupid-moment - which is what the next 2 posts from others are about. Anyway I deleted it so no one would get misinformed!!!

[Edited by - popsoftheyear on December 19, 2008 4:43:49 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by popsoftheyear
if you reassign the reference at some point (which is illegal... in fact I wonder why compilers don't check for this? Must be some good reason...)

What are you talking about? There is absolutely no way to reassign a reference. Do you mean code like this?

Foo& a = b;
a = c;

What happens here is that a is introduced as an alias for b, and in the second line c is assigned to b. The reference is not changed in any way by the second line.

Share this post


Link to post
Share on other sites
Quote:

Passing a reference is much safer because of the reasons you mentioned. But holding onto a reference might be considered more dangerous than holding onto a pointer because if you reassign the reference at some point (which is illegal... in fact I wonder why compilers don't check for this? Must be some good reason...), and you crash at some other point much later on when you go and use the reference, you are going to be quite dissappointed and may not figure out the bug for some time.


You can't reseat, or have "null" references in a well-formed C++ program. The only way to cause that to happen is by having previously invoked undefined behavior elsewhere -- at which point all bets (and guarantees) are off anyway.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Quote:
Original post by popsoftheyear
if you reassign the reference at some point (which is illegal... in fact I wonder why compilers don't check for this? Must be some good reason...)

What are you talking about? There is absolutely no way to reassign a reference. Do you mean code like this?

Foo& a = b;
a = c;

What happens here is that a is introduced as an alias for b, and in the second line c is assigned to b. The reference is not changed in any way by the second line.


Right... well don't I feel silly now? Something at some point in time drew that completely illogical conclusion in my mind and it never left. Anyway I deleted the above post in hopes no one reads it and gets misinformed... sorry 'bout that.

Share this post


Link to post
Share on other sites
Too late I'm afraid :P

But that's my point; I prefer references since they're harder to abuse than pointers. I just don't get how holding on to a reference is any worse than holding on to a pointer. Semantically it's the same thing, surely?

Share this post


Link to post
Share on other sites
Idiomatically when you use a reference there's the guarantee that the object bound to the reference must outlive the object that contains the reference. Since references can't be reseated, you can't delete the object that the reference refers to and reset the reference to a state where it isn't bound to any object. The entire point of using a reference is to say "this alias for an object is always valid". This sharply constrains the number of situations where holding a reference to an object makes sense.

Share this post


Link to post
Share on other sites

This topic is 3281 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this