ошибка очереди приоритета

Question

У меня возникают проблемы. Всякий раз, когда я пытаюсь скомпилировать эту программу, я получаю сообщение об ошибке в функции contains, где указано q.pop. Если эта строка закомментирована, она будет компилироваться отлично, но она все еще дает неправильное значение. По какой-то причине это всегда ложно.

Ошибки:
priority_queue_demo.cpp: In function 'int main()': priority_queue_demo.cpp:54:12: error: invalid conversion from 'int' to 'const char*' [-fpermissive] /usr/lib/gcc/x86_64-redhat-linux/4.6.1/../../../../include/c++/4.6.1/bits/basic_string.tcc:214:5: error: initializing argument 1 of 'std::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT*, const _Alloc&) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>]' [-fpermissive] priority_queue_demo.cpp: In function 'bool contains(const std::priority_queue<T>&, T) [with T = int, typename std::vector<T, std::allocator<_Tp1> >::value_type = int]': priority_queue_demo.cpp:43:47: instantiated from here priority_queue_demo.cpp:27:3: error: passing 'const std::priority_queue<int>' as 'this' argument of 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = int, _Sequence = std::vector<int, std::allocator<int> >, _Compare = std::less<int>]' discards qualifiers [-fpermissive]

#include <iostream> 
#include <string> 
#include <sstream> 

#include <queue> 

using namespace std; 

template <typename T> 
ostream &operator <<(ostream &os, priority_queue<T> &q) { 
     os << "{"; 
     while (!q.empty()) { 
       os << q.top() << (!q.empty() ? ", " : ""); 
       q.pop(); 
     } 

     os << "}"; 

     return os; 
} 

template <typename T> 
bool contains(const priority_queue<T> &q, T val) { 
     for (int i = 0; i < q.size(); i++) { 
       if (q.top() == val) return true; 
       q.pop(); 
     } 

     return false; 
} 

int main() { 
     cout << boolalpha; 

     priority_queue<int> qi; 

     for (int i = 0; i < 20; i++) 
       qi.push(i); 

     cout << qi << endl; 

     cout << "qi contians 15: " << contains(qi, 15) << endl; 
     cout << "qi contians 23: " << contains(qi, 23) << endl; 

     const int ARR_SIZE = 4; 
     string arr[ARR_SIZE] = {"cat", "dog", "cow", "elephant"}; 

     cout << endl; 

     priority_queue<string> qs; 

     for(int i = 0; i < ARR_SIZE; i++) 
       qs.push(i); 

     cout << qs << endl; 

     while(!qs.empty()) { 
       qs.pop(); 
       cout << qs << endl; 
     } 


     return 0; 
} 

Answer 1

Проблема заключается в том, что вы передаете const ссылки на очередь, но pop() явно не const операции, так как он мутирует очередь.

Вы должны пройти неконстантную ссылка:

bool contains(priority_queue<T>& q, T val) { .... } 

Как вы можете видеть, вы не можете действительно проверить содержимое очереди, не изменяя его.

Следующая ошибка в том, что вы толкая целое число в очереди std::string:

qi.push(i); 

Вы, вероятно, означает

qi.push(arr[i]); 

Примечание ваша перегрузка ostream& operator<< для очереди опорожняет очереди , поэтому любая попытка использовать contains после печати очереди до std::cout даст ложь независимо от исходного содержимого очереди.

См. Демонстрационный файл here.

Answer 2

У вас есть несколько проблем в коде:

priority_queue<string> qs; 

    for(int i = 0; i < ARR_SIZE; i++) 
      qs.push(i); //<<<<Error, should be arr[i] 

Вы действительно должны толкать arr[i] не i поскольку i является целым числом в то время как он ожидает string.

Вы передаете priority_queue со ссылкой на перегруженной функции << оператора , который удаляет все элементы в priority_queue, поэтому весь ваш запрос contains станет false.

Вы также можете использовать const priority_queue<T>& в contains функции, однако, функция pop() не const, что приводит к ошибке компиляции, как указывал juanchopanza.

Answer 3

Я сделал комментарий раньше, но есть и другие проблемы с кодом, которые не соответствуют комментариям.

1)qs является priority_queue<string> но подталкивают int с до него (в строке qs.push(i)); Я предполагаю, что вы хотели сделать, это нажать arr[i].Следовательно, заменить

qs.push(i); 

с

qs.push(arr[i]); 

2) функции шаблона contains принять priority_queue<T> по константной ссылке. Это означает, что вы не можете вызвать методы const на q. В частности, вы не можете позвонить q.pop(), потому что pop() является методом non const. (На самом деле, этот метод, как ожидается, чтобы изменить очередь). Таким образом, замените

template <typename T> 
bool contains(const priority_queue<T> &q, T val) { 

с

template <typename T> 
bool contains(priority_queue<T> &q, T val) {