Почему `std :: priority_queue :: top ()` не может вернуть неконстантную ссылку? - PullRequest
Новая
       26

Почему `std :: priority_queue :: top ()` не может вернуть неконстантную ссылку?

0 голосов
/ 17 апреля 2020

Мне нужно поддерживать приоритетную очередь Q больших объектов (типа T). Поскольку эти объекты копируются дорого, я хотел бы иметь возможность получить доступный для записи объект с auto h = std::move(Q.top()). Но я не могу этого сделать, поскольку std::priority_queue<std::unique_ptr<T>>::top() возвращает только константную ссылку. Почему? (И есть ли простой обходной путь?)

Ответы [ 3 ]

1 голос
/ 17 апреля 2020

Вы можете сохранить большие объекты как unique_ptr<T> в очереди с приоритетами. Следует отметить, что queue.top() возвращает const unique_ptr<T>&, что означает, что сам T не const. Таким образом, вы можете сделать это: 

T obj(std::move(*queue.top()));
queue.pop();

Редактировать: Поскольку ваш T не имеет конструктора перемещения, я бы просто немного покусал пулю и использовал std::shared_ptr<T>: 

std::priority_queue<std::shared_ptr<T>, ...> queue;

// fill queue

// No need for anything special. 
std::shared_ptr<T> ptr = queue.top();
queue.pop();
0 голосов
/ 17 апреля 2020

Вы можете наследовать от priority_queue и написать T pop(), чтобы скрыть void pop()

template <typename T>
T fixed_priority_queue<T>::pop() {
    std::pop_heap(c.begin(), c.end(), comp); 
    T value = std::move(c.back());
    c.pop_back();
    return value;
}
0 голосов
/ 17 апреля 2020

Вы можете обернуть свой большой объект в дополнительную структуру, в которой будет поле, которое будет использоваться пользовательской функцией сравнения, на этот элемент не должны влиять операции move , например, это должен быть некоторый простой тип данных как int: 

struct BigObject {
    std::unique_ptr<int> data;
    int forCmp;
};

struct Cmp {
    bool operator()(const BigObject& lhs, const BigObject& rhs) {
        return lhs.forCmp < rhs.forCmp;
    }
};

после move(queue.top()) внутренний порядок очереди не может быть нарушен. Перемещенный экземпляр BigObject по-прежнему имеет действительное значение forCmp, используемое компаратором.

Затем наследуйте от priority_queue, выполнив это, вы получите доступ к контейнеру underyling c и добавите front метод: 

template<class T, class Cmp>
struct Wrapper : std::priority_queue<T,std::vector<T>,Cmp> {
    T& front() {
        return this->c.front();
    }
};

использование: 

Wrapper<BigObject,Cmp> q;
BigObject bo;
bo.forCmp = 12;
q.push(std::move(bo));

BigObject i = std::move(q.front());

Полная демонстрация

...