приоритета реализация очереди объяснение

Question

Я читал алгоритм Дейкстров из книги конкурентного программирования 1.In программы внедрения они написали что-то вроде этого:

#define pair<int,int> ii; 
priority_queue< ii,vector<ii>,greater<ii> > pq ; 

Если мы берем целое число S в качестве источника, реализации показывает нажать пару (стоимость, источник), как это (узлы пронумерованы от 1 до п):

pq.push(ii(0,s)) ; 

Моего вопроса мы толкаем пару стоимости и узла в приоритетной очереди. Но что делают два других параметра (а именно вектор и больше) в объявлении priority_queue?

priority_queue< ii,vector<ii>,greater<ii> > pq ; 

Я попытался объявить что-то вроде:

priority_queue<ii> pq ; 

А код работает (на тех testcases я пробовал).

Может кто-нибудь сказать мне, что они имели в виду декларации:

priority_queue< ii,vector<ii>,greater<ii> > pq ; 

А в чем разница между верхней декларацией и

priority_queue<ii> pq ; 

декларации?

Answer 1

Так декларация класса шаблона является чем-то вроде этого:

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

Там должны быть три параметра шаблона. Первый, «T», является типом элементов (ii в вашем случае). Второй параметр - это то, что я назвал «базовым контейнером». Вы видите, priority_queue является адаптером, то есть он использует другие контейнеры в тайне, представляя вам другой набор операций. (Возможно, вы захотите найти «шаблон адаптера» в wikipedia.) Что касается соображений производительности, вы можете сообщить компилятору, какой контейнер он должен использовать под ним. Классы, deque и vector из стандартной библиотеки могут быть использованы. См. here для требований к классу контейнеров.

Теперь компаратор - это то, что вы используете для определения порядка ваших элементов. Это может быть либо указатель на функцию, либо класс с перегруженным оператором. Он принимает два аргумента вашего типа элемента и возвращает (bool) «true», если первый элемент должен появиться после второго в очереди. Это полезно, когда вы хотите изменить порядок по умолчанию или использовать некоторые экзотические способы упорядочения своих элементов.

например. см ниже простейшего примера

struct car{ 
    car(double engine_displ):_engine_displ(engine_displ) {} 
    double _engine_displ; 
}; 
bool cmp_cars(car one, car other){ 
    return one._engine_displ < other._engine_displ; 
} 
//..somewhere else 
std::priority_queue<car, std::vector<car>, cmp_cars> pq; 

очередь должна затем провести std::vector -ful автомобилей, отсортированных по смещению двигателя.

Когда в списке аргументов шаблона есть что-то вроде class Container = vector<T>, компилятор заполняет std::vector<T> для вас, если вы не скажете, что такое ваш основной тип контейнера. Вот почему вы можете просто сказать priority_queue<ii>; компилятор расширяет его до priority_queue<ii,vector<ii>,less<ii>>. В вашем примере автор книги явно использует greater<ii>, поэтому очередь должна помещать наименьший элемент спереди.Это имеет смысл, поскольку в алгоритме Дейкстры вы заинтересованы в пути, который имеет наименьшую стоимость. priority_queue<ii> использует less<ii> по умолчанию, так что теперь очередь поставит путь с самой большой косой впереди, что не имеет смысла.

В качестве побочного примечания вы можете обнаружить, что код на самом деле typedef pair<int,int> ii. Директива #define сообщает препроцессору заменить каждый pair<int,int> на «ii», что совсем не помогает. Typedef сообщает компилятору «ii» значение pait<int,int>.