123. SortedList

שבוע בר-השוואה וממוין טוב
Comparisons, Dictionaries

לפעמים כאשר אנחנו מתעסקים באוסף של נתונים, חשוב לנו, מסיבות כאלה ואחרות, שהוא תמיד יהיה ממוין.

לדוגמה, מיון נתונים לפי תאריך, או מיון של שמות אלפא-ביתית, או מיון עובדים לפי השכר שלהם.

אחת האפשרויות היא להשתמש במבנה נתונים שנקרא

SortedList המאפשר לנו לדאוג שהאיברים יהיו בסדר הנכון כבר בהכנסתם.

מבנה זה מזכיר Dictionary (ולכן גם מממש IDictionary):

1
2
3
4
5
6
7
8
9
SortedList<string, int> fruitNameToAmount =
    new SortedList<string, int>();
fruitNameToAmount["Banana"] = 4;
fruitNameToAmount["Apple"] = 8;
fruitNameToAmount["Mango"] = 15;
fruitNameToAmount["Grapes"] = 16;
fruitNameToAmount["Orange"] = 23;
fruitNameToAmount["Peache"] = 42;

המיון מתבצע לפי הKey. כעת כשנרוץ על הSortedList נקבל:

1
2
3
4
5
6
foreach (KeyValuePair<string, int> fruitToAmount infruitNameToAmount)
{
    Console.WriteLine("{0} - {1}",
                      fruitToAmount.Key,
                      fruitToAmount.Value);
}

Apple - 8
Banana - 4
Grapes - 16
Mango - 15
Orange - 23
Peache - 42

כמובן, איך אפשר בלי, קיים גם Overload לConstructor שמקבל Comparer לפיו נשווה את המפתחות:

1
2
SortedList<string, int> fileToSize =
    new SortedList<string, int>(new FolderLocationComparer());

איך זה עובד? בפועל מוחזקים שני מערכים – אחד של TKey והשני של TValue. בכל הכנסה מתבצע חיפוש של המקום המתאים במערך של המפתחות, ומתבצעת העתקה של כל המערך למערך אחר, עם ההוספה של המפתח החדש. במערך של הערכים פשוט מופיע כל ערך בהתאם למקום שבו מופיע המפתח שלו. כך שבעצם בכל הכנסה מתבצעות שתי העתקות של מערכים.

הדבר מאוד לא יעיל בהכנסות, אבל יכול להיות שימושי אם האוסף שלכם לא משתנה הרבה, ואכפת לכם שהוא תמיד יהיה ממוין.

המשך יום ממוין (אבל שלא משתנה יותר מדי)

שתף