Нека първо разгледаме списъчните колекции в .NET Framework, тъй като те за по-прости от речниковите и работата с тях е по-интуитивна.
Интерфейсът IList
Всеки клас, който имплементира интерфейса IList, поддържа множество от стандартни операции за работа с индексиран списък: достъп до елементите по индекс, добавяне на елемент (Add(…)), вмъкване на елемент (Insert(…)), търсене на елемент (IndexOf(…)), изтриване по индекс или по стойност (RemoveAt(…), Remove(…)) и др.
Класът ArrayList
Класът ArrayList имплементира интерфейса IList чрез масив, чийто размер се променя динамично при нужда. Всяка инстанция на този клас предварително заделя буферна памет (Capacity) за елементите, които предстои да бъдат добавени. При запълване на буферната памет се заделя нова памет, като най-често капацитетът се удвоява.
ArrayList – пример
Следният пример демонстрира работата с ArrayList и начина на употреба на най-честите операции, прилагани върху него:
static void Main()
{
ArrayList list = new ArrayList();
for (int i = 1; i <= 10; i++)
{
list.Add(i); // Adds i at the end of the ArrayList
}
list.Insert(3, 123); // Inserts 123 element number 3
list.RemoveAt(7); // Removes element with the index 7
list.Remove(2); // Removes element with value 2
list[1] = 500; // Changes element with index 1
list.Sort(); // Sorting in ascending order
int[] arr = (int[])list.ToArray(typeof(int));
foreach(int i in arr)
{
Console.Write("{0} ",i);
}
Console.WriteLine();
// Result: 1 4 5 6 8 9 10 123 500
}
|
В горния пример използвахме някои от методите на класа ArrayList. Използвахме конструктора по подразбиране за да създадем списъка list.
Капацитет на ArrayList
Ако предварително се знае приблизителният брой елементи, които ще се добавят в ArrayList, е препоръчително да се укаже този брой още при създаването му. Това намалява броя на операциите по промяна на размера, което значително подобрява производителността.
Преоразмеряването е бавна и неефективна операция, защото е свързана със заделяне на нова памет за елементите на масива и преместване на всички стойности от старата в новата памет.
Следващият код създава ArrayList съдържащ 100 000 цели числа:
ArrayList list = new ArrayList();
for (int i=0; i<100000; i++)
{
list.Add(i);
}
|
За сравнение следния код прави същото, но за два пъти по кратко време:
ArrayList list = new ArrayList(100000);
for (int i=0; i<100000; i++)
{
list.Add(i);
}
|
За да се премахнат елементи от ArrayList се използват методите Remove(…), RemoveAt(…), RemoveRange(…) или Clear(). Когато се премахнат елементи, останалите, които са с по-големи индекси, автоматично се изместват наляво за да заемат мястото на вече премахнатите. Примерно, ако премахнете елемент с индекс 5, елементът с индекс 6 става с индекс 5, елементът с индекс 7 става с индекс 6 и т.н.
За да се вмъкнат елементи в ArrayList се използват методите Insert(…) и InsertRange(…), като им се подава като аргумент позицията, на която се вмъкват елементите. Тъй като при вмъкване и изтриване на елемент от ArrayList се налага преместване на елементите от списъка и евентуално заделяне на памет, тези операции са бавни (работят с линейна сложност).
Както вече отбелязахме, всяка инстанция на ArrayList автоматично заделя памет за новите елементи. Тя обаче не се грижи за автоматичното освобождаване на тази памет при премахване на елементи от колекцията. За да намалите размера на ArrayList до настоящия брой елементи се използва метода TrimToSize(). Следващият пример добавя 1000 цели числа в ArrayList, изтрива първите 500 и след това намалява размера на колекцията до размера, нужен за останалите 500:
ArrayList list = new ArrayList (1000);
for (int i=0; i<1000; i++) // Add items
{
list.Add(i);
}
list.RemoveRange(0, 500); // Remove first 500 items
list.TrimToSize(); // Resize the capacity of ArrayList
| Други списъчни колекции
Освен ArrayList в .NET Framework стандартно са имплементирани и някои други списъчни колекции, като опашки и стекове.
Опашка – Queue
В .NET Framework освен ArrayList са дефинирани и други списъчни структури. Една от тях е така наречената опашка – Queue. Опашката представлява колекция с поведение от вида "first-in, first-out (FIFO)" и е реализирана чрез цикличен масив. Класическа аналогия за тази структура е опашката за билети. Този, който първи се е наредил на опашката, ще може първи да си купи билет.
Опашката е структура, която може да се използва при управление на достъпа до ограничени ресурси. Примерно, ако трябва да изпратите съобщения през даден ресурс който може да обработва само по едно наведнъж, е подходящо да се използва опашка, която да съхранява съобщенията, които чакат да бъдат обработени.
Характерни за класа Queue са двата метода Enqueue(…) и Dequeue(…), служещи съответно за добавяне и изваждане на елемент от опашката. Enqueue(…) добавя елемент в края на опашката, а Dequeue(…) изважда елемент от началото й.
Стек – Stack
Подобно на опашката стекът е друга списъчна структура от пространството System.Collections. За разлика обаче от опашката, стекът представлява структура с поведение от вида "last-in, first-out (LIFO)", която се реализира чрез масив. Той работи на принципа "който е влязъл последен в стека, стои най-отгоре" – точно като колона от чинии, поставени една върху друга.
Основните методи за добавяне и премахване на елемент от стека са Push(…) и Pop(). Push(…) добавя елемент към върха на стека, а Pop() връща елемента от върха на стека, като го премахва. Класът Stack съдържа и още метода Peek(), който връща елемента от върха на стека, но без да го премахва.
Други стандартни списъчни структури са StringCollection и BitArray. StringCollection е аналог на ArrayList, но за string обекти. BitArray, както подсказва и името му, реализира масив от булеви стойности, като съхранява всяка една от тях в 1 бит.
Queue и Stack – примери
Ето и два кратки примера за използването на стек и опашка:
Queue queue = new Queue();
queue.Enqueue("1. IBM");
queue.Enqueue("2. HP");
queue.Enqueue("3. Microsoft");
while (queue.Count > 0)
{
string computer = (string) queue.Dequeue();
Console.Write("{0} ", computer);
}
Console.WriteLine();
// Result: 1. IBM 2. HP 3. Microsoft
|
В следващия пример на мястото на опашка се ползва стек:
Stack stack = new Stack();
stack.Push("1. IBM");
stack.Push("2. HP");
stack.Push("3. Microsoft");
while (stack.Count > 0)
{
string computer = (string) stack.Pop();
Console.Write("{0} ", computer);
}
Console.WriteLine();
// Result: 3. Microsoft 2. HP 1. IBM
|
Сподели с приятели: |