Doubly Linked List Using std::unique_ptr

Question

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?

Comedic

Why is everyone voting to close? – Tamas

I voted for close because I didn't see any effort from the OP. No code posted what OP tried himself/herself. – Uralian

@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. – Tamas

If you read correctly, I wrote the code at home, tried it, but discovered the move semantics made an implementation real hard to near impossible. I will re-post this question again because of the child-like nature of some to vote a post closed. If this is possible, then I want to know because I enjoy a challenge and this was quite challenging for me. – Comedic

@user633658: Post the code (what you tried yourself) next time, and be specific when stating the problem. – Uralian

This is not a close question, it's a fine question. – Niel

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. – Swivel

@Arne Mertz Well, this kind of feedback to my question is what I would be looking for prior to the old grumpy egotistical readers voting the question closed. I would reopen a similar question to get more feedback but these idiots would just vote it closed again ... turds! – Comedic

just 1 more vote for reopening it ;) – Swivel

@Nawaz No reason to post code because I am asking you if you can implement a doubly-linked list using only unique-ptrs. I already tried it at home and found it too difficult. If you fail to read the question, your problem. – Comedic

@user633658: It is NOT my need. So it is not "my" problem. Period. – Uralian

Answer 1

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

Swivel

A half-unique list was not in mind. I can build a doubly-linked list out of C-pointers using dynamic memory through new easy. It is also easy to provide an implementation using std::shared_ptr. This is not the problem. I did not post code because I already attempted this at home with no success and had to resort to std::shared_ptr. My question is if someone knows how to implement a doubly-linked list using only std::unique_ptr. I was only able to create a "half-list"solution as I found the move mechanics insufficient. Is there a way to do this? Good answer for providing partial-unique. – Comedic

See first part of my answer. I put in a paragraph for clarification why it's impossible to have a unique_ptr-only-list. – Swivel

Then this is the answer I seek. I thank you for providing it. If anyone else thinks they can implement a doubly-linked list with just std::unique_ptr, please feel free post a solution. – Comedic

What to do if we want to add dummy node? We have unique_ptr on dummy node from last node and from head - it seems not good. – Aristophanes

@Gusev Slava where do you want to add the dummy node? Could you provide some code that shows the problem? – Swivel

@ArneMertz I post question here: #50974493 – Aristophanes

Answer 2

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.”

Burkitt

Answer 3

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.

Tragedienne