Jump to content
  • Advertisement
Sign in to follow this  
hymerman

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

This topic is 3644 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
Advertisement
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 rip-off
You couldn't implement a terminal value either - because a reference has to be valid.
Use a polymorphic node type [smile]

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!