1. घर
  2. सवाल और जवाब
  3. बहुत तेजी से पुनरावृत्त और अच्छे जोड़े के साथ संग्रह और

बहुत तेजी से पुनरावृत्त और अच्छे जोड़े के साथ संग्रह और

2012-01-06 4 views
5

0 को हटाएं, मैं एक संग्रह के बाद हूं जिसे मैं बहुत तेज कर सकता हूं। मैं वस्तुओं को भी जोड़ रहा हूं और (विशिष्ट) वस्तुओं को नियमित रूप से नियमित रूप से हटा दूंगा और आदर्श रूप से उन परिचालनों को तेज़ करना चाहूंगा।बहुत तेजी से पुनरावृत्त और अच्छे जोड़े के साथ संग्रह और

मैं एक्सबॉक्स पर विकास कर रहा हूं और इसलिए कॉम्पैक्ट फ्रेमवर्क (अधिक या कम) तक सीमित हूं। यह बहुत महत्वपूर्ण है कि मैं कचरा रखता हूं और आवंटन को कम से कम ऑब्जेक्ट करता हूं, इसलिए कुछ भी जहां मैं अपनी वस्तुओं के लिए स्थान आवंटित कर सकता हूं, वह बहुत अच्छा होगा।

संग्रह में uint एस संग्रहीत किया जाएगा (लेकिन यदि आवश्यक हो तो int एस हो सकता है)। हालांकि एक सामान्य समाधान अच्छा होगा, क्योंकि मुझे यकीन है कि मुझे भविष्य में आवश्यकता होगी।

ए .नेट संग्रह आदर्श होगा, यह विफल रहा कि कुछ हल्का वजन और खुला स्रोत बहुत अच्छा होगा।

क्या कोई संग्रह वर्ग है जो मेरी आवश्यकताओं के अनुरूप होगा? यदि नहीं, तो मैं एक बनाने के बारे में कैसे जाउंगा?

थोड़ा विस्तार करने के लिए, वे ऑब्जेक्ट आईडी हैं कि एक वर्ग को प्रत्येक फ्रेम को संसाधित करना चाहिए। वे आम तौर पर अंतराल के क्रम में आरोही क्रम में जोड़ा जाएगा। कोई ऊपरी सीमा नहीं है। हालांकि किसी को हटाया जा सकता है, जो अंतराल छोड़ देगा।
इटरेशन ऑर्डर पूरी तरह से महत्वपूर्ण नहीं है, लेकिन यह बहुत उपयोगी होगा (विशेष रूप से डीबगिंग के लिए) यदि यह एक सतत क्रम में था।

स्रोत

2012-01-06 George Duckett

+1

'हैशसेट ' के बारे में क्या? कोई विचार नहीं है कि यह कॉम्पैक्ट ढांचे में है। लेकिन इसे तेजी से तेज़ करना चाहिए, और वस्तुओं को जल्दी से जोड़/हटा सकता है। चूंकि यह सरणी समर्थित है, इसमें बहुत कम आवंटन हैं। "लेकिन वही मान दिए जाने चाहिए," थोड़ा सा समस्याग्रस्त हो सकता है, क्योंकि मुझे नहीं लगता कि 'हैशसेट ' गारंटी देता है कि भले ही यह अभ्यास में इस तरह से होगा। – CodesInChaos

+0

यह सीएफ में नहीं है, जो पूछने का मेरा मुख्य कारण है। एमएसडीएन पर कन्स्ट्रक्टर आइकनों की जांच करना यह है कि मैं आमतौर पर बताता हूं कि यह वहां है या नहीं ('हैशसेट '' कन्स्ट्रक्टर के आइकन 'सूची ' (जो समर्थित है) की तुलना करें। –

+0

' हैशसेट 'ऐसा प्रतीत नहीं होता है कॉम्पैक्ट फ्रेमवर्क के अलावा – SomeWritesReserved

उत्तर

2

मैं कोशिश करने के लिए दो सुझाव मिल गया है? मुझे लगता है कि कार्यान्वयन सीएफ में नहीं है या आप इसका इस्तेमाल कर सकते हैं। जेनेरिक List<T> सरणी समर्थित है और लंबाई 4 सरणी से शुरू होने वाले एक दोगुनी एल्गोरिदम का उपयोग करता है, प्रत्येक कॉल के लिए। क्षमता के ऊपर इसे डबल करने और ऐरे करने का कारण बनता है। नई सरणी में कॉपी करें। यह आकार बदलता नहीं है जब तक आप स्पष्ट रूप से शून्य पर क्षमता सेट नहीं करते हैं, इसलिए स्मृति बिंदु से सावधान रहें। जोड़ एक बात है लेकिन प्रत्येक निकालने से सरणी को कॉपी किया जाएगा और हटाए गए इंडेक्स के बाद बाएं स्थानांतरित हो जाएगा।

दूसरा सुझाव यह है - क्या बारे में सामान्य List<T> को जो जो एक समान डबल एल्गोरिथ्म का उपयोग करता इस संभाल करने के लिए एक पूर्णांक सरणी लपेटता एक कस्टम वर्ग बनाने (या चार गुना) के बारे में (आकार बदलने को संभालने के लिए), लेकिन शुरू होता है पर कहते हैं कि आकार 256। आप ऑब्जेक्ट इंटीजर आईडी को जितनी जल्दी चाहें उतनी जल्दी से जोड़ सकते हैं और यह अक्सर दोगुना नहीं होगा। आप (int) -1 या uint.MaxValue को "नल इंडेक्स" के रूप में नामित करके निकालने का अनुकरण भी कर सकते हैं जिसका अर्थ है कोई ऐरे नहीं। निकालने पर कॉपी करें। फिर, ड्राइंग से पहले ऑब्जेक्ट इंडेक्स सरणी को सॉर्ट करने के लिए प्रति फ्रेम के किसी प्रकार का फास्ट सॉर्टिंग लागू करें। यदि आप अपने सभी -1 को आरोही क्रमबद्ध करते हैं तो शुरुआत में दिखाई देंगे (या अंत में मैक्सवेल्यूज) और इसे अनदेखा किया जा सकता है। (- उपयोग लॉकिंग सावधान रहना;)

आपको क्या लगता है आप समय-समय आकार बदलने और एक अलग थ्रेड पर पूर्ववर्ती -1 के हटाने के द्वारा सूचकांक सरणी "इकट्ठा" कर सकते हैं? बस सोच आप तेजी से प्रत्येक निकालें और कुछ जोड़ता है (महंगा) पर बनाम स्मृति आवंटन/संग्रह xbox पर छँटाई (महंगा नहीं के लिए एक बार फ्रेम प्रति कुछ गणना ऑफसेट होगा

अद्यतन -। BlockArray - सूची < टी [] > जहां टी निश्चित आकार सरणी

इस पर एक और टिप्पणी। मैं हाल ही में गतिशील रूप से आकार की सूचियों के लिए सबसे कुशल डेटा संरचना के साथ प्रयोग कर रहा था और प्रयोग द्वारा खोजी गई सरणी ब्लॉक - एक वर्ग जो टी की सूची द्वारा समर्थित है [ ], जहां प्रत्येक टी [] निश्चित आकार ब्लॉक की एक सरणी थी, उदाहरण के लिए 512, 4096, 8192 सादा सूची < टी > पर कई फायदे के रूप में।

मैंने पाया कि एक) एक सूची < में जोड़ें के कार्यान्वयन ((आकार अज्ञात है जहां) टी [] > बेहद बेहतर प्रदर्शन सूची < टी > के लिए जोड़ें(), खासकर जब कुल आकार बड़ा हो गया। यह सूची < टी > के दोगुनी एल्गोरिदम के कारण है जो पुरानी के आकार के नए सरणी 2x का अनुरोध करता है, और जब भी आकार पार हो जाता है तो memcpy पुरानी सरणी होती है।

इटरेटिंग गति समान है। प्री-आवंटन (पूर्व परिभाषित क्षमता) छोटे ब्लॉक आकार (512) के लिए सूची < टी > की तुलना में बहुत धीमी थी, लेकिन बड़े ब्लॉक आकार (8192) के लिए केवल थोड़ी धीमी थी। हटाएं समस्याग्रस्त हैं, क्योंकि कई ब्लॉकों को प्रतिलिपि बनाने/छोड़ने की आवश्यकता होती है।

सूची < टी [] > (ब्लॉक सूची) में दिलचस्प क्या है, आप ब्लॉक को कैश/पूल कर सकते हैं। यदि पर्याप्त छोटा हो, तो छोटे ऑब्जेक्ट ढेर (कॉम्पैक्शन, त्वरित आवंटन का पक्ष) में फिट होने वाले टी [] के ब्लॉक, एल 2 कैश में फिट हो सकते हैं और कई ब्लॉक पूर्व-आवंटित किए जा सकते हैं और

स्रोत

2012-01-06 17:18:08

+1

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

+0

@ जॉर्ज डकेट धन्यवाद! हां आपको सॉर्ट करने की आवश्यकता होगी ताकि आप अपना दृश्य ग्राफ रेंडर ऑर्डर में प्राप्त कर सकें। इस समाधान के लिए प्लस साइड यह है कि आप प्रत्येक ऐड और निकालने पर एक प्रकार का प्रदर्शन किए बिना सरणी (ऑर्डर के बाहर) के अंत में जोड़ सकते हैं, केवल सरणी मान को -1 पर सेट कर रहा है। शायद इसे अधिक प्रदर्शन करने के लिए ऑब्जेक्ट इंडेक्स आईडी = 123 के लिए सरणी नहीं खोजें, लेकिन ऑब्जेक्ट पर इंडेक्सएरे को इंडेक्स स्टोर भी करें? वास्तव में कोशिश करने के लिए बस चीजें। .NET एक शक्तिशाली भाषा है और मैंने सी # में अत्यधिक प्रदर्शन करने से पहले सिमुलेशन सॉफ्टवेयर लिखा है। बस जीसी –

+0

को कम करके चक्र को निचोड़ने की जरूरत है ... जिसमें मुझे जोड़ना चाहिए, सी # में perf वृद्धि सी ++ के समान है। यदि आप देशी कोड लिखते हैं जो नया() नया() नया() हटा देता है हटाएं हटाएं तो यह आश्चर्यचकित नहीं होगा कि यह धीमा था, मुझे आश्चर्य है कि लोग क्यों महसूस करते हैं .NET कोई अलग होना चाहिए? ;-P –

2

मोनो के HashSet<T> का उपयोग करने के बारे में कैसे?

https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs

यह एमआईटी X11 है, जो एक अनुमोदक लाइसेंस के अंतर्गत लाइसेंस प्राप्त है है।

पुनरावृत्ति आदेश T कैसे लागू करता है GetHashCode के आधार पर एक समस्या हो सकती है, लेकिन यह एक समस्या है जब uint का उपयोग नहीं किया जाना चाहिए। दूसरी ओर GetHashCode का डिफ़ॉल्ट कार्यान्वयन अलग-अलग उदाहरणों पर अलग-अलग मान देता है, जो अलग-अलग पुनरावृत्ति आदेश का कारण बन सकता है।

इटरेशन ऑर्डर ऑर्डर आइटम पर भी निर्भर हो सकता है। यानी एक ही आइटम वाले दो संग्रह एक अलग क्रम में फिर से जोड़े जा सकते हैं यदि आइटम एक अलग क्रम में जोड़े गए थे।

एक SortedSet<T> संग्रह भी है, लेकिन मुझे नहीं पता कि इसकी प्रदर्शन विशेषताएं क्या हैं।

सबसे पहले, क्या परावर्तक या ILSpy का उपयोग कर सामान्य List<T> अंदर देखने के लिए के बारे में:

स्रोत

2012-01-06 16:48:46 CodesInChaos

1

कस्टम क्लास के बारे में कैसे , SparseList < टी >:

  • एक सूची है कि आप अनुपलब्ध मान (या SparseValueList के लिए, की तरह -1 (एक विशेष मूल्य डॉ ABT के समाधान की तरह) शून्य पर सेटिंग से आइटम हटाने के लिए अनुमति देता है, 0 (डिफ़ॉल्ट (टी)), या int.MinValue, या uint.MaxValue,) और
  • फिर की एक सूची बनाए रखना हटाए गए सूचकांक (एक स्टैक <int>)। फिर जब आपको सूची में जोड़ने की आवश्यकता होती है, तो यह स्टैक से हटाए गए इंडेक्स को पॉप करता है और वहां मान जोड़ता है। (मल्टीथ्रेडिंग के लिए, शायद ConcurrentQueue <int> एक और विचार होगा।)
    •
  • प्रगणक को नष्ट कर दिया आइटम (गणन दौरान foreach)
  • आइटम संग्रह से हटाया जा सकता है समर्थन करने के लिए छोड़ सकते हैं! (मुझे यह बहुत करना है, इसलिए यह अच्छा है।)
  • इंडेक्सर सूची में कच्ची पहुंच प्रदान करता है जिसमें नल शामिल हैं। तो यदि आप किसी (;;) लूप का उपयोग करते हैं, तो को फ़िल्टर करने के लिए तैयार रहें।
  • कॉल कॉम्पैक्ट() यदि/जब आप करना चाहते हैं सभी nulls
  • एक कभी नहीं एक खेल के दौरान कॉम्पैक्ट कॉल करता है निकालने के लिए, मैं nulls की एक बड़ी संख्या के माध्यम से पुनरावृत्ति के बारे में चिंतित हूँ। इसलिए कॉम्पैक्ट करने के लिए एक प्रयोगात्मक विकल्प के लिए, स्पैर्सलिस्ट क्लेनिंगएन्यूमेरेटर देखें: कम से कम एकल-थ्रेडेड परिस्थितियों के लिए प्रत्येक बार जब गणना की जाती है, सूची को स्वचालित रूप से संक्षिप्त करें: जब MoveNext किसी आइटम से दूर हो जाता है, तो यह देखने के लिए स्टैक को देखता है कि सूचकांक कम है या नहीं यदि ऐसा है तो यह आइटम को निम्न सूचकांक में निर्दिष्ट करता है, इसे वर्तमान स्थिति से हटा देता है, जो सूची को कम कर देगा। संतुलन कई पुनरावृत्तियों को ले सकता है और ऑप्टिमाइज़ेशन से पहले कई चालों को शामिल कर सकता है, जब तक कि स्टैक को सॉर्टलिस्ट के साथ प्रतिस्थापित नहीं किया जाता है, या स्टैक को कभी-कभी क्रमबद्ध किया जाता है। यदि अंतिम मूल्य शून्य है, तो यह काम नहीं करेगा, क्योंकि इंडेक्स को मुफ्त इंडेक्स स्टैक में दफनाया जाएगा (किसी प्रकार के स्टैक को प्रतिस्थापित करने से इसे टालना होगा)।
    •

मैंने इसे कार्यान्वित किया (अभी तक परीक्षण नहीं किया गया है) लेकिन मैं आईडी के बजाए अपनी गेम इकाइयों के वास्तविक संदर्भ संग्रहीत कर रहा हूं, इसलिए आपको किसी भी तरह int या nullable के लिए इसे अनुकूलित करने की आवश्यकता होगी। (ठीक है यह सुनिश्चित करने के लिए कि मैं आपके प्रश्न की int/uint आवश्यकता का उत्तर देता हूं मैंने एक स्पैर्सवेल्यूलिस्ट < टी > भी जोड़ा है जो कि शून्य के बजाय डिफ़ॉल्ट (टी) का उपयोग करके थोड़ा अलग है। इसका मतलब है कि आप सूची में 0 का उपयोग नहीं कर सकते हैं।) आप शायद यदि आपको नहीं लगता कि आपको इसकी आवश्यकता है तो संस्करण निकालें - अधिकांश गेम नहीं हो सकते हैं।

/// <summary> 
/// Specifying null as value has unspecified results. 
/// CopyTo may contain nulls. 
/// </summary> 
/// <typeparam name="T"></typeparam> 
public class SparseList<T> : IList<T> 
    where T : class 
{ 
    int version = 0; 
    List<T> list = new List<T>(); 
    Stack<int> freeIndices = new Stack<int>(); 

    public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } } 

    public void Compact() 
    { 
     var sortedIndices = freeIndices.ToList(); 

     foreach (var i in sortedIndices.OrderBy(x => x).Reverse()) 
     { 
      list.RemoveAt(i); 
     } 
     freeIndices.Clear(); 
     list.Capacity = list.Count; 
     version++; // breaks open enumerators 
    } 

    public int IndexOf(T item) 
    { 
     return list.IndexOf(item); 
    } 

    /// <summary> 
    /// Slow (forces a compact), not recommended 
    /// </summary> 
    /// <param name="index"></param> 
    /// <param name="item"></param> 
    public void Insert(int index, T item) 
    { 
     // One idea: remove index from freeIndices if it's in there. Stack doesn't support this though. 
     Compact(); // breaks the freeIndices list, so apply it before insert 
     list.Insert(index, item); 
     version++; // breaks open enumerators 
    } 

    public void RemoveAt(int index) 
    { 
     if (index == Count - 1) { list.RemoveAt(index); } 
     else { list[index] = null; freeIndices.Push(index); } 
     //version++; // Don't increment version for removals 
    } 

    public T this[int index] 
    { 
     get 
     { 
      return list[index]; 
     } 
     set 
     { 
      if (value == null) throw new ArgumentNullException(); 
      list[index] = value; 
     } 
    } 

    public void Add(T item) 
    { 
     if (item == null) throw new ArgumentNullException(); 

     if (freeIndices.Count == 0) { list.Add(item); return; } 

     list[freeIndices.Pop()] = item; 
     //version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators 
    } 

    public void Clear() 
    { 
     list.Clear(); 
     freeIndices.Clear(); 
     version++; 
    } 

    public bool Contains(T item) 
    { 
     if (item == null) return false; 
     return list.Contains(item); 
    } 

    /// <summary> 
    /// Result may contain nulls 
    /// </summary> 
    /// <param name="array"></param> 
    /// <param name="arrayIndex"></param> 
    public void CopyTo(T[] array, int arrayIndex) 
    { 
     list.CopyTo(array, arrayIndex); 
    } 
    //public void CopyNonNullTo(T[] array, int arrayIndex) 
    //{ 
    //} 

    /// <summary> 
    /// Use this for iterating via for loop. 
    /// </summary> 
    public int Count { get { return list.Count; } } 

    /// <summary> 
    /// Don't use this for for loops! Use Count. 
    /// </summary> 
    public int NonNullCount 
    { 
     get { return list.Count - freeIndices.Count; } 
    } 

    public bool IsReadOnly 
    { 
     get { return false; } 
    } 

    public bool Remove(T item) 
    { 
     int i = list.IndexOf(item); 
     if (i < 0) return false; 

     if (i == list.Count - 1) 
     { 
      // Could throw . Could add check in 
      list.RemoveAt(i); 
     } 
     else 
     { 
      list[i] = null; 
      freeIndices.Push(i); 
     } 
     //version++; // Don't increment version for removals 
     return true; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return new SparseListEnumerator(this); 
    } 

    private class SparseListEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseList<T> list; 
     int version; 
     int index = -1; 

     public SparseListEnumerator(SparseList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      //while (Current == null && MoveNext()) ; 
     } 

     public T Current 
     { 
      get { 
       if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       index++; 
       return index < list.Count; 
      } while (Current == null); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null. 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

    private class SparseListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseList<T> list; 
     int version; 
     int index = -1; 

     public SparseListCleaningEnumerator(SparseList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      //while (Current == null && MoveNext()) ; 
     } 

     public T Current 
     { 
      get 
      { 
       if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       if (index > 0 
        && Current != null // only works for values that are set, otherwise the index is buried in the free index stack somewhere 
        ) 
       { 
        int freeIndex = list.freeIndices.Peek(); 
        if (freeIndex < index) 
        { 
         list.freeIndices.Pop(); 
         list[freeIndex] = list[index]; 
         list.RemoveAt(index); 
        } 
       } 
       index++; 
       return index < list.Count; 
      } while (Current == null); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null. 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 
} 

/// <summary> 
/// Like SparseList but Supports value types, using default(T) in place of null. 
/// This means values of default(T) are not permitted as values in the collection. 
/// CopyTo may contain default(T). 
/// TODO: Use EqualityComparer&lt;T&gt;.Default instead of default(T).Equals() 
/// </summary> 
/// <typeparam name="T"></typeparam> 
public class SparseValueList<T> : IList<T> 
{ 
    int version = 0; 
    List<T> list = new List<T>(); 
    Stack<int> freeIndices = new Stack<int>(); 

    public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } } 

    public void Compact() 
    { 
     var sortedIndices = freeIndices.ToList(); 

     foreach (var i in sortedIndices.OrderBy(x => x).Reverse()) 
     { 
      list.RemoveAt(i); 
     } 
     freeIndices.Clear(); 
     list.Capacity = list.Count; 
     version++; // breaks open enumerators 
    } 

    public int IndexOf(T item) 
    { 
     return list.IndexOf(item); 
    } 

    /// <summary> 
    /// Slow (forces a compact), not recommended 
    /// </summary> 
    /// <param name="index"></param> 
    /// <param name="item"></param> 
    public void Insert(int index, T item) 
    { 
     // One idea: remove index from freeIndices if it's in there. Stack doesn't support this though. 
     Compact(); // breaks the freeIndices list, so apply it before insert 
     list.Insert(index, item); 
     version++; // breaks open enumerators 
    } 

    public void RemoveAt(int index) 
    { 
     if (index == Count - 1) { list.RemoveAt(index); } 
     else { list[index] = default(T); freeIndices.Push(index); } 
     //version++; // Don't increment version for removals 
    } 

    public T this[int index] 
    { 
     get 
     { 
      return list[index]; 
     } 
     set 
     { 
      if (default(T).Equals(value)) throw new ArgumentNullException(); 
      list[index] = value; 
     } 
    } 

    public void Add(T item) 
    { 
     if (default(T).Equals(item)) throw new ArgumentNullException(); 

     if (freeIndices.Count == 0) { list.Add(item); return; } 

     list[freeIndices.Pop()] = item; 
     //version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators 
    } 

    public void Clear() 
    { 
     list.Clear(); 
     freeIndices.Clear(); 
     version++; 
    } 

    public bool Contains(T item) 
    { 
     if (default(T).Equals(item)) return false; 
     return list.Contains(item); 
    } 

    /// <summary> 
    /// Result may contain default(T)'s 
    /// </summary> 
    /// <param name="array"></param> 
    /// <param name="arrayIndex"></param> 
    public void CopyTo(T[] array, int arrayIndex) 
    { 
     list.CopyTo(array, arrayIndex); 
    } 
    //public void CopyNonNullTo(T[] array, int arrayIndex) 
    //{ 
    //} 

    /// <summary> 
    /// Use this for iterating via for loop. 
    /// </summary> 
    public int Count { get { return list.Count; } } 

    /// <summary> 
    /// Don't use this for for loops! Use Count. 
    /// </summary> 
    public int NonNullCount 
    { 
     get { return list.Count - freeIndices.Count; } 
    } 

    public bool IsReadOnly 
    { 
     get { return false; } 
    } 

    public bool Remove(T item) 
    { 
     int i = list.IndexOf(item); 
     if (i < 0) return false; 

     if (i == list.Count - 1) 
     { 
      // Could throw . Could add check in 
      list.RemoveAt(i); 
     } 
     else 
     { 
      list[i] = default(T); 
      freeIndices.Push(i); 
     } 
     //version++; // Don't increment version for removals 
     return true; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return new SparseValueListEnumerator(this); 
    } 

    private class SparseValueListEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseValueList<T> list; 
     int version; 
     int index = -1; 

     public SparseValueListEnumerator(SparseValueList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      //while (Current == default(T) && MoveNext()) ; 
     } 

     public T Current 
     { 
      get 
      { 
       if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       index++; 
       return index < list.Count; 
      } while (default(T).Equals(Current)); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T). 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

    private class SparseValueListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseValueList<T> list; 
     int version; 
     int index = -1; 

     public SparseValueListCleaningEnumerator(SparseValueList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      while (default(T).Equals(Current) && MoveNext()) ; 
     } 

     public T Current 
     { 
      get 
      { 
       if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       if (index > 0 
        && (!default(T).Equals(Current)) // only works for values that are set, otherwise the index might be buried in the stack somewhere 
        ) 
       { 
        int freeIndex = list.freeIndices.Peek(); 
        if (freeIndex < index) 
        { 
         list.freeIndices.Pop(); 
         list[freeIndex] = list[index]; 
         list.RemoveAt(index); 
        } 
       } 
       index++; 
       return index < list.Count; 
      } while (default(T).Equals(Current)); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T). 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 
}

स्रोत

2014-02-09 21:40:57

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

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