एसटीएल प्राथमिकता कतार - क्या यह संभव है?

Question

मुझे कुछ कक्षा संरचना में अपनी कक्षा ए ऑब्जेक्ट्स को स्टोर करने की आवश्यकता है। इसके अलावा, मैं उन्हें एक कुंजी के अनुसार स्वचालित रूप से सॉर्ट करना चाहता हूं, जो कि मेरे मामले में किसी अन्य वर्ग बी के एक एम्बेडेड ऑब्जेक्ट बी

इस प्रकार मैंने एसटीएल प्राथमिकता कतार का उपयोग करने का निर्णय लिया।

हालांकि यह संभव है कि 2 या अधिक ऑब्जेक्ट्स बी के समान कुंजी मान हों।

मेरे सवालों का:

एसटीएल प्राथमिकता कतार डुप्लिकेट चाबी सुविधा देता है ??

यदि मुझे ऐसा करना चाहिए और मुझे किस भविष्यवाणी का उपयोग करना चाहिए?

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

Answer 1

क्या एसटीएल प्राथमिकता कतार डुप्लिकेट कुंजी की अनुमति देती है ??

हां।

यदि यह है कि मैं क्या

पर विचार करना चाहिए बराबर तत्वों के बीच क्रम मनमाने ढंग से बदल सकता है कि नहीं करता है।

और मुझे किस भविष्यवाणी का उपयोग करना चाहिए?

इसका मतलब क्या है? यह पूरी तरह से आपके अर्थशास्त्र पर निर्भर करता है।

Answer 2

हां, यह डुप्लिकेट कुंजी का समर्थन करता है।

doucumentation से:

void push(const value_type& x) Inserts x into the priority_queue. 
           Postcondition: size() will be incremented by 1. 

एक साधारण परीक्षण यह पुष्टि करता है:

int main() { 
    priority_queue<int> q; 
    q.push(5); 
    q.push(5); 
    cout << q.top() << endl; 
    q.pop(); 
    cout << q.top() << endl; 
    q.pop(); 
} 

आउटपुट:

5 
5 

जो कुछ भी आप से पहले इस्तेमाल किया है | विधेय, उपयोग के लिए के रूप में - प्राथमिकता कतार द्वारा गारंटीकृत कुछ भी बराबर तत्वों को अनुमति देकर टूट जाता है, इसलिए आपके एल्गोरिदम को चाहिए ठीक काम करो।

Answer 3

कोनराड का एक बड़ा जवाब है, इसमें जोड़ने के लिए। आपको पता होना चाहिए कि प्राथमिकता_क्यू में जरूरी प्रदर्शन नहीं है। इस पृष्ठ के अनुसार http://www.cs.brown.edu/~jwicks/libstdc++/html_user/classstd_1_1priority__queue.html, ऐसा लगता है कि इसे उच्चतम प्राथमिकता प्राप्त करने के लिए सभी परिचालनों पर make_heap, pop_heap, आदि करके कार्यान्वित किया जाता है।

पुन: हेपिंग, आपके उपयोग के मामले के आधार पर अन्य डेटा संरचनाओं की तुलना में महंगा हो सकता है।