Обобщенные коллекции
В теме Обобщенные типы мы уже говорили про обобщения: как создавать и использовать обобщенные классы, роль универсального параметра T. Обобщенные коллекции - это те же самые обобщенные классы. И опять же их использование перед необобщенными коллекциями имеет те же преимущества: повышение производительности (не надо тратить время на упаковку и распаковку объекта) и повышенная типобезопасность.
Классы обобщенных коллекций находятся в пространстве имен System.Collections.Generic. Функционал коллекций также по большей части описывается в обобщенных интерфейсах.
Только интерфейсы обобщенных коллекций отличаются от необобщеных двойников не только наличием универсального параметра T, но и самой функциональностью. Рассмотрим основные интерфейсы обобщенных коллекций:
IEnumerable<T>: определяет метод GetEnumerator, с помощью которого можно получать элементы любой коллекции
. Реализация данного интерфейса позволяет перебирать элементы коллекции с помощью цикла foreach
IEumerator<T>: определяет методы, с помощью которых потом можно получить содержимое коллекции по очереди
ICollection<T>: представляет ряд общих свойств и методов для всех необобщенных коллекций (например, методыCopyTo, Add, Remove, Contains, свойство Count)
IList<T>: предоставляет функционал для создания последовательных списков
IComparer<T>: определяет метод Compare для сравнения двух однотипных объектов
IDictionary<TKey, TValue>: определяет поведение коллекции, при котором она должна хранить объекты в виде пар ключ-значение: для каждого объекта определяется уникальный ключ типа, указанного в параметре TKey, и этому ключу соответствует определенное значение, имеющее тип, указанный в параметре TValue
IEqualityComparer<T>: определяет методы, с помощью которых два однотипных объекта сравниваются на предмет равенства
Эти интерфейсы реализуются следующими классами коллекций в пространстве имен System.Collections.Generic:
List<T>: класс, представляющий последовательный список. Реализует интерфейсы IList<T>, ICollection<T>, IEnumerable<T>
Dictionary<TKey, TValue>: класс коллекции, хранящей наборы пар "ключ-значение". Реализует интерфейсы ICollection<T>, IEnumerable<T>, IDictionary<TKey, TValue>
LinkedList<T>: класс двухсвязанного списка. Реализует интерфейсы ICollection<T> и IEnumerable<T>
Queue<T>: класс очереди объектов, работающей по алгоритму LIFO("первый вошел -первый вышел"). Реализует интерфейсы ICollection, IEnumerable<T>
SortedSet<T>: класс отсортированной коллекции однотипных объектов. Реализует интерфейсы ICollection<T>, ISet<T>, IEnumerable<T>
SortedList<TKey, TValue>: класс коллекции, хранящей наборы пар "ключ-значение", отсортированных по ключу. Реализует интерфейсы ICollection<T>, IEnumerable<T>, IDictionary<TKey, TValue>
SortedDictionary<TKey, TValue>: класс коллекции, хранящей наборы пар "ключ-значение", отсортированных по ключу. В общем похож на класс SortedList<TKey, TValue>, основные отличия состоят лишь в использовании памяти и в скорости вставки и удаления
Stack<T>: класс стека однотипных объектов. Реализует интерфейсы ICollection<T> и IEnumerable<T>
Большинство обобщенных классов коллекций дублируют необобщенные классы коллекций. Но если вам не надо хранить объекты разных типов, то предпочтительнее использовать обобщенные коллекции.
Рассмотрим основные обобщенные коллекции.
Список List<T>
Класс List<T> представляет простейший список однотипных объектов.
Среди его методов можно выделить следующие:
void Add(T item): добавление нового элемента в список
void AddRange(ICollection collection): добавление с список коллекции или массива
int BinarySearch(T item): бинарный поиск элемента в списке. Если элемент найден, то метод возвращает индекс этого элемента в коллекции. При этом список должен быть отсортирован.
int IndexOf(T item): возвращает индекс первого вхождения элемента в списке
void Insert(int index, T item): вставляет элемент item в списке на позицию index
bool Remove(T item): удаляет элемент item из списка, и если удаление прошло успешно, то возвращает true
void RemoveAt(int index): удаление элемента по указанному индексу index
void Sort(): сортировка списка
Посмотрим реализацию списка на примере:
using System;
using System.Collections.Generic;
namespace Collections
{
class Program
{
static void Main(string[] args)
{
List<int> numbers = new List<int>() { 1, 2, 3, 45 };
numbers.Add(6); // добавление элемента
numbers.AddRange(new int[] { 7, 8, 9 });
numbers.Insert(0, 666); // вставляем на первое место в списке число 666
numbers.RemoveAt(1); // удаляем второй элемент
foreach (int i in numbers)
{
Console.WriteLine(i);
}
List<Person> people = new List<Person>(3);
people.Add(new Person() { Name = "Том" });
people.Add(new Person() { Name = "Билл" });
foreach (Person p in people)
{
Console.WriteLine(p.Name);
}
Console.ReadLine();
}
}
class Person
{
public string Name { get; set; }
}
}
Здесь у нас создаются два списка: один для объектов типа int, а другой - для объектов Person. В первом случае мы выполняем начальную инициализацию списка: List<int> numbers = new List<int>() { 1, 2, 3, 45 };
Во втором случае мы используем другой конструктор, в который передаем начальную емкость списка: List<Person> people = new List<Person>(3);. Указание начальной емкости списка (capacity) позволяет в будущем увеличить производительность и уменьшить издержки на выделение памяти при добавлении элементов. Также начальную емкость можно установить с помощью свойства Capacity, которое имеется у класса List.
Двухсвязный список LinkedList<T>
Класс LinkedList<T> представляет двухсвязный список, в котором каждый элемент хранит ссылку одновременно на следующий и на предыдущий элемент.
Если в простом списке List<T> каждый элемент представляет объект типа T, то в LinkedList<T> каждый узел представляет объект класса LinkedListNode<T>. Этот класс имеет следующие свойства:
Value: само значение узла, представленное типом T
Next: ссылка на следующий элемент типа LinkedListNode<T> в списке. Если следующий элемент отсутствует, то имеет значение null
Previous: ссылка на предыдущий элемент типа LinkedListNode<T> в списке. Если предыдущий элемент отсутствует, то имеет значение null
Используя методы класса LinkedList<T>, можно обращаться к различным элементам, как в конце, так и в начале списка:
AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode): вставляет узел newNode в список после узла node.
AddAfter(LinkedListNode<T> node, T value): вставляет в список новый узел со значением value после узла node.
AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode): вставляет в список узел newNode перед узлом node.
AddBefore(LinkedListNode<T> node, T value): вставляет в список новый узел со значением value перед узлом node.
AddFirst(LinkedListNode<T> node): вставляет новый узел в начало списка
AddFirst(T value): вставляет новый узел со значением value в начало списка
AddLast(LinkedListNode<T> node): вставляет новый узел в конец списка
AddLast(T value): вставляет новый узел со значением value в конец списка
RemoveFirst(): удаляет первый узел из списка. После этого новым первым узлом становится узел, следующий за удаленным
RemoveLast(): удаляет последний узел из списка
Посмотрим на двухсвязный список в действии:
using System;
using System.Collections.Generic;
namespace Collections
{
class Program
{
static void Main(string[] args)
{
LinkedList<int> numbers = new LinkedList<int>();
numbers.AddLast(1); // вставляем узел со значением 1 на последнее место
// так как в списке нет узлов, то последнее будет также и первым
numbers.AddFirst(2); // вставляем узел со значением 2 на первое место
numbers.AddAfter(numbers.Last, 3); // вставляем после последнего узла новый узел со значением 3
// теперь у нас список имеет следующую последовательность: 2, 1, 3
foreach (int i in numbers)
{
Console.WriteLine(i);
}
LinkedList<Person> persons = new LinkedList<Person>();
// добавляем persona в список и получим объект LinkedListNode<Person>, в котором хранится имя Tom
LinkedListNode<Person> tom = persons.AddLast(new Person() { Name = "Tom" });
persons.AddLast(new Person() { Name = "John" });
persons.AddFirst(new Person() { Name = "Bill" });
Console.WriteLine(tom.Previous.Value.Name); // получаем узел перед томом и его значение
Console.WriteLine(tom.Next.Value.Name); // получаем узел после тома и его значение
Console.ReadLine();
}
}
class Person
{
public string Name { get; set; }
}
}
Здесь создаются и используются два списка: для чисел и для объектов класса Person. С числами, наверное, все более менее понятно. Разберем работу с классом Person.
Методы вставки (AddLast, AddFirst) при добавлении в список возвращают ссылку на добавленный элемент LinkedListNode<T> (в нашем случае LinkedListNode<Person>). Затем управляя свойствами Previous и Next, мы можем получить ссылки на предыдущий и следующий узлы в списке.
Очередь Queue<T>
Класс Queue<T> представляет обычную очередь, работающую по алгоритму FIFO ("первый вошел - первый вышел").
У класса Queue<T> можно отметить следующие методы:
Dequeue: извлекает и возвращает первый элемент очереди
Enqueue: добавляет элемент в конец очереди
Peek: просто возвращает первый элемент из начала очереди без его удаления
Посмотрим применение очереди на практике:
using System;
using System.Collections.Generic;
namespace Collections
{
class Program
{
static void Main(string[] args)
{
Queue<int> numbers = new Queue<int>();
numbers.Enqueue(3); // очередь 3
numbers.Enqueue(5); // очередь 3, 5
numbers.Enqueue(8); // очередь 3, 5, 8
// получаем первый элемент очереди
int queueElement = numbers.Dequeue(); //теперь очередь 5, 8
Console.WriteLine(queueElement);
Queue<Person> persons = new Queue<Person>();
persons.Enqueue(new Person() { Name = "Tom" });
persons.Enqueue(new Person() { Name = "Bill" });
persons.Enqueue(new Person() { Name = "John" });
// получаем первый элемент без его извлечения
Person pp = persons.Peek();
Console.WriteLine(pp.Name);
Console.WriteLine("Сейчас в очереди {0} человек", persons.Count);
// теперь в очереди Tom, Bill, John
foreach (Person p in persons)
{
Console.WriteLine(p.Name);
}
// Извлекаем первый элемент в очереди - Tom
Person person = persons.Dequeue(); // теперь в очереди Bill, John
Console.WriteLine(person.Name);
Console.ReadLine();
}
}
class Person
{
public string Name { get; set; }
}
}
Стек Stack<T>
Класс Stack<T> представляет коллекцию, которая использует алгоритм LIFO ("последний вошел - первый вышел"). При такой организации каждый следующий добавленный элемент помещается поверх предыдущего. Извлечение из коллекции происходит в обратном порядке - извлекается тот элемент, который находится выше всех в стеке.
В классе Stack можно выделить два основных метода, которые позволяют управлять элементами:
Push: добавляет элемент в стек на первое место
Pop: извлекает и возвращает первый элемент из стека
Peek: просто возвращает первый элемент из стека без его удаления
Посмотрим на примере:
using System;
using System.Collections.Generic;
namespace Collections
{
class Program
{
static void Main(string[] args)
{
Stack<int> numbers = new Stack<int>();
numbers.Push(3); // в стеке 3
numbers.Push(5); // в стеке 5, 3
numbers.Push(8); // в стеке 8, 5, 3
// так как вверху стека будет находиться число 8, то оно и извлекается
int stackElement = numbers.Pop(); // в стеке 5, 3
Console.WriteLine(stackElement);
Stack<Person> persons = new Stack<Person>();
persons.Push(new Person() { Name = "Tom" });
persons.Push(new Person() { Name = "Bill" });
persons.Push(new Person() { Name = "John" });
foreach (Person p in persons)
{
Console.WriteLine(p.Name);
}
// Первый элемент в стеке
Person person = persons.Pop(); // теперь в стеке Bill, Tom
Console.WriteLine(person.Name);
Console.ReadLine();
}
}
class Person
{
public string Name { get; set; }
}
}
Работу стека можно представить следующей иллюстрацией:
Словарь Dictionary<T, V>
Еще один распространенный тип коллекции представляют словари. Словарь хранит объекты, которые представляют пару ключ-значение. Каждый такой объект является объектом класса KeyValuePair<TKey, TValue>. Благодаря свойствам Key иValue, которые есть у данного класса, мы можем получить ключ и значение элемента в словаре.
Рассмотрим на примере использование словарей:
Dictionary<int, string> countries = new Dictionary<int, string>(5);
countries.Add(1, "Russia");
countries.Add(3, "Great Britain");
countries.Add(2, "USA");
countries.Add(4, "France");
countries.Add(5, "China");
foreach (KeyValuePair<int, string> keyValue in countries)
{
Console.WriteLine(keyValue.Key + " - " + keyValue.Value);
}
// получение элемента по ключу
string country = countries[4];
// изменение объекта
countries[4] = "Spain";
// удаление по ключу
countries.Remove(2);
Класс словарей также, как и другие коллекции, предоставляет методы Add и Remove для добавления и удаления элементов. Только в случае словарей в метод Add передаются два параметра: ключ и значение. А метод Remove удаляет не по индексу, а по ключу.
Так как в нашем примере ключами является объекты типа int, а значениями - объекты типа string, то словарь в нашем случае будет хранить объекты KeyValuePair<int, string>. В цикле foreach мы их можем получить и извлечь их них ключ и значение.
Кроме того, мы можем получить отдельно коллекции ключей и значений словаря:
Dictionary<char, Person> people = new Dictionary<char, Person>();
people.Add('b', new Person() { Name = "Bill" });
people.Add('t', new Person() { Name = "Tom" });
people.Add('j', new Person() { Name = "John" });
foreach (KeyValuePair<char, Person> keyValue in people)
{
// keyValue.Value представляет класс Person
Console.WriteLine(keyValue.Key + " - " + keyValue.Value.Name);
}
// перебор ключей
foreach (char c in people.Keys)
{
Console.WriteLine(c);
}
// перебор по значениям
foreach (Person p in people.Values)
{
Console.WriteLine(p.Name);
}
Здесь в качестве ключей выступают объекты типа char, а значениями - объекты Person. Используя свойство Keys, мы можем получить ключи словаря, а свойство Values соответственно хранит все значения в словаре.
Для добавления необязательно применять метод Add(), можно использовать сокращенный вариант:
Dictionary<char, Person> people = new Dictionary<char, Person>();
people.Add('b', new Person() { Name = "Bill" });
people['a'] = new Person() { Name = "Alice" };
Несмотря на то, что изначально в словаре нет ключа 'a' и соответствующего ему элемента, то он все равно будет установлен. Если же он есть, то элемент по ключу 'a' будет заменен на новый объект new Person() { Name = "Alice" }