STL priority_queue копирует класс компаратора

Question

Я пытаюсь создать приоритетную очередь с помощью пользовательского компаратора:

std::priority_queue<int, std::vector<int>, MyComparator> pq;

Моя проблема в том, что в MyComparator есть метод, который хранит дополнительное состояние. Поскольку MyComparator копируется в приоритетную очередь (насколько я могу судить), я не могу вызвать этот метод в экземпляре MyComparator, который содержится в приоритетной очереди. Есть ли способ либо:

• получить доступ к экземпляру MyComparator, находящемуся в очереди с приоритетами, или:
• как-то передать исходный экземпляр MyComparator по ссылке

Answer 1

Объекты сравнения, используемые в контейнерах STL, а также предикаты, используемые в алгоритмах STL, должны быть копируемыми объектами и методами, и алгоритмы могут свободно копировать эти функции по своему усмотрению.

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

Если вы хотите, чтобы ваш объект сравнения содержал изменяемое состояние, тогда проблема является более сложной, поскольку любые копии объекта сравнения должны совместно использовать изменяемое состояние. Если вы можете поддерживать состояние как отдельный объект, тогда ваши объекты сравнения могут хранить указатель на это внешнее состояние; в противном случае вы, вероятно, обнаружите, что вам нужно совместное владение общим состоянием, поэтому вам, вероятно, потребуется что-то вроде tr1::shared_ptr для управления этим.

Answer 2

Я столкнулся с этим перед собой с аргументом шаблона компаратора std :: sort. Определение правильного конструктора копии должно помочь, например ::1001

class MyComparator
{
    public:

        MyComparator(const MyComparator& other)
        {
            // copy members
        }

        // ...
};

Если ваш класс компаратора не тяжелый (и если это так, то это приводит к множеству других вопросов ...), это не должно вызывать особых проблем.

Answer 3

Вы можете попробовать указать тип ссылки в шаблоне специализации:

std::priority_queue<int, std::vector<int>, MyComparator&> pq;

Но в IIRC есть случаи, когда это все еще не работает, и реализации STL в любом случае могут принудительно копировать. Я не уверен по вашему вопросу, может быть, вам нужно определить конструктор копирования / оператор присваивания, чтобы копировать любое внутреннее состояние, хотя это больно, если копировать дорого.

Answer 4

Это отвратительно, но вы можете дать вашему MyComparator член static MyComparator* me и затем перегрузить конструктор копирования, чтобы присвоить этот указатель this. Возможно, есть лучший способ, но ничего не приходит на ум.