List in der jedes Element genau einmal vorkommen darf

Ich sehe grad, dass ich den Enumerator als struct gemacht habe. Wenn ich das richtig sehe, könnte das scheiße sein, weil der Enumerator als Interface-Referenz nach außen gegeben wird (was an sich schön ist) und damit u.U. geboxed wird. Evtl. ist der Enumerator als Klasse effizienter.

dEUs

Sortiert das Dictionary die Elemente automatisch? Das wäre nämlich schlecht für mich. Ich brauch sie genau in der Reihenfolge in der ich sie hinzufüge

Das Dictionary behält nicht die Einfüge-Reihenfolge und sortiert auch nicht, sondern hasht. Die Reihenfolge ist damit relativ willkürlich. Wenn du die Einfügereihenfolge brauchst, ist irgendeine Art von Liste die Datenstruktur der Wahl.

Das Einfügen könnte aber teuer werden, wenn du dann unsortiert auf Duplikate prüfst, O(n). Alternativ kannst du so ein Set verwenden und damit den ist-schon-drin-Test machen in O(1) und dann an eine List<T> (is ne ArrayList) in O(1) Zeit dranhängen.

dEUs

Das ist eine gute Idee.

Wieso machst du deine Set-Klasse sealed?

Das kommt aus einer Zeit, wo ich alles gesealed habe, wo ich nicht mehr beabsichtigt hatte, davon weiter abzuleiten. Ist aber kein guter Grund, ich mache es auch gleich mal bei mir raus.

dEUs

So, meine erste schnelle Implementation. Was hälst du davon?

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace TestingFramework
{
    public class Set<T> : IList<T>, ICollection<T>
    {
        protected Dictionary<T, object> inventory;
        protected List<T> items;
        public Set()
        {
            inventory = new Dictionary<T, object>();
            items = new List<T>();
        }

        public bool AddNoThrow(T item)
        {
            if(inventory.ContainsKey(item))
                return false;
            inventory.Add(item, null);
            items.Add(item);
            return true;
        }

        #region ICollection<T> Members

        public void Add(T item)
        {
            inventory.Add(item, null);
            items.Add(item);
        }

        public void Clear()
        {
            inventory.Clear();
            items.Clear();
        }

        public bool Contains(T item)
        {
            return inventory.ContainsKey(item);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            foreach(T t in array)
                inventory.Add(t, null);
            items.CopyTo(array, arrayIndex);
        }

        public int Count
        {
            get { return items.Count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(T item)
        {
            bool success = inventory.Remove(item);
            if(!success)
                return false;
            return items.Remove(item);
        }

        #endregion

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator()
        {
            return items.GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new NotSupportedException("Use the generic enumerator instead.");
        }

        #endregion

        #region IList<T> Members

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

        public void Insert(int index, T item)
        {
            inventory.Add(item, null);
            items.Insert(index, item);
        }

        public void RemoveAt(int index)
        {
            T t = items[index];
            if(inventory.Remove(t))
                items.RemoveAt(index);
        }

        public T this[int index]
        {
            get
            {
                return items[index];
            }
            set
            {
                if(index >= items.Count)
                    throw new ArgumentOutOfRangeException("index");
                inventory.Add(value, null);
                T t = items[index];
                inventory.Remove(t);
                items[index] = value;
            }
        }
        #endregion
    }
}

bja

Warum stopfst du jedes element aus dem Array in dein inventory?

public void CopyTo(T[] array, int arrayIndex)
        {
            foreach(T t in array)
                inventory.Add(t, null);
            items.CopyTo(array, arrayIndex);
        }

ergibt für mich keinen Sinn. Ausserdem fliegt eine Exception, wenn im array ein element null ist.

Ja, das finde ich auch komisch. CopyTo() ist nicht so zu verstehen, dass die Elemente aus dem Array der Datenstruktur hinzugefügt werden. Amsonsten würde ich noch AddNoThrow() .Net-üblich TryAdd() nennen. Aber sonst seh ich jetzt nichts.

dEUs

Hi,

was macht CopyTo denn dann?
AddNoThrow werd ich ändern.

CopyTo macht das Gegenteil, deshalb heißt es ja auch nicht CopyFrom.
http://msdn2.microsoft.com/en-us/library/0efx51xw.aspx

dEUs

Ah, ok