Chapter 7 - Collections
Enumeration
Low-level use of IEnumerable and IEnumerator
string s = "Hello";
// Because string implements IEnumerable, we can call GetEnumerator():
IEnumerator rator = s.GetEnumerator();
while (rator.MoveNext())
{
char c = (char) rator.Current;
Console.Write (c + ".");
}
Console.WriteLine();
// Equivalent to:
foreach (char c in s)
Console.Write (c + ".");
Disposing enumerators
IEnumerable<char> s = "Hello";
using (var rator = s.GetEnumerator())
while (rator.MoveNext())
{
char c = (char) rator.Current;
Console.Write (c + ".");
}
Use of nongeneric interfaces
void Main()
{
Count ("the quick brown fix".Split()).Dump();
}
public static int Count (IEnumerable e)
{
int count = 0;
foreach (object element in e)
{
var subCollection = element as IEnumerable;
if (subCollection != null)
count += Count (subCollection);
else
count++;
}
return count;
}
Simple iterator class
void Main()
{
foreach (int element in new MyCollection())
Console.WriteLine (element);
}
public class MyCollection : IEnumerable
{
int[] data = { 1, 2, 3 };
public IEnumerator GetEnumerator()
{
foreach (int i in data)
yield return i;
}
}
Simple iterator class - generic
void Main()
{
foreach (int element in new MyGenCollection())
Console.WriteLine (element);
}
public class MyGenCollection : IEnumerable<int>
{
int[] data = { 1, 2, 3 };
public IEnumerator<int> GetEnumerator()
{
foreach (int i in data)
yield return i;
}
IEnumerator IEnumerable.GetEnumerator() // Explicit implementation
{ // keeps it hidden.
return GetEnumerator();
}
}
Iterator method
void Main()
{
foreach (int i in Test.GetSomeIntegers())
Console.WriteLine (i);
}
public class Test
{
public static IEnumerable <int> GetSomeIntegers()
{
yield return 1;
yield return 2;
yield return 3;
}
}
Low-level approach - nongeneric
void Main()
{
foreach (int i in new MyIntList())
Console.WriteLine (i);
}
public class MyIntList : IEnumerable
{
int[] data = { 1, 2, 3 };
public IEnumerator GetEnumerator() => new Enumerator (this);
class Enumerator : IEnumerator // Define an inner class
{ // for the enumerator.
MyIntList collection;
int currentIndex = -1;
internal Enumerator (MyIntList collection)
{
this.collection = collection;
}
public object Current
{
get
{
if (currentIndex == -1)
throw new InvalidOperationException ("Enumeration not started!");
if (currentIndex == collection.data.Length)
throw new InvalidOperationException ("Past end of list!");
return collection.data [currentIndex];
}
}
public bool MoveNext()
{
if (currentIndex >= collection.data.Length - 1) return false;
return ++currentIndex < collection.data.Length;
}
public void Reset() => currentIndex = -1;
}
}
Low-level approach - generic
void Main()
{
foreach (int i in new MyIntList())
Console.WriteLine (i);
}
class MyIntList : IEnumerable<int>
{
int[] data = { 1, 2, 3 };
// The generic enumerator is compatible with both IEnumerable and
// IEnumerable<T>. We implement the nongeneric GetEnumerator method
// explicitly to avoid a naming conflict.
public IEnumerator<int> GetEnumerator() => new Enumerator(this);
IEnumerator IEnumerable.GetEnumerator() => new Enumerator(this);
class Enumerator : IEnumerator<int>
{
int currentIndex = -1;
MyIntList collection;
internal Enumerator (MyIntList collection)
{
this.collection = collection;
}
public int Current { get { return collection.data [currentIndex]; } }
object IEnumerator.Current { get { return Current; } }
public bool MoveNext() => ++currentIndex < collection.data.Length;
public void Reset() => currentIndex = -1;
// Given we don't need a Dispose method, it's good practice to
// implement it explicitly, so it's hidden from the public interface.
void IDisposable.Dispose() {}
}
}
ICollection and IList
ICollection and IList
// (see book)
Arrays
Referential vs structural comparisons
object[] a1 = { "string", 123, true };
object[] a2 = { "string", 123, true };
Console.WriteLine (a1 == a2); // False
Console.WriteLine (a1.Equals (a2)); // False
IStructuralEquatable se1 = a1;
Console.WriteLine (se1.Equals (a2, StructuralComparisons.StructuralEqualityComparer)); // True
Shallow array clone
StringBuilder[] builders = new StringBuilder [5];
builders [0] = new StringBuilder ("builder1");
builders [1] = new StringBuilder ("builder2");
builders [2] = new StringBuilder ("builder3");
StringBuilder[] builders2 = builders;
StringBuilder[] shallowClone = (StringBuilder[]) builders.Clone();
builders.Dump();
builders2.Dump();
(builders[0] == builders2[0]).Dump ("Comparing first element of each array");
Construction and indexing
// Via C#'s native syntax:
int[] myArray = { 1, 2, 3 };
int first = myArray [0];
int last = myArray [myArray.Length - 1];
// Using GetValue/SetValue:
// Create a string array 2 elements in length:
Array a = Array.CreateInstance (typeof(string), 2);
a.SetValue ("hi", 0); // → a[0] = "hi";
a.SetValue ("there", 1); // → a[1] = "there";
a.Dump();
string s = (string) a.GetValue (0); // → s = a[0];
s.Dump();
// We can also cast to a C# array as follows:
string[] cSharpArray = (string[]) a;
string s2 = cSharpArray [0];
s2.Dump();
Print first element of array
// This works for arrays of any rank
void WriteFirstValue (Array a)
{
Console.Write (a.Rank + "-dimensional; ");
// The indexers array will automatically initialize to all zeros, so
// passing it into GetValue or SetValue will get/set the zero-based
// (i.e., first) element in the array.
int[] indexers = new int[a.Rank];
Console.WriteLine ("First value is " + a.GetValue (indexers));
}
void Main()
{
int[] oneD = { 1, 2, 3 };
int[,] twoD = { {5,6}, {8,9} };
WriteFirstValue (oneD); // 1-dimensional; first value is 1
WriteFirstValue (twoD); // 2-dimensional; first value is 5
}
Enumeration
int[] myArray = { 1, 2, 3};
foreach (int val in myArray)
Console.WriteLine (val);
// Alternative:
Array.ForEach (new[] { 1, 2, 3 }, Console.WriteLine);
Searching arrays
string[] names = { "Rodney", "Jack", "Jill", "Jane" };
Array.Find (names, n => n.Contains ("a")).Dump(); // Returns first matching element
Array.FindAll (names, n => n.Contains ("a")).Dump(); // Returns all matching elements
// Equivalent in LINQ:
names.FirstOrDefault (n => n.Contains ("a")).Dump();
names.Where (n => n.Contains ("a")).Dump();
Sorting arrays
int[] numbers = { 3, 2, 1 };
Array.Sort (numbers);
numbers.Dump ("Simple sort");
numbers = new[] { 3, 2, 1 };
string[] words = { "three", "two", "one" };
Array.Sort (numbers, words);
new { numbers, words }.Dump ("Parallel sort");
Sorting arrays with lambda
// Sort such that odd numbers come first:
int[] numbers = { 1, 2, 3, 4, 5 };
Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1);
numbers.Dump();
Converting arrays
float[] reals = { 1.3f, 1.5f, 1.8f };
int[] wholes = Array.ConvertAll (reals, r => Convert.ToInt32 (r));
wholes.Dump();
Lists, Queues, Stacks and Sets
Generic List class
List<string> words = new List<string>(); // New string-typed list
words.Add ("melon");
words.Add ("avocado");
words.AddRange (new[] { "banana", "plum" } );
words.Insert (0, "lemon"); // Insert at start
words.InsertRange (0, new[] { "peach", "nashi" }); // Insert at start
words.Remove ("melon");
words.RemoveAt (3); // Remove the 4th element
words.RemoveRange (0, 2); // Remove first 2 elements
// Remove all strings starting in 'n':
words.RemoveAll (s => s.StartsWith ("n"));
Console.WriteLine (words [0]); // first word
Console.WriteLine (words [words.Count - 1]); // last word
foreach (string s in words) Console.WriteLine (s); // all words
List<string> subset = words.GetRange (1, 2); // 2nd->3rd words
string[] wordsArray = words.ToArray(); // Creates a new typed array
// Copy first two elements to the end of an existing array:
string[] existing = new string [1000];
words.CopyTo (0, existing, 998, 2);
List<string> upperCaseWords = words.ConvertAll (s => s.ToUpper());
List<int> lengths = words.ConvertAll (s => s.Length);
Old ArrayList class
ArrayList al = new ArrayList();
al.Add ("hello");
string first = (string) al [0];
string[] strArr = (string[]) al.ToArray (typeof (string));
al = new ArrayList();
al.Add ("hello");
first = (string) al [0];
// We need a clumsy cast to retrieve elements:
strArr = (string[]) al.ToArray (typeof (string));
// which fails at *runtime* if we get it wrong:
var runtimeFail = (int) al [0]; // Runtime exception
LinkedList
var tune = new LinkedList<string>();
tune.AddFirst ("do"); tune.Dump(); // do
tune.AddLast ("so"); tune.Dump(); // do - so
tune.AddAfter (tune.First, "re"); tune.Dump(); // do - re- so
tune.AddAfter (tune.First.Next, "mi"); tune.Dump(); // do - re - mi- so
tune.AddBefore (tune.Last, "fa"); tune.Dump(); // do - re - mi - fa- so
tune.RemoveFirst(); tune.Dump(); // re - mi - fa - so
tune.RemoveLast(); tune.Dump(); // re - mi - fa
LinkedListNode<string> miNode = tune.Find ("mi");
tune.Remove (miNode); tune.Dump(); // re - fa
tune.AddFirst (miNode); tune.Dump(); // mi- re - fa
Queue
var q = new Queue<int>();
q.Enqueue (10);
q.Enqueue (20);
int[] data = q.ToArray(); // Exports to an array
Console.WriteLine (q.Count); // "2"
Console.WriteLine (q.Peek()); // "10"
Console.WriteLine (q.Dequeue()); // "10"
Console.WriteLine (q.Dequeue()); // "20"
Console.WriteLine (q.Dequeue()); // throws an exception (queue empty)
Stack
var s = new Stack<int>();
s.Push (1); // Stack = 1
s.Push (2); // Stack = 1,2
s.Push (3); // Stack = 1,2,3
Console.WriteLine (s.Count); // Prints 3
Console.WriteLine (s.Peek()); // Prints 3, Stack = 1,2,3
Console.WriteLine (s.Pop()); // Prints 3, Stack = 1,2
Console.WriteLine (s.Pop()); // Prints 2, Stack = 1
Console.WriteLine (s.Pop()); // Prints 1, Stack = <empty>
Console.WriteLine (s.Pop()); // throws exception
BitArray
var bits = new BitArray(2);
bits[1] = true;
bits.Xor (bits); // Bitwise exclusive-OR bits with itself
Console.WriteLine (bits[1]); // False
HashSet and SortedSet
{
var letters = new HashSet<char> ("the quick brown fox");
Console.WriteLine (letters.Contains ('t')); // true
Console.WriteLine (letters.Contains ('j')); // false
foreach (char c in letters) Console.Write (c); // the quickbrownfx
}
Console.WriteLine();
{
var letters = new SortedSet<char> ("the quick brown fox");
foreach (char c in letters)
Console.Write (c); // bcefhiknoqrtuwx
Console.WriteLine();
foreach (char c in letters.GetViewBetween ('f', 'i'))
Console.Write (c); // fhi
}
HashSet and SortedSet - set operators
{
var letters = new HashSet<char> ("the quick brown fox");
letters.IntersectWith ("aeiou");
foreach (char c in letters) Console.Write (c); // euio
}
Console.WriteLine();
{
var letters = new HashSet<char> ("the quick brown fox");
letters.ExceptWith ("aeiou");
foreach (char c in letters) Console.Write (c); // th qckbrwnfx
}
Console.WriteLine();
{
var letters = new HashSet<char> ("the quick brown fox");
letters.SymmetricExceptWith ("the lazy brown fox");
foreach (char c in letters) Console.Write (c); // quicklazy
}
Dictionaries
Dictionary
var d = new Dictionary<string, int>();
d.Add("One", 1);
d["Two"] = 2; // adds to dictionary because "two" not already present
d["Two"] = 22; // updates dictionary because "two" is now present
d["Three"] = 3;
Console.WriteLine (d["Two"]); // Prints "22"
Console.WriteLine (d.ContainsKey ("One")); // true (fast operation)
Console.WriteLine (d.ContainsValue (3)); // true (slow operation)
int val = 0;
if (!d.TryGetValue ("onE", out val))
Console.WriteLine ("No val"); // "No val" (case sensitive)
// Three different ways to enumerate the dictionary:
foreach (KeyValuePair<string, int> kv in d) // One; 1
Console.WriteLine (kv.Key + "; " + kv.Value); // Two; 22
// Three; 3
foreach (string s in d.Keys) Console.Write (s); // OneTwoThree
Console.WriteLine();
foreach (int i in d.Values) Console.Write (i); // 1223
var dIgnoreCase = new Dictionary<string, bool> (StringComparer.OrdinalIgnoreCase);
dIgnoreCase["foo"] = true;
dIgnoreCase["FOO"].Dump();
SortedDictionary and SortedList
// MethodInfo is in the System.Reflection namespace
var sorted = new SortedList <string, MethodInfo>();
foreach (MethodInfo m in typeof (object).GetMethods())
sorted [m.Name] = m;
sorted.Keys.Dump ("keys");
sorted.Values.Dump ("values");
foreach (MethodInfo m in sorted.Values)
Console.WriteLine (m.Name + " returns a " + m.ReturnType);
Console.WriteLine (sorted ["GetHashCode"]); // Int32 GetHashCode()
Console.WriteLine (sorted.Keys [sorted.Count - 1]); // ToString
Console.WriteLine (sorted.Values[sorted.Count - 1].IsVirtual); // True
Customizable Collections and Proxies
Using System.Collections.ObjectModel.Collection
public class Animal
{
public string Name;
public int Popularity;
public Animal (string name, int popularity)
{
Name = name; Popularity = popularity;
}
}
public class AnimalCollection : Collection <Animal>
{
// AnimalCollection is already a fully functioning list of animals.
// No extra code is required.
}
public class Zoo // The class that will expose AnimalCollection.
{ // This would typically have additional members.
public readonly AnimalCollection Animals = new AnimalCollection();
}
static void Main()
{
Zoo zoo = new Zoo();
zoo.Animals.Add (new Animal ("Kangaroo", 10));
zoo.Animals.Add (new Animal ("Mr Sea Lion", 20));
foreach (Animal a in zoo.Animals) Console.WriteLine (a.Name);
}
Extending previous example
public class Animal
{
public string Name;
public int Popularity;
public Zoo Zoo { get; internal set; }
public Animal (string name, int popularity)
{
Name = name; Popularity = popularity;
}
}
public class AnimalCollection : Collection <Animal>
{
Zoo zoo;
public AnimalCollection (Zoo zoo) { this.zoo = zoo; }
protected override void InsertItem (int index, Animal item)
{
base.InsertItem (index, item);
item.Zoo = zoo;
}
protected override void SetItem (int index, Animal item)
{
base.SetItem (index, item);
item.Zoo = zoo;
}
protected override void RemoveItem (int index)
{
this [index].Zoo = null;
base.RemoveItem (index);
}
protected override void ClearItems()
{
foreach (Animal a in this) a.Zoo = null;
base.ClearItems();
}
}
public class Zoo
{
public readonly AnimalCollection Animals;
public Zoo() { Animals = new AnimalCollection (this); }
}
static void Main()
{
Zoo zoo = new Zoo();
zoo.Animals.Add (new Animal ("Kangaroo", 10));
zoo.Animals.Add (new Animal ("Mr Sea Lion", 20));
foreach (Animal a in zoo.Animals) Console.WriteLine (a.Name);
}
KeyedCollection
public class Animal
{
string name;
public string Name
{
get { return name; }
set {
if (Zoo != null) Zoo.Animals.NotifyNameChange (this, value);
name = value;
}
}
public int Popularity;
public Zoo Zoo { get; internal set; }
public Animal (string name, int popularity)
{
Name = name; Popularity = popularity;
}
}
public class AnimalCollection : KeyedCollection <string, Animal>
{
Zoo zoo;
public AnimalCollection (Zoo zoo) { this.zoo = zoo; }
internal void NotifyNameChange (Animal a, string newName)
{
this.ChangeItemKey (a, newName);
}
protected override string GetKeyForItem (Animal item)
{
return item.Name;
}
protected override void InsertItem (int index, Animal item)
{
base.InsertItem (index, item);
item.Zoo = zoo;
}
protected override void SetItem (int index, Animal item)
{
base.SetItem (index, item);
item.Zoo = zoo;
}
protected override void RemoveItem (int index)
{
this [index].Zoo = null;
base.RemoveItem (index);
}
protected override void ClearItems()
{
foreach (Animal a in this) a.Zoo = null;
base.ClearItems();
}
}
public class Zoo
{
public readonly AnimalCollection Animals;
public Zoo() { Animals = new AnimalCollection (this); }
}
static void Main()
{
Zoo zoo = new Zoo();
zoo.Animals.Add (new Animal ("Kangaroo", 10));
zoo.Animals.Add (new Animal ("Mr Sea Lion", 20));
Console.WriteLine (zoo.Animals [0].Popularity); // 10
Console.WriteLine (zoo.Animals ["Mr Sea Lion"].Popularity); // 20
zoo.Animals ["Kangaroo"].Name = "Mr Roo";
Console.WriteLine (zoo.Animals ["Mr Roo"].Popularity); // 10
}
ReadOnlyCollection
public class Test
{
List<string> names;
public ReadOnlyCollection<string> Names { get; private set; }
public Test()
{
names = new List<string>();
Names = new ReadOnlyCollection<string> (names);
}
public void AddInternally() { names.Add ("test"); }
}
void Main()
{
Test t = new Test();
Console.WriteLine (t.Names.Count); // 0
t.AddInternally();
Console.WriteLine (t.Names.Count); // 1
t.Names.Add ("test"); // Compiler error
((IList<string>) t.Names).Add ("test"); // NotSupportedException
}
Immutable Collections
Creating immutable collections
ImmutableArray<int> array = ImmutableArray.Create<int> (1, 2, 3);
var list = new[] { 1, 2, 3 }.ToImmutableList();
array.Dump();
list.Dump();
Manipulating immutable collections
var oldList = ImmutableList.Create<int> (1, 2, 3);
ImmutableList<int> newList = oldList.Add (4);
Console.WriteLine (oldList.Count); // 3 (unaltered)
Console.WriteLine (newList.Count); // 4
var anotherList = oldList.AddRange (new[] { 4, 5, 6 });
anotherList.Dump();
Builders
ImmutableArray<int>.Builder builder = ImmutableArray.CreateBuilder<int>();
builder.Add(1);
builder.Add(2);
builder.Add(3);
builder.RemoveAt(0);
ImmutableArray<int> myImmutable = builder.ToImmutable();
myImmutable.Dump();
var builder2 = myImmutable.ToBuilder();
builder2.Add (4); // Efficient
builder2.Remove (2); // Efficient
// ... // More changes to builder...
// Return a new immutable collection with all the changes applied:
ImmutableArray<int> myImmutable2 = builder2.ToImmutable().Dump();
Plugging in Equality and Order
IEqualityComparer and EqualityComparer
public class Customer
{
public string LastName;
public string FirstName;
public Customer (string last, string first)
{
LastName = last;
FirstName = first;
}
}
public class LastFirstEqComparer : EqualityComparer <Customer>
{
public override bool Equals (Customer x, Customer y)
=> x.LastName == y.LastName && x.FirstName == y.FirstName;
public override int GetHashCode (Customer obj)
=> (obj.LastName + ";" + obj.FirstName).GetHashCode();
}
void Main()
{
Customer c1 = new Customer ("Bloggs", "Joe");
Customer c2 = new Customer ("Bloggs", "Joe");
Console.WriteLine (c1 == c2); // False
Console.WriteLine (c1.Equals (c2)); // False
var d = new Dictionary<Customer, string>();
d [c1] = "Joe";
Console.WriteLine (d.ContainsKey (c2)); // False
var eqComparer = new LastFirstEqComparer();
d = new Dictionary<Customer, string> (eqComparer);
d [c1] = "Joe";
Console.WriteLine (d.ContainsKey (c2)); // True
}
IComparer and Comparer
class Wish
{
public string Name;
public int Priority;
public Wish (string name, int priority)
{
Name = name;
Priority = priority;
}
}
class PriorityComparer : Comparer <Wish>
{
public override int Compare (Wish x, Wish y)
{
if (object.Equals (x, y)) return 0; // Fail-safe check
return x.Priority.CompareTo (y.Priority);
}
}
void Main()
{
var wishList = new List<Wish>();
wishList.Add (new Wish ("Peace", 2));
wishList.Add (new Wish ("Wealth", 3));
wishList.Add (new Wish ("Love", 2));
wishList.Add (new Wish ("3 more wishes", 1));
wishList.Sort (new PriorityComparer());
wishList.Dump();
}
IComparer and Comparer - SurnameComparer
class SurnameComparer : Comparer <string>
{
string Normalize (string s)
{
s = s.Trim().ToUpper();
if (s.StartsWith ("MC")) s = "MAC" + s.Substring (2);
return s;
}
public override int Compare (string x, string y)
=> Normalize (x).CompareTo (Normalize (y));
}
void Main()
{
var dic = new SortedDictionary<string,string> (new SurnameComparer());
dic.Add ("MacPhail", "second!");
dic.Add ("MacWilliam", "third!");
dic.Add ("McDonald", "first!");
dic.Dump();
}
StringComparer
var dict = new Dictionary<string, int> (StringComparer.OrdinalIgnoreCase);
dict["joe"] = 12345;
dict["JOE"].Dump();
string[] names = { "Tom", "HARRY", "sheila" };
CultureInfo ci = new CultureInfo ("en-AU");
Array.Sort<string> (names, StringComparer.Create (ci, false));
names.Dump();
Culture-aware SurnameComarer
class SurnameComparer : Comparer <string>
{
StringComparer strCmp;
public SurnameComparer (CultureInfo ci)
{
// Create a case-sensitive, culture-sensitive string comparer
strCmp = StringComparer.Create (ci, false);
}
string Normalize (string s)
{
s = s.Trim();
if (s.ToUpper().StartsWith ("MC")) s = "MAC" + s.Substring (2);
return s;
}
public override int Compare (string x, string y)
{
// Directly call Compare on our culture-aware StringComparer
return strCmp.Compare (Normalize (x), Normalize (y));
}
}
void Main()
{
var dic = new SortedDictionary<string,string> (new SurnameComparer(CultureInfo.GetCultureInfo ("de-DE")));
dic.Add ("MacPhail", "second!");
dic.Add ("MacWilliam", "third!");
dic.Add ("McDonald", "first!");
dic.Dump();
}
IStructuralEquatable and IStructuralComparable
{
int[] a1 = { 1, 2, 3 };
int[] a2 = { 1, 2, 3 };
IStructuralEquatable se1 = a1;
Console.WriteLine (a1.Equals (a2)); // False
Console.WriteLine (se1.Equals (a2, EqualityComparer<int>.Default)); // True
}
{
string[] a1 = "the quick brown fox".Split();
string[] a2 = "THE QUICK BROWN FOX".Split();
IStructuralEquatable se1 = a1;
bool isTrue = se1.Equals (a2, StringComparer.InvariantCultureIgnoreCase);
}
{
var t1 = Tuple.Create (1, "foo");
var t2 = Tuple.Create (1, "FOO");
IStructuralEquatable se1 = t1;
Console.WriteLine (se1.Equals (t2, StringComparer.InvariantCultureIgnoreCase)); // True
IStructuralComparable sc1 = t1;
Console.WriteLine (sc1.CompareTo (t2, StringComparer.InvariantCultureIgnoreCase)); // 0
}
{
var t1 = Tuple.Create (1, "FOO");
var t2 = Tuple.Create (1, "FOO");
Console.WriteLine (t1.Equals (t2)); // True
}