क्या कोई कतार (प्राथमिकता क्यूई) कार्यान्वयन है जो एक सेट भी है?

Question

मैं PriorityQueue कार्यान्वयन की तलाश में हूं जो Set भी है।

compareTo कार्यान्वयन अगर उसके तत्वों को equals के कार्यान्वयन के साथ संगत होने की आवश्यकता नहीं होनी चाहिए।

क्या जावा के लिए कहीं ऐसा कोई कार्यान्वयन है?

अद्यतन: मैंने अब इसे सॉर्टेडसेट का उपयोग आंतरिक संग्रह के रूप में लागू किया है। तो मुझे कतार इंटरफ़ेस को संतुष्ट करने के लिए केवल गायब विधियों को लागू करना पड़ा। मैं यह भी उल्लेख करना भूल गया कि इसे एक बाध्य कतार भी होनी चाहिए, इसलिए इसमें क्षमता होती है और यदि क्षमता तक पहुंच जाती है तो सेट के अंतिम तत्व को त्याग दिया जाता है।

Answer 1

खैर PriorityQueue ही जा रहा है Comparitor या उसके छंटाई के लिए आइटम के प्राकृतिक आदेश पर निर्भर होना, वैसे ही Set प्राकृतिक आदेश या Comparitor समारोह पर निर्भर होगा ताकि कोई मुझे नहीं लगता कि एक मौजूद है डिफ़ॉल्ट जावा स्थापित का हिस्सा ... के रूप में

लेकिन आप शायद एक बहुत आसानी से बना सकता है अगर गति बस इंटरफेस आप चाहते हैं, आदि

को लागू करने, और उनके प्राकृतिक backings का उपयोग कर ... उर्फ ​​द्वारा एक चिंता नहीं है

MyQueueSet extends PriorityQueue implements Set { 
    HashSet set; 
    ... 
} 

दुर्भाग्य से जावा का java.util । * डेटा-सेट कक्षाएं हमेशा उनके कोड के पुन: लिखने के बिना विस्तार करने के लिए सबसे आसान नहीं होती हैं।

PriorityQueue समर्थन, तत्वों का एक ढेर अनुसार क्रमबद्ध सूची है, तो एक नए तत्व डालने और फिर एक contains(e) परीक्षण कर रही हो जाएगा एक हे (एन) क्योंकि क्रमित कतार पर आधारित है खोज, नहीं डेटा मान पर, अगर Set कार्यक्षमता का समर्थन करने के लिए आप HashSet शामिल करते हैं, फिर भी आप डेटासेट संदर्भों को दो बार बनाए रखने के खर्च पर अपना लुकअप समय सुधार सकते हैं (याद रखें कि जावा पास-बाय-वैल्यू है और सभी ऑब्जेक्ट्स ढेर पर रहते हैं)। यह एक बड़े सेट के प्रदर्शन में सुधार करना चाहिए।

Answer 2

यदि यह एक 'सेट की तरह' व्यवहार, IAW तुम सिर्फ डुप्लिकेट प्रविष्टियों को स्वीकार नहीं करना चाहते हैं के साथ एक कतार है करने के लिए पर्याप्त है, तो मुझे लगता है, एक आसान समाधान PriorityQueue उपवर्ग और add(), addAll() ओवरराइड करने के लिए हो सकता है और offer() तरीकों की तरह:

@Override 
public boolean offer(E e) { 
    if (contains(e)) { 
    return false; 
    } else { 
    return super.offer(e); 
    } 
} 

Btw - add() कॉल offer() आंतरिक रूप से है, तो शायद यह भी सिर्फ offer() विधि ओवरराइड और वहाँ की जांच करने के लिए काफी है।

Answer 3

प्राथमिकता क्यूई एक सार संग्रह है - इसमें सेट के लिए लगभग समान इंटरफ़ेस है। मुझे यकीन है कि एक रैपर बनाना आसान होगा जो एक प्राथमिकता क्यूयू को एक सेट में परिवर्तित करता है। यदि आपको वास्तव में इसे लागू करने की आवश्यकता है, तो आप डुप्लिकेट से बचने के लिए सम्मिलित तत्वों की एक साइड हैश तालिका रख सकते हैं।

मुझे नहीं लगता कि प्राथमिकता Queue की तुलना की आवश्यकता है बराबर के साथ संगत होने के लिए। PriorityQueue बिल्कुल बराबर का उपयोग नहीं करता है (इसके विरासत सार कोलेक्शन ऑपरेशंस को छोड़कर?)।

Answer 4

TreeSet एक ऐसा सेट है जो एक आदेश दिया गया इटरेटर प्रदान करता है।यह SortedSet इंटरफ़ेस लागू करता है, जो गारंटी देता है कि iterator विधि द्वारा लौटाए गए इटरेटर को सेट के तत्वों को उनके प्राकृतिक क्रम (Comparable के माध्यम से) या उसके निर्माण पर सेट के लिए दिए गए तुलनाकर्ता द्वारा निर्धारित अनुसार आरोही क्रम में वापस कर दिया जाएगा।