приоритетная очередь для алгоритма Дейкстры [закрыта]

Как работает приоритетная очередь? Я начал изучать алгоритм Дейкстры, погуглил и получил много кода, где разные кодеры использовали разные версии приоритетных очередей. В одном коде я заметил, что он использует это объявление

priority_queue <pii, vector <pii>, comp> Q;
//pii means pair <int,int>
// And comp is compare structure  which I also cannot understand

Комп идет так

struct comp {
  bool operator() (const pii &a, const pii &b) {
    return a.second > b.second;
  }
};

Кто-нибудь может объяснить мне, что здесь происходит? Также, сколько версий объявлений priority_queue существует в С++?


c++ dijkstra
person run_time_error    schedule 26.12.2013    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Очередь приоритетов C++:

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

В этом:

T — тип, который будет храниться в очереди; надеюсь, это достаточно ясно.

Container — это базовое хранилище в очереди. Как видно из объявления, по умолчанию это std::vector<T>, и обычно его можно игнорировать.

Compare' is the method for determining the ordering in the queue. Again, it has a default and can often be ignored.Compare` — это тип, поддерживающий вызов функции, которая может сравнивать два элемента в очереди и определять их порядок.

less используется по умолчанию и просто применяет обычный оператор <.

Когда кто-то хочет порядок, отличный от определенного <, он определяет тип, который обеспечивает необходимое сравнение. Как у вас:

struct comp {
  bool operator() (const pii &a, const pii &b) {
    return a.second > b.second;
  }
};

Обратите внимание, как это принимает два pii и сравнивается с использованием оператора >; это дает обратный порядок в очереди по умолчанию.

Затем этот тип comp указывается в качестве третьего параметра шаблона.

Затем, указав третий параметр, с шаблонами, как и с функциями, второй параметр также должен быть указан, даже если мы хотим только то же самое, что и по умолчанию, std::vector<pii>.

Зачем нужна спецификация базового контейнера? Это шаблон container adaptor. Идея состоит в том, что семантика приоритетных очередей не обязательно подразумевает лежащий в основе способ хранения данных. Также стандарт предоставляет ряд структур данных, специально предназначенных для хранения. Поэтому, почему бы Priority_queue не разрешить выбор базового хранилища? Это концепция адаптера.

person Keith    schedule 03.01.2014

arrow_upward
0
arrow_downward

Проверьте это

а также проверьте этот алгоритм Дейкстры - в С++?

person sachin10    schedule 26.12.2013
comment
На самом деле, я ранее обращался за помощью к первому сайту. Не могли бы вы рассказать мне, для чего используется вектор внутри объявления? Вот этот вектор беспокоит меня больше всего. Спасибо еще раз - person run_time_error; 26.12.2013

arrow_upward
0
arrow_downward

Если вы прочтете справку по priority_queue, вы увидите, что первый аргумент имеет тип а второй аргумент — это контейнер, а третий — класс сравнения. Кроме того, насколько я знаю, в стандарте C++ существует только одна приоритетная очередь, я реализовал свою собственную очередь, используя двоичное дерево поиска, что является очень полезным упражнением, которое я рекомендую.

В примере с алгоритмом Дейкстры в блоге zobayer все это немного запутано из-за использования макросов в коде. Жаль, что этот код настолько запутан, что за ним труднее следить.

В классе comp (структура — это класс со всеми открытыми членами по умолчанию) оператор () просто берет второй элемент в паре pii и сравнивает его с другим pii. Вы можете настроить это так, чтобы ваш тип находился в вашей очереди приоритетов.

person JHagdahl    schedule 03.01.2014