Sorting a list of unique_ptrs

Question

The following code will not compile:

bool ptrLess(unique_ptr<int> ptr1, unique_ptr<int> ptr2)
{
   return *ptr1 < *ptr2;
}

int main()
{
   unique_ptr<int> ptr1(new int(3));
   unique_ptr<int> ptr2(new int(2));
   unique_ptr<int> ptr3(new int(5));
   list<unique_ptr<int>> list;

   list.push_back(ptr1);
   list.push_back(ptr2);
   list.push_back(ptr3);

   list.sort(ptrLess);

   for (auto &element : list) {
      cout << *element;
   }

   return 0;
}

I assume this is because unique_ptr's copy constructor is deleted. I get an error like:

error C2280: 'std::unique_ptr>::unique_ptr(const std::unique_ptr<_Ty,std::default_delete<_Ty>> &)': attempting to reference a deleted function

Is there any way to sort a list of unique_ptr's, perhaps by using the move constructor instead?

This looks a lot like trial-and-error C++, which does not tend to go too well. You should take a step back and systematically learn the language from a good book. — Baum mit Augen, May 20 '18 at 20:53
You can't copy unique_ptr's and ptrLess uses pass by value so would try to create copies. Change the arguments to const refs and it should work. — Ian4264, May 20 '18 at 20:59
@Ian4264 Would you mind creating an answer instead of a comment? I have a feeling the OP would appreciate sample code in the answer too. — Jens, May 20 '18 at 21:03
@BaummitAugen Could you please explain why this looks like trial-and-error? I have read Stroustrup's "The C++ Programming Language." I'll be honest I have only been learning C++ for a few months, but I do feel as though I understand the language pretty well. — Zach, May 20 '18 at 21:07
@Zach Ok, that's a useful book at least, so it looks like my comment was not accurate. Sorry. However, it is strange that a) your first idea when you want something sorted is to put it in a linked list and b) that your first guess for the argument type of a comparator is something other than `const &`. While it does have some oddities like his "range checked vector", I do not recall the book teaching any of that stuff wrong. — Baum mit Augen, May 20 '18 at 21:12
@BaummitAugen You're right, typically I would not used a linked-list if I needed to sort it later. However, this is for an exercise that my professor gave us where we need to use a linked-list for a particular algorithm. I was just wondering if I would be able to sort it at the end. — Zach, May 20 '18 at 21:20
btw, you also have the class `list` and a variable `list` in the same scope, that could easily cause problems for you — kmdreko, May 20 '18 at 21:21
@vu1p3n0x Thanks you're right. I typed this up really quickly in a couple of minutes to ask this question, so I totally missed that. — Zach, May 20 '18 at 21:23
@Zach Ok, then that might be your teacher's fault. As a word of advice: linked lists are very rarely useful these days because they are *awfully* slow in pretty much everything. And yes, that usually includes inserting in the middle; by the time you found the insertion point in the list, you would be long done with shifting around your `std::vector` elements. This is commonly underestimated by teaching staff it seems. — Baum mit Augen, May 20 '18 at 21:24
Note that if you were to use the move constructor for your `ptrLess`, then the `ptrLess` function would *own* the pointers it was comparing. Then, when the function was over, there would be no owner and the `unique_ptr` destructor would delete whatever was being pointed to. Your result would be a (technically sorted) list of null `unique_ptr`s. — Daniel H, May 20 '18 at 22:33
@BaummitAugen The performance of linked list will be poor if you use it for what it can't do well... — curiousguy, May 25 '18 at 16:15
@curiousguy Which sadly happens to apply to the vast majority of linked list use I've seen so far. Just saying you need to have a better reason than gut-profiling for picking lists over vectors, not that they are literally always the wrong choice. — Baum mit Augen, May 25 '18 at 16:29

joe_chip · Accepted Answer · 2018-05-20T22:17:10.407

5

You should use const ref - after all you don't want to modify those pointers:

bool ptrLess(const unique_ptr<int>& ptr1, const unique_ptr<int>& ptr2)

If your list template is std::list, then passing arguments as r-value references won't work - list::sort would have to call std::move effectively resetting your pointers.

Edit

As for list the rest of your code: std::list has a handy method called emplace_back (and emplace_front) which allows you to construct and append an element in-place:

your_list.emplace_back(new int(2));

edited May 20 '18 at 22:17

answered May 20 '18 at 21:05

joe_chip

2,468
1
12
23

And, _because of the way the list is declared_, it takes ownership of the object passed in, right? Neato, I like it, but (for me, at least) you need to make clear what that innocent looking one-liner actually does. It's [unusual](https://stackoverflow.com/questions/4303513/push-back-vs-emplace-back) to pass a newly-constructed object to that method (in this case it is passed on to `unique_ptr` as an argument to the constructor so it's OK, it will get deleted in due course). – Paul Sanders May 21 '18 at 08:42

Michael Beer · Answer 2 · 2018-05-20T21:23:31.707

Try this:

#include <memory>
#include <list>
#include <iostream>
using namespace ::std;

bool ptrLess(unique_ptr<int>& ptr1, unique_ptr<int>& ptr2)
{
   return *ptr1 < *ptr2;
}

int main()
{
   unique_ptr<int> ptr1(new int(3));
   unique_ptr<int> ptr2(new int(2));
   unique_ptr<int> ptr3(new int(5));
   list<unique_ptr<int>> list;

   list.push_back(move(ptr1));
   list.push_back(move(ptr2));
   list.push_back(move(ptr3));

   list.sort(ptrLess);

   for (auto &element : list) {
      cout << *element;
   }

   return 0;
}

The problem here is that you need to understand what a unique_ptr actually aims to be:

When dealing with pointers/references, there are a hell lot of potential problems arising if there are several pointersrs/references referring to the same object. unique_ptr tries to avoid precisely that. Therefore, you cannot create 2 unique_ptr referring to the same object.

You cannot use your ptrLess() function because calling it like

   unique_ptr<int> ptr1(new int(3));
   unique_ptr<int> ptr2(new int(2));

   ptrLess(ptr1, ptr2);

because this would mean ptr1 an ptr2 would have to be copied and passed over to ptrLess() - keyword here is 'call-by-value'.

Moreover, you cannot do

   list<unique_ptr<int>> list;
   unique_ptr<int> ptr1(new int(3));

   unique_ptr<int> ptr1(new int(3));

because this too, would have to create a copy of ptr1. The solution here is to not pass the unique_ptr s to ptrLess as values, but as reference:

bool ptrLess(unique_ptr<int>& ptr1, unique_ptr<int>& ptr2);

And you dont pass copies into the list, but move your object there:

list.push_back(move(ptr1));

keyword here is 'move-semantics'. This will invalidate the content of your ptr1 variable - the object has been moved out of ptr1 into the list.

I recommend having a look at the Rust language if you are more deeply interested in things like these ;)

As Baum mit Augen pointed out, the parameters to ptrLess better be declared as const:

bool ptrLess(const unique_ptr<int>& ptr1, const unique_ptr<int>& ptr2);

At least this compiles, but a comparator should not use non-const reference and, more importantly, using a linked list to sort some values is not the right approach. You should address and explain that. — Baum mit Augen, May 20 '18 at 21:16
You are right, my answer is not optimal - but I cannot unclude every aspect in the answer - otherwise I would end up like Donald Knuth ;) — Michael Beer, May 20 '18 at 21:19
Incorporated your remark about const parameters. Thanks for the hint! — Michael Beer, May 20 '18 at 21:23
@MichaelBeer: In depth detail somewhat somewhere and made jump over to Rust and finally the code compiled. — JeJo, May 20 '18 at 21:42
@BaummitAugen: Its all about ownership, one of Rusts core concepts ;) — Michael Beer, May 20 '18 at 21:46

score -1 · Answer 3 · answered May 20 '18 at 21:06

-1

Try passing by const ref so it won't copy the parameters : bool ptrLess(const unique_ptr& ptr1, const unique_ptr& ptr2) { return *ptr1 < *ptr2; }

answered May 20 '18 at 21:06

Ian4264

307
2
6

Paul Sanders · Answer 4 · 2018-05-23T07:53:46.330

-1

It occurs to me to suggest that if the OP uses shared_ptr instead of unique_ptr then the code as originally posted will otherwise run unchanged:

#include <memory>
#include <list>
#include <iostream>
using namespace ::std;

bool ptrLess(const shared_ptr<int>& ptr1, const shared_ptr<int>&  ptr2)
{
   return *ptr1 < *ptr2;
}

int main()
{
   shared_ptr<int> ptr1(new int(3));
   shared_ptr<int> ptr2(new int(2));
   shared_ptr<int> ptr3(new int(5));
   list<const shared_ptr<int>> list;

   list.push_back(ptr1);
   list.push_back(ptr2);
   list.push_back(ptr3);

   list.sort(ptrLess);

   for (auto &element : list) {
      cout << *element;
   }

   return 0;
}

Run it on Wandbox.

In some senses, this is a consistent way to do things. push_back would normally copy the object being added to the list, leaving the original object still available to the caller should he or she want to use it. Using shared_ptr has similar semantics without the overhead of copying the object itself. Instead, just the shared_ptr is copied, which is a cheap operation.

Also, modifying the OP's original code to move the unique_ptrs into the list is inherently fragile. They remain in scope to the caller but are no longer usable. You will get (I assume) a nullptr dereference if you try. Better then, to do this (note the extra set of braces):

...

list<unique_ptr<int>> list;

{
   unique_ptr<int> ptr1(new int(3));
   unique_ptr<int> ptr2(new int(2));
   unique_ptr<int> ptr3(new int(5));

   list.push_back(move(ptr1));
   list.push_back(move(ptr2));
   list.push_back(move(ptr3));
}

...

Now you are safe.

There, that's a much better post than the original version, sorry about that.

edited May 23 '18 at 07:53

answered May 20 '18 at 23:24

Paul Sanders

24,133
4
26
48

I was trying to provide the MCVE. It's for a project where I have to write a function that takes a list of unique_pointers of objects and performs an operation on it. I figured that it was unnecessary to talk about what the object was and what the operation is that I am performing (it happens to involve a sort). All I was asking was how to sort it. – Zach May 20 '18 at 23:54
There is absolutely no reason for `ptrLess` to have ownership of the pointers. Making them shared so it can own pointers it doesn't need to own is a bad idea; better to express the lack of ownership with `unique_ptr const&`. – Daniel H May 21 '18 at 01:35
@DanielH What you say about passing a const ref to `ptrLess` is quite right and I have amended my answer. But you have missed the point. The _list_ needs to ensure that the objects pushed onto it remain valid for as long as it needs access to them and that is precisely what `shared_ptr` is designed for. Using `unique_ptr` for any kind of object to be stored in an STL container is asking for trouble. Stop and think for a moment: what happens if the `unique_ptr` goes out of scope before the container does? – Paul Sanders May 21 '18 at 04:52
@PaulSanders If you have a list of `unique_ptr`s, the pointers *won't* go out of scope unless you remove them from the list or explicitly transfer them. The *list* owns the pointers; that's the point of them. It's a perfectly reasonable thing to do if for some reason you need to transfer the objects between containers without calling their move constructors, or the type you're pointing to doesn't fit all the requirements of the container, or probably other cases. It's not a usual thing to do because you'd usually just store the type directly and indirection costs overhead, but it isn't unsafe. – Daniel H May 21 '18 at 05:45
@Zach Sorry, I didn't mean to beat you up, I just wanted to point out that your list can just be a simple list of int's. Try implementing that - everything will get much simpler. – Paul Sanders May 21 '18 at 06:25
@PaulSanders To move from a `unique_ptr` you need to call `move`; it doesn't happen accidentally and you can deliberately break anything. The typical advice (eg. [CPP core guidelines F.27](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rf-shared_ptr), [GotW 89 Q. 1](https://herbsutter.com/2013/05/29/gotw-89-solution-smart-pointers/), [this CppCon talk](https://youtu.be/JfmTagWcqoE?t=2m43s)) is to use `shared_ptr` only when you *need* shared ownership; in this case, having the list own the `int`s is better (which is also why you prefer `list` to any sort of list of pointers). – Daniel H May 21 '18 at 06:55
@DanielH Oh right, if you move them in there then yes, sorry. That's fine as long as you don't need them for anything else. You have to be careful though. As you yourself pointed out above, passing (references to) unique_ptr's around is fragile, lest they get moved again. shared_ptr is flexible, safe and almost as efficient. – Paul Sanders May 21 '18 at 06:55
@DanielH Fair enough, I stand corrected. I guess, in any particular instance, it comes down to whether you want access to the objects after you have added them to the list or not, simple as that. – Paul Sanders May 21 '18 at 07:54
@PaulSanders All good. I know that a list of int's would be simpler. I purposely made it that way to reflect some code I have to complete for a project where I don't have a choice in the matter. – Zach May 22 '18 at 03:30
@Zach Cool, thank you. I think I underestimated you. – Paul Sanders May 22 '18 at 04:57
@DanielH I reworked my post, I'd be the first to admit that the tone was all wrong. Thanks for your input. I learnt a few things. – Paul Sanders May 23 '18 at 08:31

Sorting a list of unique_ptrs

4 Answers4