Материал: Лекція 11. Множини
Лекція 9. Множини
План
Означення множини, операції над множинами
Класи HashSet<T> i SortedSet<T>
Методи розширення Linq для роботи з множинами
1. Означення множини, операції над множинами
Множина у математиці - це сукупність однотипних елементів, що розглядається як одне ціле. Наприклад, множина цілих чисел, множина дійсних чисел. Елементи множини не повторюються. Кількість елементів множини називається її потужністю. Множина, яка не містить елементів, називається пустою.
У програмуванні кількість елементів множини є скінченною.
Операції з множинами (булеві операції).
Основні операції з множинами: об'єднання, перетин, різниця, симетрична різниця.
Об'єднання
Отримання нової множини, яка містить всі елементи початкових множин.
Перетин
Отримання нової множини, яка містить однакові елементи з обох множин.
Різниця
Отримання нової множини, яка містить елементи першої множини, які відсутні в другій.
Симетрична різниця
Вибір з обох множин елементів, які не належать одночасно обом множинам.
2. Класи HashSet<T> i SortedSet<T>
Для роботи з множинами в бібліотеці класів .NET Framework є два універсальних класи HashSet <T> і SortedSet <T>, які знаходяться в просторі імен System.Collections.Generic. Різниця між ними в тому, що SortedSet <T> представляє впорядковану множину.
Ці класи реалізують інтерфейс ISet<T>, який надає методи для роботи з множинами.
2.1. Клас HashSet<T>
Клас HashSet <T> забезпечує високопродуктивні операції з множинами. Множина - це колекція, яка не містить дублікатів елементів, і елементи яких не впорядковані.
Нижче наведено найбільш використовувані конструктори, визначені в класі HashSet <T>:
public HashSet ()
public HashSet (IEnumerable <T> collection)
public HashSet (IEqualityCompare comparer)
public HashSet (IEnumerable <T> collection, IEqualityCompare comparer)
У першій формі конструктора створюється порожня множина, а в другій формі - множина, що складається з елементів вказаної колекції collection. У третій формі конструктора допускається вказувати спосіб порівняння за допомогою параметра comparer. А в четвертій формі створюється множина, що складається з елементів вказаної колекції collection, і використовується заданий спосіб порівняння comparer. Є також п'ята форма конструктора даного класу, в якій допускається форматувати множину послідовно впорядкованими даними.
Операції над множинами, визначені в класі HashSet
Операції (методи) |
Математичний еквівалент |
UnionWith |
Об’єднання |
IntersectWith |
Перетин |
ExceptWith |
Різниця |
SymmetricExceptWith |
Симетрична різниця |
Окрім перерахованих операцій, клас HashSet <T> надає методи для додавання елементів, визначення рівності множин, перекриття множин і того, чи є множина підмножиною або супермножиною іншої множини.
Основні методи класу HashSet <T>
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1?view=netframework-4.7.2
Add(T) |
Додає вказаний елемент до колекції. |
Clear() |
Видаляє всі елементи з колекції. |
Contains(T) |
Визначає, чи є вказаний елемент в колекції. |
CopyTo(T[]) |
Копіює елементи колекції в масив. |
CopyTo(T[], Int32) |
Копіює елементи колекції в масив, починаючи з вказаного індексу масиву. |
CopyTo(T[], Int32, Int32) |
Копіює вказану кількість елементів в масив, починаючи з вказаного індексу масиву. |
Equals(Object) |
Визначає, чи рівний вказаний елемент колекції поточному об’єкту. |
ExceptWith(IEnumerable<T>) |
Видаляє всі елементи вказаної колекції, починаючи з поточного об’єкту. |
GetType() |
Повертає тип поточного елементу колекції. |
IsSubsetOf(IEnumerable<T>) |
Визначає, чи є колекція підмножиною вказаної колекції. |
IsSupersetOf(IEnumerable<T>) |
Визначає, чи є колекція надмножиною вказаної колекції. |
Remove(T) |
Видаляє вказаний елемент з колекції |
RemoveWhere(Predicate<T>) |
Видаляє всі елементи з колекції, які відповідають умовам, визначеним вказаним предикатом |
SetEquals(IEnumerable<T>) |
Визначає, чи містять дві колекції однакові елементи. |
ToString() |
Перетворює елемент колекції в рядок. |
TrimExcess() |
Встановлює ємність колекції HashSet <T> рівній фактичній кількості елементів. |
TryGetValue(T, T) |
Шукає в колекції вказане значення і повертає рівне значення, якщо таке є. |
Приклад 1. Без використання класу HashSet
Створити 2 лінійні списки цілих чисел (класу List<T>), у яких є однакові елементи. Створити список unionList, який містить елементи обох списків без повторень (об’єднання). Створити список intersectList, який містить елементи, які є в обох списках (перетин).
class Program
{
static void PrintList(List<int> list)
{
Console.Write("{ ");
foreach (var item in list)
{
Console.Write(item);
Console.Write(" ");
} Console.WriteLine("}");
}
static void Main(string[] args)
{
List<int> firstList = new List<int>();
firstList.Add(1);
firstList.Add(2);
firstList.Add(3);
firstList.Add(4);
firstList.Add(5);
Console.Write("firstList = ");
PrintList(firstList);
List<int> secondList = new List<int>();
secondList.Add(2);
secondList.Add(4);
secondList.Add(6);
Console.Write("secondList = ");
PrintList(secondList);
List<int> unionList = new List<int>();
unionList.AddRange(firstList);
for (int i = unionList.Count - 1; i >= 0; i--)
{
if (secondList.Contains(unionList[i]))
{
unionList.RemoveAt(i);
}
}
unionList.AddRange(secondList);
Console.Write("union = ");
PrintList(unionList);
List<int> intersectList = new List<int>();
intersectList.AddRange(firstList);
for (int i = intersectList.Count - 1; i >= 0; i--)
{
if (!secondList.Contains(intersectList[i]))
{
intersectList.RemoveAt(i);
}
}
Console.Write("intersect = ");
PrintList(intersectList);
Console.ReadKey();
}
}
Реалізуємо той самий приклад з використанням класу HashSet.
class Program
{
static void PrintList(HashSet<int> list)
{
Console.Write("{ ");
foreach (var item in list)
{
Console.Write(item);
Console.Write(" ");
}
Console.WriteLine("}");
}
static void Main(string[] args)
{
HashSet<int> firstList = new HashSet<int>(); //перша множина
firstList.Add(1);
firstList.Add(2);
firstList.Add(3);
firstList.Add(4);
firstList.Add(5);
Console.Write("firstList = ");
PrintList(firstList);
HashSet<int> secondList = new HashSet<int>(); //друга множина
secondList.Add(2);
secondList.Add(4);
secondList.Add(6);
Console.Write("secondList = ");
PrintList(secondList);
//Об'єднання множин
HashSet<int> unionList = new HashSet<int>(firstList);
unionList.UnionWith(secondList); //Об'єднання множин
Console.Write("union = ");
PrintList(unionList);
//перетин множин
HashSet <int> intersectList = new HashSet<int>(firstList);
intersectList.IntersectWith(secondList);
Console.Write("intersect = ");
PrintList(intersectList);
Console.ReadKey();
}
}
Важливо
При роботі з множинами в .NET Framework необхідно враховувати наступну особливість.
Результат виконання операції з множинами зберігається в тій змінній, для якої був викликаний відповідним методом, переписуючи початкову колекцію. Тобто, перша колекція буде змінена.
Приклад 2
class Program
{
static void Main()
{
HashSet<int> evenNumbers = new HashSet<int>();
HashSet<int> oddNumbers = new HashSet<int>();
for (int i = 0; i < 5; i++)
{
// Заповнення першої колекції evenNumbers парними числами
evenNumbers.Add(i * 2);
// Заповнення другої колекції oddNumbers непарними числами
oddNumbers.Add((i * 2) + 1);
}
Console.Write("evenNumbers contains {0} elements: ", evenNumbers.Count);
DisplaySet(evenNumbers);
Console.Write("oddNumbers contains {0} elements: ", oddNumbers.Count);
DisplaySet(oddNumbers);
// Створення нової колекції numbers з чисел evenNumbers.
HashSet<int> numbers = new HashSet<int>(evenNumbers);
Console.WriteLine("numbers UnionWith oddNumbers...");
//Об’єднання множин
numbers.UnionWith(oddNumbers);
Console.Write("numbers contains {0} elements: ", numbers.Count);
DisplaySet(numbers);
Console.ReadKey();
}
static void DisplaySet(HashSet<int> set)
{
Console.Write("{");
foreach (int i in set)
{
Console.Write(" {0}", i);
}
Console.WriteLine(" }");
}
}
Елементами множини можуть бути рядки чи об’єкти класів.