24
मेरे पास कुछ ऑब्जेक्ट की प्राथमिकता_क्यू है:एसटीएल प्राथमिकता_क्यू में एक कुशल प्राथमिकता अद्यतन कैसे करें?
typedef priority_queue<Object> Queue;
Queue queue;
समय-समय पर, ऑब्जेक्ट्स में से किसी एक की प्राथमिकता बदल सकती है - मुझे कतार में उस ऑब्जेक्ट की प्राथमिकता को एक कुशल तरीके से अपडेट करने में सक्षम होना चाहिए । वर्तमान में मैं इस विधि का उपयोग कर रहा हूं जो काम करता है लेकिन अक्षम लगता है:
Queue newQueue;
while (!queue.empty())
{
Object obj=queue.top();
queue.pop();
if (priorityHasChanged(obj))
newQueue.push_back(Object(new_priority));
else
newQueue.push_back(obj);
}
newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
// class and exposed a swap method that swaps in the container
मैंने इसे इस तरह कार्यान्वित किया क्योंकि मैं उस समय जल्दी में था और यह सबसे तेज़ चीज थी जो मैं कर सकता था कि मैं इसे सुनिश्चित कर सकता था ठीक काम करेगा। हालांकि इसके मुकाबले बेहतर तरीका होना चाहिए। वास्तव में जो मैं चाहता हूं वह एक तरीका है:
- बदली हुई प्राथमिकता के साथ उदाहरण निकालें और नई प्राथमिकता मान
- के साथ एक नया डालें बदली प्राथमिकता के साथ उदाहरण अद्यतन करें और फिर कतार को अद्यतन करें कि यह सही ढंग से क्रमबद्ध है
ऐसा करने का सबसे अच्छा तरीका क्या है?
यह सही नहीं है - मानक प्राथमिकता कतार कंटेनर को संरक्षित सदस्य 'c' के रूप में संग्रहीत करती है (देखें [संदर्भ] (http://en.cppreference.com/w/cpp/container/priority_queue))। आप प्राथमिकता कतार से प्राप्त कर सकते हैं और व्युत्पन्न कक्षा में कंटेनर तक पहुंच सकते हैं। –
@ user283145 सुनिश्चित करें कि आप 'c' के साथ अंतर्निहित ढेर तक पहुंच प्राप्त कर सकते हैं, लेकिन चूंकि आप ओ (लॉग इन) में किसी कुंजी की अनुक्रमणिका नहीं पा रहे हैं, तो आप O (lgn) में प्राथमिकता अद्यतन नहीं कर सकते जो वास्तव में है दुर्भाग्यपूर्ण हिस्सा। –