Переместить элемент std priority_queue в C++11

Question

Минимальный рабочий пример.

#include <cassert>
#include <list>
#include <queue>
//#define USE_PQ

struct MyClass
{
    const char* str;
    MyClass(const char* _str) : str(_str) {}
    MyClass(MyClass&& src) { str = src.str; src.str = nullptr; }
    MyClass(const MyClass&) = delete;
};

struct cmp_func
{
    bool operator() (const MyClass&, const MyClass&) const
    {
        return true;
    }
};

typedef std::priority_queue<MyClass, std::vector<MyClass>, cmp_func> pq_type;

#ifdef USE_PQ
MyClass remove_front(pq_type& l)
{
    MyClass moved = std::move(l.top());
    // error from the above line:
    // use of deleted function ‘MyClass::MyClass(const MyClass&)’
    l.pop();
    return std::move(moved);
}
#else
MyClass remove_front(std::list<MyClass>& l)
{
    MyClass moved = std::move(l.front());
    l.erase(l.begin());
    return std::move(moved);
}
#endif

int main()
{
    const char* hello_str = "Hello World!";
    MyClass first(hello_str);
#ifdef USE_PQ
    pq_type l;
    l.push(std::move(first));
    MyClass moved = remove_front(l);
#else
    std::list<MyClass> l;
    l.push_back(std::move(first));
    MyClass moved = remove_front(l);
#endif
    assert(moved.str);
    assert(!first.str);
    return 0;
}

Так что это работает. Теперь удалите знаки комментария из строки 4, и он говорит, что понадобятся конструкторы копирования (мой удален). Кроме того, он пропускает operator=, Вопросы:

• Какая здесь разница?
• Можно ли решить проблему? Если да, то как, если нет, то почему бы и нет?

Примечание: вы также можете использовать boost_queue для вашего ответа, но я получил ту же ошибку с ним.

Answer 1

Это, кажется, упущение в дизайне std::priority_queue<T>, Похоже, нет способа напрямую переместить (не скопировать) элемент из него. Проблема в том, что top() возвращает const T&, так что не может связываться с T&&, А также pop() возвращается voidтак что вы тоже не можете получить это.

Тем не менее, есть обходной путь. Это так же хорошо, как гарантировано, что объекты внутри очереди приоритетов на самом деле не const, Это обычные объекты, очередь просто не дает к ним изменяемого доступа. Поэтому это совершенно законно:

MyClass moved = std::move(const_cast<MyClass&>(l.top()));
l.pop();

Как отметил @DyP в комментариях, вы должны убедиться, что перемещенный объект все еще жизнеспособен для передачи в компаратор очереди. И я считаю, что для того, чтобы сохранить предварительные условия очереди, он должен был бы сравнить то же, что и раньше (чего почти невозможно достичь).

Поэтому вы должны инкапсулировать cast & top() а также pop() вызывает функцию и следит за тем, чтобы никакие изменения в очереди не происходили между ними. Если вы сделаете это, вы можете быть уверены, что компаратор не будет вызван для объекта, который был удален.

И, конечно, такая функция должна быть чрезвычайно хорошо документирована.

---

Обратите внимание, что всякий раз, когда вы предоставляете пользовательский конструктор копирования / перемещения для класса, вы должны также предоставлять соответствующий оператор присваивания копирования / перемещения (в противном случае класс может вести себя непоследовательно). Так что просто предоставьте вашему классу оператор присваивания удаленной копии и соответствующий оператор присваивания перемещения.

_{(Примечание: да, есть ситуации, когда вы хотите создать конструируемый для перемещения, но не назначаемый для перемещения класс, но они чрезвычайно редки (и вы узнаете их, если когда-нибудь их найдете). Как правило, всегда обеспечить ctor и назначение op одновременно)}

Answer 2

Это легко продлить std::priority_queue, поскольку он выставляет нижележащий контейнер как защищенный элемент:

template <
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>>
class extended_priority_queue : public std::priority_queue<T, Container, Compare> {
public:
  T top_and_pop() {
    std::pop_heap(c.begin(), c.end(), comp);
    T value = std::move(c.back());
    c.pop_back();
    return value;
  }

protected:
  using std::priority_queue<T, Container, Compare>::c;
  using std::priority_queue<T, Container, Compare>::comp;
};

Если вам нужно переместить элемент из std::priority_queue Например, вы могли бы использовать extended_priority_queue реализовать вспомогательную функцию:

template<typename PriorityQueue>
auto priority_queue_top_and_pop(PriorityQueue& queue) ->
    typename PriorityQueue::value_type {
  return static_cast<extended_priority_queue<
      typename PriorityQueue::value_type,
      typename PriorityQueue::container_type,
      typename PriorityQueue::value_compare>&>(queue).top_and_pop();
}

Answer 3

В зависимости от того, какой тип вы хотите сохранить в очереди приоритетов, альтернатива решению Angew, которое позволяет избежать const_cast и удаляет некоторые возможности для стрельбы себе в ногу, будет заключаться в том, чтобы обернуть элемент типа следующим образом:

struct Item {
    mutable MyClass element;
    int priority; // Could be any less-than-comparable type.

    // Must not touch "element".
    bool operator<(const Item& i) const { return priority < i.priority; }
};

Перемещение элемента из очереди будет сделано следующим образом:

MyClass moved = std::move(l.top().element);
l.pop();

Таким образом, нет особых требований к семантике перемещения MyClass чтобы сохранить отношение порядка в недействительном объекте, и не будет секции кода, в которой инварианты приоритетной очереди будут недействительными.

Answer 4

Может быть очень веская причина, по которой не существует (const-ref) top(): изменение объекта нарушит инвариант priority_queue. Так что трюк с const_cast, вероятно, сработает только после того, как вы попадите сразу

Answer 5

Какая здесь разница?

MyClass remove_front(pq_type& l)
{
    MyClass moved = std::move(l.top()); // PROBLEM
    l.pop();
    return std::move(moved);
}

std::priority_queue::top возвращает const value_type&, так что вы не можете позвонить std::move (который занимает T&&).

MyClass remove_front(std::list<MyClass>& l)
{
    MyClass moved = std::move(l.front());
    l.erase(l.begin());
    return std::move(moved);
}

std::list::front имеет перегрузку, которая возвращает ссылку, поэтому у него есть способ привязать к T&&,

Я не уверен почему top не имеет неконстантной перегрузки (потенциально недосмотр в стандарте?). Ты можешь использовать const_cast чтобы обойти это, но не забудьте написать подробные комментарии, описывающие, что вы делаете и почему.

Answer 6

Ответ с лучшим рейтингом выглядит хорошо, но, к сожалению, он несовместим с -D_GLIBCXX_DEBUG, Пример:

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

struct T {
  int x;
  std::shared_ptr<int> ptr;
  T(int x, std::shared_ptr<int> ptr) : x(x), ptr(ptr) {}
};
struct Compare {
  bool operator()(const T& x, const T& y) {
    return *x.ptr < *y.ptr;
  }
};
int main() {
  auto ptr1 = std::make_shared<int>(3);
  auto ptr2 = std::make_shared<int>(3);
  std::priority_queue<T, std::vector<T>, Compare> f;
  f.emplace(3, ptr1);
  f.emplace(4, ptr2);
  T moved = std::move(const_cast<T&>(f.top()));
  f.pop();
  std::cerr << moved.x << "\n";
}

Если вы запустите это с g++ foo.cpp -D_GLIBCXX_DEBUG -O0 -g -std=c++11 && ./a.out в GCC (не clang, макрос в этом случае ничего не сделает) вы вызовете разыменование нулевого указателя в компараторе.