Возможно, я не верно понимаю, суть priority_queue. Я ожидал очередь с приоритетом

#include <queue>

//свой предикат, а не std::less
class pred
{
public:
  bool operator()(int a, int b)
  {
    return a > b;
  }
};

int main(int argc, char* argv[])
{
  std::priority_queue<int,std::vector<int>,pred> pqueue;
  for (int i = 9; i > 0; --i)
  {
    pqueue.push(i);
  }
}

Ожидал: 1,2,3,4,5,6,7,8,9
Получил: 1,2,4,3,7,8,5,9,6

Почему?

Здравствуйте, BogusCoder, Вы писали:

BC>Возможно, я не верно понимаю, суть priority_queue. Я ожидал очередь с приоритетом
BC>Почему?

Судя по документации, требуется "binary predicate that induces a strict weak ordering in the standard mathematical sense. " Тогда вопрос уточняю, можно ли упорядочить очередь в неубывающем порядке?

Вместо std::priority_queue<int,std::vector<int>,pred>, я воспользовался std::set<int,pred>.
Пары push,pop заменил на insert, erase(begin()) соотвественно.
Есть ли более оптимальное решение?

Здравствуйте, BogusCoder, Вы писали:

BC>Судя по документации, требуется "binary predicate that induces a strict weak ordering in the standard mathematical sense. " Тогда вопрос уточняю, можно ли упорядочить очередь в неубывающем порядке?

На STLPort 5.2 приведенный код работает корректно. Какую версию STL используете? Проверьте нет ли ошибок в коде, считывающем значения из очереди.

Здравствуйте, BogusCoder, Вы писали:

BC>Ожидал: 1,2,3,4,5,6,7,8,9
BC>Получил: 1,2,4,3,7,8,5,9,6

BC>Почему?

priority_queue это вроде фибоначчиева куча, S[i]>=S[2i], S[i]>=S[2i+1]

Здравствуйте, Meer, Вы писали:

M>Здравствуйте, BogusCoder, Вы писали:

BC>>Судя по документации, требуется "binary predicate that induces a strict weak ordering in the standard mathematical sense. " Тогда вопрос уточняю, можно ли упорядочить очередь в неубывающем порядке?

M>На STLPort 5.2 приведенный код работает корректно. Какую версию STL используете? Проверьте нет ли ошибок в коде, считывающем значения из очереди.

Проверял в 2008 студии. Уже нашел свою проблему, в ДНК естественно. Я завязался на ту последовательность которую показывала студия, и совсе не подумал что доступ к элементам будет не порядке "слева-направо" а в порядке обхода кучи. ВОпрос снят

Здравствуйте, BogusCoder, Вы писали:

BC>Ожидал: 1,2,3,4,5,6,7,8,9
BC>Получил: 1,2,4,3,7,8,5,9,6
BC>Почему?

А в каком месте ты "получил"?
У тебя нет кода извлечения из очереди.

Очередь основана на пирамиде (heap) — специальным образом упорядоченном контейнере.
Добавление произвольного элемента в пирамиду и удаление головного ("наибольшего" в соответствии с предикатом) осуществляется за логарифмическое время, а прямой доступ к головному — за единичное (это головной элемент массива).

Если ты посмотрел дебаггером в содержимое контейнера — так всё правильно.
Содержимое очереди примерно так и выглядит.

А вот если ты начнёшь поштучно извлекать...
http://codepad.org/pKyewJHQ

int main(int argc, char* argv[])
{
  std::priority_queue<int,std::vector<int>, std::greater<int> > pqueue;
  cout << "push:";
  for (int i = 9; i > 0; --i)
  {
    cout << " " << i; // 9 8 7 6 5 4 3 2 1
    pqueue.push(i);
  }
  cout << endl;

  cout << "popp:";
  while(!pqueue.empty())
  {
    int t = pqueue.top();
    pqueue.pop();
    cout << " " << t; // 1 2 3 4 5 6 7 8 9
  }
  cout << endl;
}

И кстати, обрати внимание: есть такой предикат std::greater

Здравствуйте, MasterYoda, Вы писали:

MY>priority_queue это вроде фибоначчиева куча, S[i]>=S[2i], S[i]>=S[2i+1]

Двоичная куча. Фибоначчиева куча по-другому сбалансирована.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, BogusCoder, Вы писали:

BC>>Ожидал: 1,2,3,4,5,6,7,8,9
BC>>Получил: 1,2,4,3,7,8,5,9,6
BC>>Почему?

К>А в каком месте ты "получил"?
К>У тебя нет кода извлечения из очереди.

К>Очередь основана на пирамиде (heap) — специальным образом упорядоченном контейнере.
К>Добавление произвольного элемента в пирамиду и удаление головного ("наибольшего" в соответствии с предикатом) осуществляется за логарифмическое время, а прямой доступ к головному — за единичное (это головной элемент массива).

К>Если ты посмотрел дебаггером в содержимое контейнера — так всё правильно.
К>Содержимое очереди примерно так и выглядит.

К>А вот если ты начнёшь поштучно извлекать...
К>http://codepad.org/pKyewJHQ
К>

К>int main(int argc, char* argv[])
К>{
К>  std::priority_queue<int,std::vector<int>, std::greater<int> > pqueue;
К>  cout << "push:";
К>  for (int i = 9; i > 0; --i)
К>  {
К>    cout << " " << i; // 9 8 7 6 5 4 3 2 1
К>    pqueue.push(i);
К>  }
К>  cout << endl;

К>  cout << "popp:";
К>  while(!pqueue.empty())
К>  {
К>    int t = pqueue.top();
К>    pqueue.pop();
К>    cout << " " << t; // 1 2 3 4 5 6 7 8 9
К>  }
К>  cout << endl;
К>}
К>

К>И кстати, обрати внимание: есть такой предикат std::greater

Благодарю за ответ! Выше по ветке я уже упомянул, что ложно принял вывод дебаггера за истину, но все равно спасибо.
Предикат реально используется сложнее чем в примере, поcему std::greater мне был не нужен.