Doubly Linked List Using std::unique_ptr

3
votes

Anyone suggest an implementation? I tried this at home the other day and discovered the move semantics too difficult to establish a prior link or a simple linked list. Easy if making a tree using std::unique_ptr. Of course a std::shared_ptr makes an easy implementation of this question thanks to the copy/assign. So how about it?

3
c++unique-ptrdoubly-linked-list
Why is everyone voting to close? – Pubby
I voted for close because I didn't see any effort from the OP. No code posted what OP tried himself/herself. – Nawaz
@Nawaz That doesn't make it "not a real question". I would say downvote as "this question does not show any research effort", but then again, the second sentence says he spent time trying stuff out. But this isn't really a question about why his code, and so I fail to see why that's relevant. – Pubby
This is not a close question, it's a fine question. – Puppy
You mean using only unique_ptr? Seems impossible to me, since in a doubly linked list you have two pointers pointing to each element, and thus they cannot be both unique_ptrs. The alternative would be a list where the next are unique_ptrs, while the last are plain old pointers - I don't see much problems there at first sight. – Arne Mertz

3 Answers

5
votes

Since the question has been reopened, I'll post my comment as what I think is an answer:

If you mean using only unique_ptr, that will be impossible, since in a doubly linked list you have two pointers pointing to each element, and thus they cannot be both unique_ptrs. (That would contradict the unique part somehow...)

To clarify, let's consider a list of three elements: A <-> B <-> C Here A would contain a unique_ptr next, pointing to B and therefore owning B. C would have a unique_ptr prev, poiting to B as well - and owning it, too. Two unique_ptrs owning the same object is against unique_land's law, and you would have to put evil efforts in it to achieve it due to unique_ptr's move-only properties.

The alternative would be a list where the next pointers are unique_ptrs, while the last pointers are plain old C-pointers - I don't see much problems there, so I don't think that is what you wanted.

But if you had some thing like that "half unique list" in mind, provide some code and tell us, what you have problems with - we'll gladly help :)

0
votes

Here's what I use,

https://gist.github.com/mukunda-/153d802065c130e2956c

It is of course using the 'half-unique' method, since that is the only possible way.

What this does is it takes control of unique_ptr's given to it, and any interaction with the items in the list are done with normal pointers. If you pull an item out of the list, then you gain ownership.

Essentially, it gives you the convenience of auto deletion with smart pointers. Of course it will break if you delete the list object while you are working on one of the objects, in that case you would want a shared_ptr list.

0
votes

yes it can be done by using any of the pointer(next or prev) as unique_ptr and the other as raw pointer . Refer CppCon 2016: Herb Sutter “Leak-Freedom in C++... By Default.” CppCon 2016: Herb Sutter “Leak-Freedom in C++... By Default.”