मैं सी # में वास्तव में अपरिवर्तनीय दोगुनी लिंक कैसे बना सकता हूं?

Question

यह एक सैद्धांतिक प्रश्न है: क्या यह वास्तव में अपरिवर्तनीय दोगुनी लिंक्ड सूची बनाने के लिए सी # में किसी भी माध्यम से संभव है? एक समस्या जो मैं देखता हूं वह 2 आसन्न नोड्स की पारस्परिक निर्भरता में है।

"सचमुच" से मेरा मतलब है केवल पढ़ने वाले फ़ील्ड का उपयोग करना।

Answer 1

मुश्किल कन्स्ट्रक्टर तर्क के साथ ऐसा करना संभव है। उदाहरण के लिए

public sealed class Node<T> { 
    readonly T m_data; 
    readonly Node<T> m_prev; 
    readonly Node<T> m_next; 

    // Data, Next, Prev accessors omitted for brevity  

    public Node(T data, Node<T> prev, IEnumerator<T> rest) { 
    m_data = data; 
    m_prev = prev; 
    if (rest.MoveNext()) { 
     m_next = new Node(rest.Current, this, rest); 
    } 
    } 
} 

public static class Node {  
    public static Node<T> Create<T>(IEnumerable<T> enumerable) { 
    using (var enumerator = enumerable.GetEnumerator()) { 
     if (!enumerator.MoveNext()) { 
     return null; 
     } 
     return new Node(enumerator.Current, null, enumerator); 
    } 
    } 
} 

Node<string> list = Node.Create(new [] { "a", "b", "c", "d" }); 

Answer 2

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

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

Answer 3

आपने मेरी जिज्ञासा पिक्चर की।

public class ReadOnlyNode<T> 
{ 
    public readonly T Value; 
    public readonly ReadOnlyNode<T> Next; 
    public readonly ReadOnlyNode<T> Prev; 

    public Node(T value, ReadOnlyNode<T> next, ReadOnlyNode<T> prev) 
    { 
     Value = value; 
     Next = next; 
     Prev = prev; 
    } 
} 

एक दोगुना से जुड़े सूची में readonly के साथ समस्या यह प्रत्येक नोड के लिए, आप निर्माता में उस नोड के पिछले और अगले नोड्स निर्दिष्ट करने के लिए है, है, इसलिए: एक ReadOnlyNode के लिए वर्ग काफी सरल परिभाषित करने के लिए है अगर वे कन्स्ट्रक्टर के बाहर से पास हो जाते हैं तो वे पहले से ही मौजूद होना चाहिए। लेकिन, जब आप कन्स्ट्रक्टर को कॉल करते हैं, तो नोड एम को अपने "अगले" नोड के रूप में पूर्व-मौजूदा नोड एन की आवश्यकता होती है, लेकिन उस नोड एन को एम के निर्माण के लिए अपने "पिछले" नोड के रूप में आवश्यकता होती है। यह एक "चिकन और अंडा" स्थिति बनाता है जहां एन और एम दोनों को अन्य नोड की आवश्यकता होती है जो पहले तत्काल हो।

हालांकि, इस बिल्ली को त्वचा के एक से अधिक तरीके हैं। क्या होगा यदि एक सूची के प्रत्येक नोड को एक ReadOnlyNode के निर्माता के भीतर से तुरंत चालू किया गया था? प्रत्येक कन्स्ट्रक्टर पूरा होने तक, प्रत्येक स्तर पर गुण अभी भी व्यवहार्य हो जाएंगे, और प्रत्येक नोड का संदर्भ इसके कन्स्ट्रक्टर में मौजूद होगा, इसलिए इससे कोई फर्क नहीं पड़ता कि सबकुछ स्थापित होने तक सब कुछ स्थापित नहीं किया गया था। निम्नलिखित कोड को संकलित करता है, और यह देखते हुए पहले से मौजूद एक IEnumerable अपरिवर्तनीय दोगुना से जुड़े सूची का उत्पादन करेगा:

public class ReadOnlyNode<T> 
{ 
    public readonly T Value; 
    public readonly ReadOnlyNode<T> Next; 
    public readonly ReadOnlyNode<T> Prev; 

    private ReadOnlyNode(IEnumerable<T> elements, ReadOnlyNode<T> prev) 
    { 
     if(elements == null || !elements.Any()) 
      throw new ArgumentException(
       "Enumerable must not be null and must have at least one element"); 
     Next = elements.Count() == 1 
      ? null 
      : new ReadOnlyNode<T>(elements.Skip(1), this); 
     Value = elements.First(); 
     Prev = prev; 
    } 

    public ReadOnlyNode(IEnumerable<T> elements) 
     : this(elements, null) 
    { 
    } 
} 


//Usage - creates an immutable doubly-linked list of integers from 1 to 1000 
var immutableList = new ReadOnlyNode<int>(Enumerable.Range(1,1000)); 

आप किसी भी संग्रह है कि IEnumerable लागू करता है के साथ इस का उपयोग कर सकते (काफी सब में निर्मित संग्रह करते हैं, और आप गैर-जेनेरिक आईसीलेक्शंस और आईनेमरेबल्स को जेनेरिक आईनेमरेबल्स में बदलने के लिए ऑफटाइप() का उपयोग कर सकते हैं। कॉल स्टैक के बारे में चिंता करने की एकमात्र चीज है; इस बात की एक सीमा है कि आप कितने विधि कॉल कर सकते हैं, जो इनपुट की एक सीमित लेकिन बड़ी सूची पर एसओई का कारण बन सकती है।

संपादित करें: जेरेडपर एक बहुत अच्छा बिंदु लाता है; यह समाधान गणना() और कोई भी() का उपयोग करता है जिसे छोड़ने के परिणामों को खाते में लेना पड़ता है, और इसलिए इन विधियों में बनाए गए "शॉर्टकट्स" का उपयोग नहीं कर सकता जो संग्रह वर्ग की कार्डिनलिटी प्रॉपर्टी का उपयोग कर सकते हैं। वे कॉल रैखिक बन जाते हैं, जो एल्गोरिदम की जटिलता को चौकोर करते हैं।

public class ReadOnlyNode<T> 
{ 
    public readonly T Value; 
    public readonly ReadOnlyNode<T> Next; 
    public readonly ReadOnlyNode<T> Prev; 

    private ReadOnlyNode(IEnumerator<T> elements, ReadOnlyNode<T> prev, bool first) 
    { 
     if (elements == null) throw new ArgumentNullException("elements"); 

     var empty = false; 
     if (first) 
      empty = elements.MoveNext(); 

     if(!empty) 
     { 
      Value = elements.Current; 
      Next = elements.MoveNext() ? new ReadOnlyNode<T>(elements, this, false) : null; 
      Prev = prev; 
     } 
    } 

    public ReadOnlyNode(IEnumerable<T> elements) 
     : this(elements.GetEnumerator(), null, true) 
    { 
    } 
} 

इस समाधान के साथ

, तो आप और अधिक सुरुचिपूर्ण त्रुटि-जांच का एक छोटा खो देते हैं, लेकिन अगर IEnumerable है अशक्त एक अपवाद होगा: तुम सिर्फ बजाय IEnumerable के बुनियादी सदस्यों का उपयोग करते हैं, यह बहुत अधिक performant हो जाता है वैसे भी फेंक दिया गया है।