List in der jedes Element genau einmal vorkommen darf

dEUs

Hi Leute,

ich brauch eine Liste, bei der jedes Element genau einmal vorkommen darf. Im Grunde ein Dictionary ohne die Values. Gibt's sowas?

Nein, leider nicht. Du müsstest ein Dictionary in ein selbsterstelltes Set wrappen oder benutzt die values einfach nicht.
Es gibt noch die PowerCollections wo ein Set drin ist, das war aber bei meinen Tests sowohl mit viel als auch mit wenig hashcode-Kollisionen immer langsamer als die Implementierung des Dictionary.

dEUs

Die Values einfach nicht zu benutzen ist unschön, da das auch nach außen gegeben wird.
Wie wrappe ich das in ein Set? (grob skizzieren reicht, möglicherweise reicht sogar ein Link)

bja

Naja. Du könntest eine Klasse von List<T> ableiten und die entsprechenden Methoden überladen in dem du immer vorher prüfst ob das Element schon in der Liste ist.

LordJaxom

dEUs schrieb:

Wie wrappe ich das in ein Set? (grob skizzieren reicht, möglicherweise reicht sogar ein Link)

Einfachster Gedanke: Leite von Dictionary ab und überschreibe alles was Du an Dictionary in dem Zusammenhang unschön findest, so dass nach aussen nur noch Keys gelangen.

dEUs

bja schrieb:

Naja. Du könntest eine Klasse von List<T> ableiten und die entsprechenden Methoden überladen in dem du immer vorher prüfst ob das Element schon in der Liste ist.

Unschön, da ich dann den schnellen Hashing-Algorithmus vom Dictionary nciht verwenden kann.

dEUs

LordJaxom schrieb:

dEUs schrieb:

Wie wrappe ich das in ein Set? (grob skizzieren reicht, möglicherweise reicht sogar ein Link)

Einfachster Gedanke: Leite von Dictionary ab und überschreibe alles was Du an Dictionary in dem Zusammenhang unschön findest, so dass nach aussen nur noch Keys gelangen.

Mal sehen, ob das nciht zu viel Aufwand ist.

Noodles

Vielleicht hilft Dir das:

public class Person
{
    public string name;

    public Person( string name )
    {
        this.name = name;
    }
}

// aufruf
List<Person> persons = new List<Person>();
persons.Add( new Person("deus"));
persons.Add( new Person("keinDeus"));
Person pers = new Person("deus" );
if (persons.Find(delegate(Person p) { return p.name == pers.name; }) == null)
    persons.Add(pers);
else
    MessageBox.Show("Name schon vorhanden");

Natürlich ohne public Klassenvariablen ( nur falls sich daran einer stößt )

Von ICollection<T> (oder wegen mir auch CollectionBase<T> oder wie das heißt) ableiten ist das einzig richtige. Die IList<T> hat die Semantik, dass die Elemente in der Einfügereihenfolge bleiben, was bei ner Set nicht gegeben ist. Überhaupt hat jede Spezialisierung von Collection eine Semantik, die nicht mehr passt.

Die Methoden musst du alle selber implementieren, was so viel heißt wie an das Dictionary zu delegieren. Ich hab sowas mal angefangen so weit wie ich es brauchte. Du kannst es ja fortführen.

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

namespace OrcWars.Utilities.Collections {
	/// <summary>A <c>Set</c> is a collection in which the items are unique; it is not allowed to
	/// add an item that is equal to another one already in the set. Such an operation will cause
	/// an exception to be thrown when using the <c>Add(T item)</c> method.
	/// 
	/// Because the set is implemented as a hash table, looking up, inserting and removing an item
	/// is very fast, mostly an O(1) operation. On the other hand, the elements are not sorted in
	/// any way, so enumerating through the collection will return the elements in an undefined
	/// order.</summary>
	/// <typeparam name="T">The type of the items this set will contain.</typeparam>
	public sealed class Set<T> : ICollection<T> {
		/// <summary>Adds an item to the <c>Set</c>.</summary>
		/// <param name="item">The item to add. The item must not already be in the set.</param>
		/// <exception cref="InvalidOperationException">The item is already in the set.</exception>
		public void Add(T item) {
			dictionary.Add(item, null);
		}

		/// <summary>Removes all items from the <c>Set</c>.</summary>
		public void Clear() {
			dictionary.Clear();
		}

		/// <summary>Determines whether the <c>Set</c> contains a specific item.</summary>
		/// <param name="item">The item to look for.</param>
		/// <returns><c>true</c>, if the set contains the specified item, <c>false</c> otherwise.
		/// </returns>
		public bool Contains(T item) {
			return dictionary.ContainsKey(item);
		}

		/// <summary>Copies the elements of the <c>Set</c> to an array.</summary>
		/// <param name="array">The array to copy the elements to.</param>
		/// <param name="arrayIndex">The index in the array where to start.</param>
		public void CopyTo(T[] array, int arrayIndex) {
			dictionary.Keys.CopyTo(array, arrayIndex);
		}

		/// <summary>Gets the number of elements contained in the <c>Set</c>.</summary>
		public int Count {
			get{ return dictionary.Count; }
		}

		/// <summary>Gets a value indicating whether the <c>Set</c> is read-only.</summary>
		public bool IsReadOnly {
			get{ return false; }
		}

		/// <summary>Removes the specified item from the <c>Set</c>.</summary>
		/// <param name="item">The item to remove.</param>
		/// <returns><c>true</c> if the item was found in the set, otherwise <c>false</c>.</returns>
		public bool Remove(T item) {
			return dictionary.Remove(item);
		}

		/// <summary>Returns an enumerator that iterates through the collection.</summary>
		/// <returns>A generic <c>IEnumerator</c> that can be used to iterate through the
		/// collection.</returns>
		public IEnumerator<T> GetEnumerator() {
			return new SetEnumerator<T>(dictionary.GetEnumerator());
		}

		/// <summary>This enumerator is not supported. Use the strongly-typed enumerator instead by
		/// calling <c>GetEnumerator()</c> of the generic <c>IEnumerable</c> interface.</summary>
		/// <returns>This method always throws an exception.</returns>
		/// <exception cref="NotSupportedException">This exception is always thrown.</exception>
		IEnumerator IEnumerable.GetEnumerator() {
		    throw new NotSupportedException("Use the generic enumerator instead.");
		}

		/// <summary>The internal dictionary used to implement the set methods.</summary>
		private readonly Dictionary<T, object> dictionary = new Dictionary<T, object>();

		private struct SetEnumerator<U> : IEnumerator<U> {
			public SetEnumerator(IEnumerator<KeyValuePair<U, object>> enumerator) {
				this.enumerator = enumerator;
			}

			public U Current {
				get{ return enumerator.Current.Key; }
			}

			public void Dispose() {
				enumerator.Dispose();
			}

			object IEnumerator.Current {
				get{ throw new NotSupportedException("Use the generic enumerator instead."); }
			}

			public bool MoveNext() {
				return enumerator.MoveNext();
			}

			public void Reset() {
				enumerator.Reset();
			}

			private readonly IEnumerator<KeyValuePair<U, object>> enumerator;
		}
	}
}

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