2010-12-19 28 views
43

क्या मैं एक मानक priority_queue या मानक queue को सी ++ में एक इटरेटर (जैसे vector) से पार कर सकता हूं? मैं पॉप का उपयोग नहीं करना चाहता क्योंकि यह मेरी कतार को अस्वीकार कर देता है।प्राथमिकता_क्यू पर फिर से कैसे करें?

किसी भी मदद के लिए धन्यवाद

उत्तर

2

यह संभव नहीं है। आपको एक अलग कंटेनर का उपयोग करना होगा, शायद deque आपको सर्वश्रेष्ठ सेवा प्रदान करेगा।

+1

कुछ भी संभव है, लेकिन कुछ चीजें अव्यवस्थित हैं। – Richard

11

queue उद्देश्य से सीमित इंटरफ़ेस प्रदान करता है, जिसमें पुनरावृत्ति शामिल नहीं है। लेकिन चूंकि queue अंतर्निहित कंटेनर के रूप में deque का उपयोग करता है, तो deque का उपयोग क्यों न करें?

#include <iostream> 
#include <queue> 
using namespace std; 

int main() { 
    deque<int> q; 
    q.push_back(1); 
    q.push_back(2); 
    q.push_back(3); 
    for(deque<int>::iterator it = q.begin(); it != q.end(); ++it) 
    cout << *it << endl; 
} 

प्राथमिकता कतार के लिए समान उत्तर: नहीं, आप नहीं कर सकते। हालांकि इस मामले में, vector डिफ़ॉल्ट रूप से उपयोग किया जाता है। किसी भी मामले में आप अंतर्निहित कंटेनर को फिर से चलाने के लिए उपयोग नहीं कर सकते हैं। आगे पढ़ने के लिए this question देखें।

+2

मैंने सोचा कि मैं आपके प्रश्न का उत्तर दूंगा "क्यों डेक का उपयोग सीधे नहीं करें?" मेरे परिदृश्य में, मैं कार्यान्वयन को प्रभावित किए बिना प्राथमिकता_क्यू की सामग्री को लॉग करना चाहता हूं (प्रकार को बदलकर)। यह एक लॉगिंग प्रयास है, जहां प्रदर्शन महत्वपूर्ण नहीं है, इसलिए एक प्रतिलिपि बनाना ठीक काम करेगा। –

5

हां, प्राथमिकता_क्यू की एक प्रति बनाएं और उस पर पुनरावृत्ति करें।

+8

प्रदर्शन एक चिंता का विषय नहीं है, तो एक उचित विचार की तरह लगता है। यदि आप कोड स्निपेट प्रदान करते हैं तो आपको मेरा अपवॉट मिल जाएगा। –

1

कतार वैक्टर से बिल्कुल अलग हैं और विभिन्न उद्देश्यों के लिए उपयोग की जाती हैं। प्राथमिकता कतारों को सीधे डेक को सॉर्ट किया जाता है, बिना किसी सीधी पहुंच के। हालांकि, यदि आप जो कुछ भी विधि के लिए करना चाहते हैं, तो आप शीर्ष/फ्रंट तत्व को पॉप कर सकते हैं, इसे किसी सूची/सरणी/वेक्टर में जोड़ें, और उसके बाद तत्व को अपनी कतार में वापस धक्का दें (size_t i = 0; मैं < q.size(); i ++)। मैंने जावा डेटा संरचनाओं में एक कक्षा ली, और यह एक परीक्षा प्रश्न का उत्तर था। इसके अलावा यह एकमात्र तरीका है जिसे मैं सोच सकता हूं।

10

आप इसे इस तरह कर सकते हैं - बम! ध्यान दें कि कंटेनर के सीधे-आगे पुनरावृत्ति के संबंध में, कतार में रहते समय आइटम क्रमबद्ध रूप से "क्रमबद्ध" क्रम में नहीं होते हैं।

#include <queue> 
#include <cstdlib> 
#include <iostream> 
using namespace std; 

template <class T, class S, class C> 
S& Container(priority_queue<T, S, C>& q) { 
    struct HackedQueue : private priority_queue<T, S, C> { 
     static S& Container(priority_queue<T, S, C>& q) { 
      return q.*&HackedQueue::c; 
     } 
    }; 
    return HackedQueue::Container(q); 
} 

int main() 
{ 
    priority_queue<int> pq; 
    vector<int> &tasks = Container(pq); 

    cout<<"Putting numbers into the queue"<<endl; 
    for(int i=0;i<20;i++){ 
     int temp=rand(); 
     cout<<temp<<endl; 
     pq.push(temp); 
    } 

    cout<<endl<<"Reading numbers in the queue"<<endl; 
    for(vector<int>::iterator i=tasks.begin();i!=tasks.end();i++) 
     cout<<*i<<endl; 

    cout<<endl<<"Taking numbers out of the queue"<<endl; 
    while(!pq.empty()){ 
     int temp=pq.top(); 
     pq.pop(); 
     cout<<temp<<endl; 
    } 

    return 0; 
} 
+2

subclassing std :: कंटेनर खतरनाक/गलत है क्योंकि उनमें वर्चुअल विनाशकों की कमी है। – imallett

+0

तो इस उदाहरण में मेमोरी लीकिंग है क्योंकि 'std :: कंटेनर' subclassing खतरनाक/गलत है क्योंकि उनमें वर्चुअल विनाशक की कमी है? –

-1

मैं एक ही समस्या है, जहां मैं dequeuing (इसलिए मेरी कतार को नष्ट करने) के बिना एक प्राथमिकता कतार से अधिक पुनरावृति करना चाहता था था। मैंने अपने प्राथमिकता_क्यू पॉइंटर को वेक्टर में पॉइंटर को दोबारा जोड़कर मेरे लिए काम किया (क्योंकि मेरे priority_queue वेक्टर को इसके कंटेनर के रूप में उपयोग करता है)। के बाद से मैं reinterpret_cast उपयोग कर रहा हूँ, लोगों के बारे में टाइप सुरक्षा का तर्क कर सकते हैं

class PriorityQueue { 
    private: 
    class Element { 
    int x; 
    //Other fields 
    ... 
    .. 
    //Comparator function 
    bool operator()(const Element* e1, const Element* e2) const { 
     // Smallest deadline value has highest priority. 
     return e1->x > e2->x; 
    } 
    }; 
    // Lock to make sure no other thread/function is modifying the queue 
    // Ofcourse we can do our operation w/o lock. if we are sure what is happening in other functions 
    pthread_mutex_t lock; 
    std::priority_queue<Element*, std::vector<Element*>, Element> pq; 

    public: 
    PriorityQueue(); 
    ~PriorityQueue(); 
    //print the all the elements of the queue 
    void print_queue_elements() { 
     std::vector<PriorityQueue::Element*> *queue_vector; 
     //Acquire the lock 
     pthread_mutex_lock(&lock); 
     //recast the priority queue to vector 
     queue_vector = reinterpret_cast<std::vector<PriorityQueue::Element*> *>(&pq); 
     for(std::vector<PriorityQueue::Element*>::iterator it = (*queue_vector).begin(); it != (*queue_vector).end(); it++) { 
      //Assuming Element class has string function 
      printf("My Element %s", (*it)->string); 
      //other processing with queue elements 
     } 
     //Release the lock 
     pthread_mutex_unlock(&lock);  

    } 
    //other functions possibly modifying the priority queue 
    ... 
    .. 
    . 
}; 

अब यहां तरीका देखें: यह की तरह लग रहा है। लेकिन इस मामले में मुझे यकीन है कि कतार तक पहुंचने/बदलने वाले सभी अन्य कार्यों के बारे में निश्चित है (जिनमें से सभी सुरक्षित हैं) .. और मुझे लगता है कि यह पूरे कतार की सामग्री को किसी अन्य कंटेनर में कॉपी करने से कहीं बेहतर तरीका है।

मैं वास्तव में काम करने के लिए static_cast की अपेक्षा कर रहा था .. प्राथमिकता_क्यू कंटेनर (हमारे मामले में वेक्टर) पर एडाप्टर है, लेकिन ऐसा नहीं है और मुझे reinterpret_cast का उपयोग करना पड़ा।

1

मुझे यह आपके प्रश्न पर ठोकर खाने के बाद मिला। Std :: primary_queue से विरासत में प्राप्त कार्यान्वयन लिखकर ऐसा करने का एक बहुत ही सरल तरीका है। यह सभी 14 लाइनें हैं।

http://www.linuxtopia.org/online_books/programming_books/c++_practical_programming/c++_practical_programming_189.html

5
क्योंकि यह अमान्य में बहुत आसान होती है (तत्वों आप पार संशोधित करके) कतार की प्राथमिकता आदेश या हो सकता है कि यह एक "नहीं है

priority_queue सभी सदस्यों के माध्यम से यात्रा की अनुमति नहीं है, शायद मेरी नौकरी "तर्क।

सरकारी काम के आसपास के बजाय एक vector का उपयोग करें और प्रबंधन करने के लिए है अपने आप को make_heap, push_heap और pop_heap साथ प्राथमिकता-साय। @ रिचर्ड के जवाब में, एक और काम, priority_queue से प्राप्त कक्षा का उपयोग करना और अंतर्निहित भंडारण तक पहुंचना है जिसमें protected दृश्यता है।

0

मेरे पास एक ही सवाल था। मैंने पाया कि प्राथमिकता कतार के अंतर्गत डेटा संरचना को प्राप्त करना बहुत मुश्किल था, शायद असंभव था। मेरे मामले में यह वस्तुओं का एक वेक्टर था।

हालांकि, मैं एक मानक टेम्पलेट लाइब्रेरी ढेर का उपयोग कर समाप्त हुआ। यह प्राथमिकता कतार के रूप में लगभग आसान है (इसे पुक और पॉप के लिए दो निर्देश लेते हैं, पीक्यू के लिए बनाम 1), अन्यथा व्यवहार समान और जैसा लगता है कि मैं अंतर्निहित डेटा संरचना में प्राप्त कर सकता हूं यदि मैं नहीं करता इसे संशोधित करें।

+0

मैंने अभी देखा है कि उत्तर कतार में मेरे ऊपर वाला व्यक्ति वही उत्तर देता है, और यह बेहतर करता है! –

2
#include <queue> 
#include <iostream> 

int main() { 
    std::priority_queue<int> pq; 

    pq.push_back(1); 
    pq.push_back(2); 
    pq.push_back(3); 

    std::priority_queue<int> temp = pq; 

    while (!temp.empty()) { 
     std::cout << temp.top() << std::endl; 
     temp.pop(); 
    } 

    return 0; 
} 
0

सी ++ priority_queue एक .begin() सूचक (सदिश की तरह करना होगा) कि आप इस पर पुनरावृति करने के लिए उपयोग कर सकते हैं प्रदान नहीं करता है।

यदि आप प्राथमिकता कतार में पुनरावृत्ति करना चाहते हैं तो यह पता लगाने के लिए कि इसमें कोई मान है या नहीं, तो शायद एक रैपर प्राथमिकता कतार बनाएं और कतार में आपके पास क्या है इसका ट्रैक रखने के लिए हैश सेट का उपयोग करें।

class MyPriorityQueue { 

    MyPriorityQueue() {} 

    void push(int item) { 
    if (!contains(item)){ 
     pq_.push(item); 
     set_.emplace(item); 
    } 
    } 
    void pop() { 
    if (!empty()) { 
     int top = pq_.top(); 
     set_.erase(top); 
     pq_.pop(); 
    } 
    } 
    int top() { return pq_.top(); } 
    bool contains(int item) { return set_.find(item) != set_.end(); } 
    bool empty() const { return set_.empty(); } 

private: 
    std::priority_queue<int> pq_; 
    std::unordered_set<int> set_; 
}; 
0

इनमें से कई उत्तर कोडिंग/सी ++ आर्केन सुविधाओं का उपयोग करके भरोसा करते हैं। यह ठीक है, मज़ा और धन महंगे प्रोग्रामर। एक सीधा समाधान है कि, जल्दी कार्यक्रम के लिए सस्ती लेकिन चलाने के लिए और अधिक महंगा है, यह है:

// 
// Only use this routine when developing code, NOT for production use!! 
// 
// Note. _pq is in private for a class that uses the priority queue 
// and listQueue is a public method in that same class. 
// 
void listQueue() { 

    // allocate pointer to a NEW container 
    priority_queue<int>* new_pq = new priority_queue<int>; 

    while (!_pq->empty()) { 

     int el = _pq->top(); 

     cout << "(" << el << ")" << endl; 

     new_pq->push(el); 

     _pq->pop(); 

    } // end while; 

    // remove container storage 
    delete(_pq); 

    // viola, new container same as the old 
    _pq = new_pq; 

} // end of listQueue; 

वैसे, यह पूरी तरह गैर समझदार लगता है नहीं एक priority_queue के लिए एक इटरेटर प्रदान करते हैं, खासकर जब यह एक कंटेनर है एक या संरचना के लिए कक्षा।

संबंधित मुद्दे