Checking position of newly added unique_ptr to priority_queue

Question

I am switching my design to use smart pointers and I've encountered a problem with std::priority_que

I had a method that inserts new task into queue and signalizes if new task landed at the top of it:

bool foo(SchedulerTask* task)
{
  eventList_.push(task);
  return task == eventList_.top();
}

After wrapping SchedulerTask into unique_ptr I met problem with checking its priority in container. After moving the object into queue I was not able to use it again for compare. I have end up with caching comparator member and comparing it with the top object:

bool foo(std::unique_ptr<SchedulerTask> task)
{
  const auto prio = task->getCycle(); // my priority_queue compares objects by getCycle() value

  eventList_.push(std::move(task));

  return prio >= eventList_.top()->getCycle();;
}

Can it be done better way?

Have you tried caching and comparing the native pointer, like in the smart-less version? There is no law that says that you can't `get()` the unique_ptr, and as long as it still exists, `get()` it again and compare notes. That's what `get()` is there for. P.S. pointer comparison is unspecified behavior in C++ in this context, and you'll have to do a little bit of work if you want to go strictly by the book. — Sam Varshavchik, Feb 17 '20 at 12:03
@SamVarshavchik I don't see what is unspecified, the standard says: Comparing pointers is defined as follows: (3.1) If one pointer represents the address of a complete object, and another pointer represents the address one past the last element of a different complete object,79 the result of the comparison is unspecified. (3.2) Otherwise, if the pointers are both null, both point to the same function, or both represent the same address, they compare equal. (3.3) Otherwise, the pointers compare unequal. — n314159, Feb 17 '20 at 12:51
@n314159 - see https://stackoverflow.com/questions/31774683/is-pointer-comparison-undefined-or-unspecified-behavior-in-c — Sam Varshavchik, Feb 17 '20 at 13:22
@SamVarshavchik If I see that right the linked question is about subtraction and relational comparison not plain and simple equality comparison. — n314159, Feb 17 '20 at 14:52
@SamVarshavchik I did. The second quote (the first is about subtraction) is an excerpt from [[expr.rel] Relational operators](http://eel.is/c++draft/expr.rel), not from [[expr.eq] Equality Operators](http://eel.is/c++draft/expr.eq). It only handles `<, >, <=, >=`. It explicitly states that the equality comparison is defined in the next subsection ("If two operands p and q compare equal (5.10), ..."). There you will find my quote from above, that states that equality comparison will work. (The links are to a newer standard than quoted in the answer, but nothing significant changed) — n314159, Feb 17 '20 at 17:22

score 1 · Answer 1 · answered Feb 17 '20 at 12:06

As @Sam Varschavchik hinted at, you can compare to the raw pointer. I.e. you'd do something like:

bool foo (std::unique_ptr<SchedulerTask> task) {
  auto const * taskPtr = task.get();
  eventList_.push(std::move(task));
  return taskPtr == eventList_.top().get();
}

score 0 · Answer 2 · answered Feb 17 '20 at 12:08

0

Two sad ways to solve this would be:

1.

bool foo(std::unique_ptr<SchedulerTask> task)
{
  SchedularTask* tmp = task.get();
  eventList_.push(std::move(task));
  return tmp == eventList_.top().get();
}

2.

bool foo(std::unique_ptr<SchedulerTask> task)
{
  std::unique_ptr<SchedularTask> tmp(task.get());
  eventList_.push(std::move(task));
  bool ret = (tmp == eventList_.top());
  tmp.release();
  return ret;
}

answered Feb 17 '20 at 12:08

theWiseBro

1,439
12
11

Your second suggestion is going to cause a double deletion of whatever `task` is pointing to. You have two `std::unique_ptr` managing the same `SchedulerTask` object. – AVH Feb 17 '20 at 13:37
@Darhuuk i release the ownership of the object before returning - `tmp.release()`. So no. – theWiseBro Feb 17 '20 at 14:18

score 0 · Answer 3 · answered Feb 17 '20 at 16:19

You can also check before adding the task if it will end up in front:

// Assumes eventList_ uses a stateless Comparator of type Cmp
bool foo(std::unique_ptr<SchedulerTask> task)
{
  bool greater = Cmp{}(eventList_.top(), task); 

  eventList_.push(std::move(task));

  return greater;
}

Of course this can be a wrong result in a multi-threaded context, since eventList_ can change between the check and the push. But the same can happen for a check afterwards and this has to be caught by a lock.

score 0 · Answer 4 · answered Feb 18 '20 at 08:34

Use a shared pointer

You could use a shared ownership pointer type. That is, just use a std::shared_ptr instead. That one won't have the same issue at all. The code then is almost as before:

bool foo(std::shared_ptr<SchedulerTask> task)
{
  eventList_.push(task);
  return task == eventList_.top();
}

Use a proxy with id

Your issue is basicly this: once you move the unique pointer into the container, you no longer can identify it. Therefore, another solution could be to stick with the std::unique_ptr but add a mechanism of unique identification. This could be in a proxy type of object:

struct SchedulerTaskInfo {
  std::unique_ptr<SchedulerTask> task_;
  int id_;
};

Now you can compare using the id_:

bool foo(SchedulerTaskInfo task)
{
  eventList_.push(std::move(task));
  return task.id_ == eventList_.top().id_;
}

You could even create the operator== on the proxy if you wanted.

Checking position of newly added unique_ptr to priority_queue

4 Answers4

Use a shared pointer

Use a proxy with id