Нельзя просто так взять и priority_queue of unique_ptr ...

priority_queue у меня используется для хранения заданий (BaseTask), упорядочиваемых по времени (BaseTask::get_scheduled_time).

Поэтому, как я понимаю, у меня остается выбор:
1) Использовать указатели
2) shared_ptr
3) unique_ptr (больше всего подходит по смыслу, потому что указатели на задачи нет смысла шарить)

Но с unqiue ptr такая беда...

Подскажите, как такое "идиоматически выдержанно " делать в C++ 14?

Заранее благодарю!

Здравствуйте, MarcoPolo, Вы писали:

MP>Нельзя просто так взять и priority_queue of unique_ptr ...

MP>Подскажите, как такое "идиоматически выдержанно " делать в C++ 14?

На Stackoverflow в принципе ответили, на ваш вопрос. Еще можно снять константность со ссылки результата `queue::top()`. Это должно быть безопасно, если не планируется менять ключ объекта по которому упорядочены элементы priority queue:

https://ideone.com/c47H9D

#include <iostream>
#include <memory>
#include <queue>

int main ()
{
    auto const less = [](std::unique_ptr<int> const& x, std::unique_ptr<int> const& y)
    {
        return x && y && (*x < *y);
    };
    using container = std::vector<std::unique_ptr<int>>;
    std::priority_queue<std::unique_ptr<int>, container, decltype(less)> queue(less);
    
    queue.push(std::make_unique<int>(24));
    queue.push(std::make_unique<int>(42));
    queue.push(std::make_unique<int>(11));

    while (!queue.empty()) 
    {
        std::unique_ptr<int>& top = const_cast<std::unique_ptr<int>&>(queue.top());
        std::unique_ptr<int> myInt = std::move(top);

        queue.pop();
        std::cout << *myInt << '\n';
        if (*myInt == 24) queue.push(std::make_unique<int>(33)); 
    }
}

Здравствуйте, PM, Вы писали:

PM>На Stackoverflow в принципе ответили, на ваш вопрос. Еще можно снять константность со ссылки результата `queue::top()`. Это должно быть безопасно, если не планируется менять ключ объекта по которому упорядочены элементы priority queue:

std::move изменяет значение верхнего элемента heap-структуры что нарушает инвариант и можешь сломать pop()

Здравствуйте, 5.März, Вы писали:

5M>std::move изменяет значение верхнего элемента heap-структуры что нарушает инвариант и можешь сломать pop()

std::move ничего менять не может в принципе, а вот move конструктор может.

Здравствуйте, PM, Вы писали:

PM>Еще можно снять константность со ссылки результата `queue::top()`. Это должно быть безопасно, если не планируется менять ключ объекта по которому упорядочены элементы priority queue:

А с чем будет сравниваться следующий вставляемый элемент в очередь? Очередь с приоритетами, это по сути — heap. При вставке нового элемента сравнение может происходить с любым из элементов уже размещенных в куче, в том числе и с "головой".

Здравствуйте, MarcoPolo, Вы писали:

MP>Нельзя просто так взять и priority_queue of unique_ptr ...

MP>priority_queue у меня используется для хранения заданий (BaseTask), упорядочиваемых по времени (BaseTask::get_scheduled_time).

Тут возникает встречный вопрос: если у вас BaseTask не нужно ни с кем разделять, то зачем вам обязательно извлекать BaseTask из priority_queue перед использованием, а не после? Вот так же пример со Stackoverflow будет работать:

#include <queue>

int main ()
{
  std::priority_queue<std::unique_ptr<int>> queue;
  queue.push(std::unique_ptr<int>(new int(42)));

  const std::unique_ptr<int> & myInt = queue.top();
  return *myInt;
}

Т.е. получили константную ссылку на unique_ptr<BaseTask>, поработали с ним, затем вызывали pop у priority_queue.

Если же BaseTask обязательно нужно извлечь из очереди перед использованием, a shared_ptr<BaseTask> по каким-то причинам не устраивает, то напрашивается хранение в очереди не unique_ptr<BaseTask> напрямую, а специальной обертки. Что-то типа:

class ScheduledTaskInfo {
  mutable unique_ptr<BaseTask> task_;
  Timepoint scheduled_time_;
public:
  ScheduledTaskInfo(unique_ptr<BaseTask> task) noexcept
    : task_{std::move(task)}
    , scheduled_time_{task_->get_scheduled_time()}
  {}

  auto giveaway_task() const noexcept { return std::move(task_); }

  friend bool operator<(
    const ScheduledTaskInfo & a,
    const ScheduledTaskInfo & b) noexcept {
    return a.scheduled_time_ < b.scheduled_time_;
  }
};
...
std::priority_queue<ScheduledTaskInfo> queue;
...
auto task = queue.top().giveaway_task();
queue.pop();
taks->do_something();

Здравствуйте, 5.März, Вы писали:

5M>Здравствуйте, PM, Вы писали:

PM>>На Stackoverflow в принципе ответили, на ваш вопрос. Еще можно снять константность со ссылки результата `queue::top()`. Это должно быть безопасно, если не планируется менять ключ объекта по которому упорядочены элементы priority queue:

5M>std::move изменяет значение верхнего элемента heap-структуры что нарушает инвариант и можешь сломать pop()

Это зависит от компаратора, используемого в heap. В моем примере инвариант не нарушается.

Здравствуйте, Videoman, Вы писали:

PM>>Еще можно снять константность со ссылки результата `queue::top()`. Это должно быть безопасно, если не планируется менять ключ объекта по которому упорядочены элементы priority queue:

V>А с чем будет сравниваться следующий вставляемый элемент в очередь? Очередь с приоритетами, это по сути — heap. При вставке нового элемента сравнение может происходить с любым из элементов уже размещенных в куче, в том числе и с "головой".

Если оператор сравнения, используемый для упорядочивания элементов кучи не нарушает инвариант, то это безопасно:

struct item
{
    int key;
    std::string data;
    bool operator<(item const& that) const { return key < that.key; }
};

std::priority_queue<item> pq;
pq.emplace(1, "str1");
pq.emplace(2, "str2");

const_cast<item&>(pq.top()).data = "no problem";

Здравствуйте, PM, Вы писали:

PM>Если оператор сравнения, используемый для упорядочивания элементов кучи не нарушает инвариант, то это безопасно...

Вы правы, но поскольку автор не привел всего кода, лучше такие экзотические примеры не рассматривать. Автор явно пытается перемещать сразу весь объект. Что после этого будет? — остается только гадать.

Здравствуйте, MarcoPolo, Вы писали:

MP>Подскажите, как такое "идиоматически выдержанно " делать в C++ 14?

Проблема, как я понимаю, в том, что top не получается достать из очереди с отдачей владения. Можно на top посмотреть, и можно его уничтожить.
По идее это же просто очередные проявления того старого косяка контейнеров stl, что в них нельзя хранить объекты, копии которых различимы.

Ну проще всего складывать в очередь что-то такое, что можно копировать.
Например, можно складывать задания в лежащий рядом с очередью std::list, а вместо указателя на задание, использовать его итератор в списке.
Тогда, вынутые и обработанные задания грохнет из списка тот, кто вынимает, а те, что остались почему-то в очереди, грохнет при разрушении всего этого хозяйства сам список...

Здравствуйте, Erop, Вы писали:

E>По идее это же просто очередные проявления того старого косяка контейнеров stl, что в них нельзя хранить объекты, копии которых различимы.

Не уверен, что в данном случае это косяк. Очередь использует компаратор элементов, чтобы показать тебе top. Если поменяешь top или украдешь его кишки, то поломаешь инвариант контейнера.

Здравствуйте, andyp, Вы писали:

A>Не уверен, что в данном случае это косяк. Очередь использует компаратор элементов, чтобы показать тебе top. Если поменяешь top или украдешь его кишки, то поломаешь инвариант контейнера.
Ну это особенность проектирования. Что мешало добавить в очередь не только возможность создавать элемент на месте, но и вынимать его с возможностью дальнейшего move или swap, не особо понятно.
Но в STL это последовательное решение было, которое потом ослабили всякими там emplace, но всё равно методы вроде datach_top как-то не особо во всех контейнерах предусмотрели

Здравствуйте, Erop, Вы писали:


E>Ну это особенность проектирования. Что мешало добавить в очередь не только возможность создавать элемент на месте, но и вынимать его с возможностью дальнейшего move или swap, не особо понятно.
E>Но в STL это последовательное решение было, которое потом ослабили всякими там emplace, но всё равно методы вроде datach_top как-то не особо во всех контейнерах предусмотрели

Дизайн STL, на сколько помню, предполагал что элементы контейнера будут по крайней мере Regular, что в последнее время все чаще не выполняется. Суют абы что

Ведь и контейнер перестает быть Regular, если его элементы не являются объектами регулярных типов. Я бы всё-таки смотрел на emplace как на возможность оптимизации, а не как на возможность хранения move only типов. Вроде ж в стандарте нигде не написано, что копи-конструктор вектора может отваливаться в зависимости от типа элементов.

Ну и штуки типа detach_top, помимо логарифмической сложности, что в общем не беда, именно поэтому не предусмотрены имхо — не собираются отказываться от регулярности элементов.