List ב-C#: Add, Remove, Contains, Find ו-Sort

List<T> הוא אוסף מסודר שגדל וקטן כשמוסיפים ומוחקים פריטים. הוא נמצא ב-System.Collections.Generic, עובד עם אינדקסים כמו מערך (list[0]), והוא הבחירה הרגילה ב-C# עבור "הרבה דברים".

יצירת רשימה והוספת פריטים

פרמטר הטיפוס שבסוגריים המשולשים אומר מה הרשימה מחזיקה: List<string>, List<int>, List<Order>.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var cart = new List<string>();
        cart.Add("apples");
        cart.Add("bread");

        var names = new List<string> { "Ana", "Ben" };  // collection initializer
        names.Insert(0, "Zoe");                         // at position 0
        names.AddRange(new[] { "Chloe", "Dev" });        // several at once

        var fromArray = new List<int>(new[] { 3, 1, 2 });

        Console.WriteLine(cart.Count);
        Console.WriteLine(string.Join(", ", names));
        Console.WriteLine(names[1]);
        names[1] = "Ana B.";                             // replace by index
        Console.WriteLine(names[1]);
        Console.WriteLine(fromArray.Count);
    }
}

פלט:

2
Zoe, Ana, Ben, Chloe, Dev
Ana
Ana B.
3

Count הוא מאפיין, לא מתודה (מערכים משתמשים ב-Length, ל-LINQ יש מתודה Count(); ברשימה השתמשו במאפיין). Insert מזיז כל פריט שאחריו מקום אחד קדימה, ולכן הכנסה לתחילת רשימה גדולה לוקחת זמן ביחס לגודל שלה. Add לסוף היא הפעולה הזולה.

מחיקת פריטים

יש ארבע דרכים למחוק, לפי מה שאתם יודעים על הפריט:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var scores = new List<int> { 40, 85, 62, 40, 91, 55 };

        bool removed = scores.Remove(40);          // first 40 only
        Console.WriteLine(removed + ": " + string.Join(", ", scores));

        Console.WriteLine(scores.Remove(100));     // not found, nothing happens

        scores.RemoveAt(0);                        // by index
        Console.WriteLine(string.Join(", ", scores));

        int count = scores.RemoveAll(s => s < 60); // every match
        Console.WriteLine(count + " removed: " + string.Join(", ", scores));

        try
        {
            scores.RemoveAt(10);
        }
        catch (ArgumentOutOfRangeException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        scores.Clear();
        Console.WriteLine(scores.Count);
    }
}

פלט:

True: 85, 62, 40, 91, 55
False
62, 40, 91, 55
2 removed: 62, 91
Caught ArgumentOutOfRangeException
0

Remove מקבל ערך ומוחק רק את ההתאמה הראשונה. כדי למחוק את כל העותקים של ערך, השתמשו ב-RemoveAll(s => s == 40). אינדקס שגוי ברשימה זורק ArgumentOutOfRangeException (מערך זורק במקום זאת IndexOutOfRangeException), גם עבור list[i] וגם עבור RemoveAt(i). RemoveRange(index, count) מוחק בלוק.

Count מול Capacity

רשימה שומרת את הפריטים שלה במערך פנימי. Capacity הוא הגודל של המערך הזה; Count הוא כמה משבצות בשימוש. כש-Count מגיע ל-Capacity, ה-Add הבא מקצה מערך בגודל כפול ומעתיק אליו הכול.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var list = new List<int>();
        Console.WriteLine("Count " + list.Count + ", Capacity " + list.Capacity);

        for (int i = 1; i <= 9; i++)
        {
            list.Add(i);
            Console.WriteLine("Count " + list.Count + ", Capacity " + list.Capacity);
        }

        var sized = new List<int>(1000); // preallocate when you know the size
        Console.WriteLine("Count " + sized.Count + ", Capacity " + sized.Capacity);
    }
}

פלט:

Count 0, Capacity 0
Count 1, Capacity 4
Count 2, Capacity 4
Count 3, Capacity 4
Count 4, Capacity 4
Count 5, Capacity 8
Count 6, Capacity 8
Count 7, Capacity 8
Count 8, Capacity 8
Count 9, Capacity 16
Count 0, Capacity 1000

ההכפלה אומרת שרוב הקריאות ל-Add הן רק כתיבה למשבצת פנויה. אם אתם יודעים בערך כמה פריטים יגיעו, העבירו את המספר לבנאי כדי לדלג על ההעתקות שבדרך. שימו לב של-new List<int>(1000) עדיין יש Count של 0: list[0] עליה זורק חריגה. Capacity הוא מקום, לא פריטים.

חיפוש: Contains, IndexOf, Find, Exists

using System;
using System.Collections.Generic;

class Product
{
    public string Name;
    public decimal Price;
    public Product(string name, decimal price) { Name = name; Price = price; }
}

class Program
{
    static void Main()
    {
        var tags = new List<string> { "new", "sale", "gift" };
        Console.WriteLine(tags.Contains("sale"));
        Console.WriteLine(tags.IndexOf("gift"));
        Console.WriteLine(tags.IndexOf("used"));

        var products = new List<Product>
        {
            new Product("Mug", 8.50m),
            new Product("Lamp", 32.00m),
            new Product("Pen", 1.20m),
        };

        Product lamp = products.Find(p => p.Name == "Lamp");
        Console.WriteLine(lamp.Price);

        List<Product> cheap = products.FindAll(p => p.Price < 10m);
        Console.WriteLine(cheap.Count + " cheap items");

        Console.WriteLine(products.Exists(p => p.Price > 100m));
        Console.WriteLine(products.FindIndex(p => p.Name == "Pen"));

        Product missing = products.Find(p => p.Name == "Desk");
        Console.WriteLine(missing == null);

        // Contains compares references for a class without Equals:
        Console.WriteLine(products.Contains(new Product("Mug", 8.50m)));
    }
}

פלט:

True
2
-1
32.00
2 cheap items
False
2
True
False

Find מחזיר את ההתאמה הראשונה, או את ערך ברירת המחדל של הטיפוס (null למחלקה) כששום דבר לא מתאים, ולכן בדקו לפני שמשתמשים בתוצאה. השורה האחרונה מדפיסה False כי Contains משתמש ב-Equals, ומחלקה בלי דריסה של Equals משווה הפניות: Product חדש עם אותם שדות הוא אובייקט אחר. חפשו לפי מאפיין עם Exists או Find, או דרסו את Equals ואת GetHashCode במחלקה.

כל אחת מהמתודות האלה עוברת על הרשימה מההתחלה, ולכן כל קריאה היא O(n). לחיפושים חוזרים לפי מפתח, Dictionary עונה בזמן קבוע.

מיון רשימה

Sort() ממיין במקום לפי הסדר הטבעי של הפריטים. העבירו lambda של השוואה כדי למיין לפי כל דבר אחר.

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

class Player
{
    public string Name;
    public int Score;
    public Player(string name, int score) { Name = name; Score = score; }
    public override string ToString() { return Name + " " + Score; }
}

class Program
{
    static void Main()
    {
        var numbers = new List<int> { 5, 2, 9, 1 };
        numbers.Sort();
        Console.WriteLine(string.Join(", ", numbers));

        numbers.Sort((a, b) => b.CompareTo(a)); // descending
        Console.WriteLine(string.Join(", ", numbers));

        var players = new List<Player>
        {
            new Player("Ana", 120),
            new Player("Ben", 95),
            new Player("Chloe", 150),
        };

        players.Sort((a, b) => a.Score.CompareTo(b.Score)); // by property
        Console.WriteLine(string.Join(", ", players));

        List<Player> byName = players.OrderByDescending(p => p.Name).ToList(); // new list
        Console.WriteLine(string.Join(", ", byName));
        Console.WriteLine(string.Join(", ", players)); // unchanged by OrderBy
    }
}

פלט:

1, 2, 5, 9
9, 5, 2, 1
Ben 95, Ana 120, Chloe 150
Chloe 150, Ben 95, Ana 120
Ben 95, Ana 120, Chloe 150

השוואה מחזירה מספר שלילי כש-a צריך לבוא ראשון, חיובי כש-b צריך לבוא ראשון, ואפס כשהם שווים; CompareTo מפיקה בדיוק את זה. שני הבדלים בין Sort ל-OrderBy של LINQ חשובים בפועל:

• Sort משנה את הרשימה; OrderBy מחזיר רצף חדש ולא נוגע ברשימה.
• Sort לא יציב: פריטים שמשתווים יכולים להחליף מקומות. OrderBy יציב, ו-ThenBy מוסיף מפתח שני: players.OrderBy(p => p.Score).ThenBy(p => p.Name).

קריאה ל-Sort() על רשימה של מחלקה שלכם בלי השוואה זורקת InvalidOperationException, כי הרשימה לא יודעת איך לסדר את הפריטים. או שתעבירו השוואה, או שתממשו IComparable<T> במחלקה.

Reverse() הופך את הסדר במקום. מכיוון ש-System.Linq מגדיר גם הרחבה בשם Reverse, list.Reverse() על List<T> בוחר בגרסה שעובדת במקום, שלא מחזירה כלום.

לולאות, ומחיקה תוך כדי מעבר

foreach קוראת כל פריט לפי הסדר. לולאת for נותנת גם את האינדקס. מה שאי אפשר לעשות זה להוסיף או למחוק פריטים באמצע foreach על אותה רשימה:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var orders = new List<int> { 120, 15, 80, 5, 60 };

        try
        {
            foreach (int total in orders)
            {
                if (total < 20) orders.Remove(total);
            }
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        orders = new List<int> { 120, 15, 80, 5, 60 };

        // Fix 1: RemoveAll
        var a = new List<int>(orders);
        a.RemoveAll(t => t < 20);
        Console.WriteLine(string.Join(", ", a));

        // Fix 2: loop backwards, so removals do not shift items you have not seen
        var b = new List<int>(orders);
        for (int i = b.Count - 1; i >= 0; i--)
        {
            if (b[i] < 20) b.RemoveAt(i);
        }
        Console.WriteLine(string.Join(", ", b));
    }
}

פלט:

Caught InvalidOperationException
120, 80, 60
120, 80, 60

החריגה היא InvalidOperationException עם ההודעה "Collection was modified; enumeration operation may not execute." לולאת for קדימה לא זורקת חריגה, אבל היא מדלגת בשקט על הפריט שבא מיד אחרי כל פריט שמוחקים, כי הכול זז אינדקס אחד אחורה. מעבר מהסוף להתחלה מונע את זה. פתרון שלישי הוא מעבר על עותק: foreach (var t in orders.ToList()).

שינוי של מאפיין של פריט בתוך foreach (למשל order.Status = "sent") בסדר. הוספה או מחיקה של פריטים שוברות את ה-enumerator, וכך גם החלפה של פריט דרך האינדקסר (orders[i] = 0).

המרה בין רשימות למערכים

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

class Program
{
    static void Main()
    {
        string[] cities = { "Oslo", "Lima", "Pune" };

        List<string> list = cities.ToList();       // or new List<string>(cities)
        list.Add("Kyiv");

        string[] back = list.ToArray();
        Console.WriteLine(back.Length);
        Console.WriteLine(cities.Length);           // the original array is unchanged

        List<int> lengths = list.ConvertAll(c => c.Length);
        Console.WriteLine(string.Join(", ", lengths));
        Console.WriteLine(string.Join(" / ", list));
    }
}

פלט:

4
3
4, 4, 4, 4
Oslo / Lima / Pune / Kyiv

בשני הכיוונים האיברים מועתקים לאחסון חדש, ולכן שינוי של הרשימה בהמשך לא משפיע על המערך. ConvertAll היא הגרסה של הרשימה עצמה ל-Select(...).ToList() של LINQ. הדפסה של רשימה עם Console.WriteLine(list) מציגה את שם הטיפוס (System.Collections.Generic.List`1[System.String]); השתמשו ב-string.Join.

טבלת עזר מהירה

טעויות נפוצות

• מחיקה בתוך foreach. זורקת InvalidOperationException; השתמשו ב-RemoveAll או בלולאת for מהסוף להתחלה.
• ציפייה ש-Remove(x) ימחק כל עותק. הוא מוחק את הראשון; השתמשו ב-RemoveAll.
• שימוש ב-Contains על אובייקטים בלי Equals. הוא משווה הפניות; חפשו לפי מאפיין עם Exists.
• גישה לפי אינדקס לרשימה שנוצרה עם capacity. new List<int>(10) ריקה; הוסיפו קודם פריטים.
• הנחה ש-Sort שומר על הסדר בין פריטים שווים. הוא לא; השתמשו ב-OrderBy כשהסדר בין שווים חשוב.
• השמה של רשימה כדי לשתף אותה, ואז הפתעה משינויים. var copy = list; היא אותה רשימה; new List<T>(list) הוא עותק.