list

 פוסט זה ממשיך את הסדרה שדנה ב- STL containers. לקבלת רקע מומלץ לקרוא את הפוסט הקודם בנושא. בכל אופן, אשתדל לספק הסבר קצר ומספק גם כאן.

מה זה list? זהו סוג נוסף של sequential container.
מה זה container? זהו class שמאחסן קבוצה של אובייקטים. האובייקטים יהיו תמיד מאותו סוג. למשל: container של int או של string או של אוביקטים מסוג כלשהו. ה-containers  הם Templates כך שאפשר להתאים אותם לכל data type.
מה המקבילה של c ל-container? מערך (array) למשל. המערך מאורגן כמו ה-vector container עליו נרחיב מיד.
מה זה sequential container? מדובר בסוג של containers בהם האלמנטים מסודרים אחד אחרי השני. המקום של כל אלמנט ב-container נקבע בזמן ההכנסה. אפשר להכניס אלמנט להתחלה, לסוף או לדחוף אותו בין אלמנטים קיימים.
אפשר לקבל דוגמאות sequential containers?  דוגמאות:  vector וגם list. על vector דיברנו בפוסט הקודם - ראה קישור למעלה.
מה ההבדל בין list לבין vector?
הנה 4 הבדלים:
1. בוקטור יש אפשרות לגישה ישירה לכל אחד מהאלמנטים  (random access).
הנה למשל גישה לאלמנט שנמצא במקום ה-n:

 a=vect[n];

אפשר גם כך:

a = vect.at(n);

וגם כך:

iterator = vect.begin();

a = vect(iterator + 2);

ב-list  כל הגישות הנ"ל לא נתמכות.  list  היא רשימה מקושרת. כל אחד מהאלמנטים מצביע על האלמנט שאחריו והאלמנט שלפניו. הם בהחלט לא חיבים להיות מסודרים בכתובות עוקבות. הכתובת בזיכרון של כל אלמנט נמצאת אצל השכנים הסמוכים אליו. לפיכך, גישה ישירה לכתובת לא נתמכת. אז איך ניגשים לאלמנט ב-list? מצביעים עם האיטרטור על אלמנט ברשימה - למשל:

iterator = vect.begin();

או

iterator = vect.end();

ומכאן אפשר לצעוד עם ה-iterator קדימה ואחורה: ++iterator ו- --iterator.

לגבי iterators - נגענו קצת ב-iterators בפוסט על ה-vectors ויש סיכוי שיהיה פוסט מיוחד לנושא. בכל אופן, ה-list לא תומך ב-random access iterator. מהסיבות שפורטו בסעיף זה. הנה דוגמא לשגיאה:

iterator = list(begin() + 2);

ב-list זה לא יתקמפל. 

2.  list יעילה מאד בהכנסה והוצאה של אלמנטים ל-container. אין צורך להזיז כלום. פשוט לשנות ערכים של מצביעים.  גם פעולת המיון קלה יותר.הכנסה והוצאה של אלמנטים בוקטור יקרה הרבה יותר. היא כרוכה ב-relocation של אברים. גם הגדלה של הוקטור יכולה לדרוש relocation.

3. ה-list דורשת מיקום איחסון למצביעים. ככל שהרשימה גדולה יותר והאלמנטים בה קטנים יותר, התשלום הנוסף ביחדות אחסון יכול להיות משמעותי יותר.

4. מתודות. הרבה מהמתודות של list ו-vector משותפות. אבל יש גם הבדלים. הנה הרשימה של המתודות היחודיות רק ל-list:

.

splice - העברת אלמנטים מרשימה אחרת. splice מבצעת למעשה פעולת move, כאשר היא מוחקת מה-container המקורי את האלמנטים שהועברו ממנו.

remove - מוחקת אלמנטים עם ערך מסוים.

unique - מוחקת את כל האלמנטים מלבד הראשון מכל האלמנטים בעלי ערך מסוים.

merge - איחוד רשימות.

sort - מיון.

reverse - הפיכת סדר האלמנטים ברשימה.

הנה מתודות שאינן קימות ב-vector אך אינן יחודיות ל-list:

pop_front();

push_front();

הנה האופרטורים המשותפים -list ול-containers אחרים  כולל vector(לפי סדר אלפבתי):

assign();

back();

begin();

clear();

empty();

end();

erase();

front();

insert();

max_size();

operator =();

pop_back();

push_back();

rbegin();

rend();

resize();

size();

swap();

והאופרטורים:

 ==

!=

 <

>

 <=

 >=

כעת נדגים שימוש במתודות הנ"ל (יודגמו כאן אלה המודגשות בצהוב ברשימה למעלה). השימוש ביתר המתודות הודגם כבר בדיון על vector.
הדוגמות מוצגות בצורת פונקציות קטנות שמדגימות את המתודות של list. בסוף ההסבר הדבקתי שוב את כל פונקציות שהודגמו + main מוכנים להרצה.

Constructos


נציג בדוגמא את 6 צורות constructors הנתמכות עבור list.

1. void demonstrate_constructors(){
2. // Demonstrate 6 types of constructors:
3. list<int>list1;
4. list<int>list2(10);
5. list<int>list3(10,1);
6. list<int>list4(list3.begin(), list3.end());
7. list<int>list5(list4);
8. int array[] = {1,2,2,3,4,5,4,6,6};
9. list<int>list6(array, array + sizeof(array)/sizeof(int));
10. print_list(list1);
11. print_list(list2);
12. print_list(list3);
13. print_list(list4);
14. print_list(list5);
15. print_list(list6);
16. }

שורה 3: יוצר אובייקט ריק של list

שורה 4: יוצר אובייקט עם 10 אלמנטים מסוג int. הערך של האלמנטים מאופס.

שורה 5: יוצר אוביקט עם 10 אלמנטים מסוג int שערכם 1.

שורה 6: יוצר את list, שמקבל את ערכיה מתוך התחום שנקבע ע"י שני איטרטורים.

ה-prototype של הפונקציה: 

list(iterator first, iterator last);

בשורה 6 הiterators מצביעים על הההתחלה והסוף שך list3, כך שהתוצאה תהיה: list5 יהיה זהה ל-list3.

שורה 7: יוצר list שמעתיק את הערכים מ-list אחר. במקרה הנ"ל list4.

שורה 9: שימוש חוזר ב-prototype שהודגם בשורה 6. הכוונה כאן היתה להדגים שימוש ב-pointers שמצביעים על שני קצוות מערך. המתחם בין שתי הקצוות  מועתק ל-list.

הערה: זה תמיד מתחם כזה (], כלומר המצביע העליון מצביע למעשה על איבר אחד מעל התחום.

שורות 10 -15: מפעילות פונקציה שמדפיסה את גודל ה-list ואת האלמנטים שלו. (זו לא פונקציית ספריה - אני כתבתי אותה). נשתמש בפונקציה זו בכל הדוגמאות.

היא נראית כך:

שורה 2: הדפסת גודל ה-list/

שורה 4: הדפסת האלמנטחם ב-list.

1. void print_list(list<int>tlist){
2. cout << tlist.size() << endl;
3. for (list<int>::iterator iter = tlist.begin(); iter != tlist.end(); iter++)
4.     cout << *iter << " ";
5.  cout << endl;
6. }

הפלט של demonstrate_constructors:

0

10

0 0 0 0 0 0 0 0 0 0

10

1 1 1 1 1 1 1 1 1 1

10

1 1 1 1 1 1 1 1 1 1

10

1 1 1 1 1 1 1 1 1 1

9

1 2 2 3 4 5 4 6 6

עבור כל constructor מודפסות שתי שורות (ע"י  print_list): שורה 1: דוגל. שורה 2: האלמנטים של ה-list.

2 שורות הפלט הראשונות מתייחסות ל-constructor ללא הפרמטרים:

list<int>list1;

לכן מס האיברים שלו הוא 0, ושורה שמדפיסה אותם ריקה.

קל לעקוב אחר שאר שורות הפלט.

erase

הפונקציה הבאה מדגימה את המתודה erase. היא מופיעה פעמיים: שורה 7: מחיקת איבר בודד, שורה 9: למחיקת range - תחום של איברים.

הנה התוכנית:

1. void demonstrate_erase(){
2. list<int>list1(10,1);
3. list<int>::iterator iter = list1.begin();
4. iter++;
5. iter++;
6. print_list(list1);
7. list1.erase(iter);
8. print_list(list1);
9. list1.erase(list1.begin(), list1.end());
10. print_list(list1);
11. }

שורה 7: מוחקת איבר יחיד שמוצבע ע"י ה-iterator. ה-iterator מצביע על האיבר השלישי ברשימה. כמו שהוסבר כבר קודם, לא ניתן היה להשתמש ב-random access ולשים את ה-iterator ישירות על האיבר השלישי. במקום זה, ה-iterator הצביע על ראש ה-list ומשם התקדם שני צעדים (שורות 4 -5).

בדוגמא שלנו האיבר השלישי כמו כל האיברים עשרת איברי הרשימה הוא 1. אחרי המחיקה ישארו ברשימה רק 9 איברים.

שורה 9: מוחקת תחום של איברים, המוצבע ע"י שני iterators. אחזור שוב על העובדה שה-iteratorשמצביע על קצה התחום העליון, מצביע על "איבר אחד אחרי" כך שתחום המחיקה למעלה הוא כזה:

[iterator start, iterator end)

בדוגמא שלנו, מוחקים את כל התחום שבין begin ו-end כך שהרשימה תשאר ריקה.

הנה הפלט:

10

1 1 1 1 1 1 1 1 1 1 

9

1 1 1 1 1 1 1 1 1 

0

התיחסות לפלט הנ"ל: היו בפונקציה 3 פקודות הדפסה.

הראשונה - של הסדרה המקורית עם 10 האיברים.

השניה אחרי מחיקת האיבר השלישי - נשארו 9 אברים.

השלישי אחרי מחיקת כל האיברים.

insert


פעולת insert מכניסה אלמנטים חדשים תוך דחיפת האלמנטים הקיימים. קיימים 3  prototypes ל-insert, והם מודגמים בפונקציה כאן למטה. מתודות insert מודגשות בצהוב.

3 סוגי ה-prototype הם:
1. הכנסת איבר יחיד עם ערך מוגדר למקום אליו מצביע iterator:

list.insert(iterator position, value_type &const x);

ראה מימוש בשורה 7.

2. הכנסת n איברים עם ערך מוגדר למקום אליו מצביע ה-iterator:

list.insert(iterator position,  size_type n, value_type &const x);

ראה מימוש בשורה 10

3. הכנסת תחום של איברים, התחום ע"י שני iterators - בהתחלה ובסוף התחום, למקום אליו מצביע iterator.

list.insert(iterator position,  iterator first, iterator last);

ראה מימוש בשורה 22.

נתייחס לקוד שלמטה:

 שורה 7: הכנסת אלמנט שערכו 5 לתחילת הרשימה. הרשימה המקורית היתה באורך 5  (ראה שורה 3). אחרי שורה 7, האורך יהיה 6.
הרשימה תראה עכשיו כך:

5 1 1 1 1 1 

שורה 10: הכנסת 5 אלמנטים בהתחלת הרשימה.ערכם 23.
הרשימה תראה עכשיו כך:

23 23 23 23 23 5 1 1 1 1 1 

שורה 22: הכנסת list2 לתוך list1, החל מהמקום השלישי של list1.

list2 נראה כך:

10 10 10 10 10 10 10 

ו-list1 אחרי ההכנסה של list2 יראה כך:

23 23 10 10 10 10 10 23 23 23 5 1 1 1 1 1

1. void demonstrate_insert(){
2. 
   
3. list<int>list1(5,1);
4. list<int>::iterator iter = list1.begin();
5. print_list(list1);
6. // insert 5 elements at begin:
7. list1.insert(list1.begin(), 5);
8. print_list(list1);
9. // insert 5 elements at begin. val = 23:
10. list1.insert(list1.begin(), 5, 23);
11. print_list(list1);
12. // insert  to list1 from list 2[begin+2,list2[end])
13. list<int>list2(7,10);
14. iter = list1.begin();
15. iter++;
16. iter++;
17. list<int>::iterator iter_src_start = list2.begin();
18. list<int>::iterator iter_src_end;
19. 
    
20. iter_src_start++;
21. iter_src_start++;
22. list1.insert(iter, iter_src_start, list2.end());
23. print_list(list1);
24. }
25. 
    

והנה הפלט כולו:

5

1 1 1 1 1

6

5 1 1 1 1 1

11

23 23 23 23 23 5 1 1 1 1 1

16

23 23 10 10 10 10 10 23 23 23 5 1 1 1 1 1

assign

המתודה assign מכניסה לרשימה אלמנטים חדשים. שלא כמו insert, האלמנטים הישנים נמחקים.
קיימים שני prototypes של assign:
1. כמות האיברים וערכם נקבעים ע"י קבועים. הנה ב-prototype:

list.assign(size__type n, const value_type& x);

שימוש ב-prototype  מהסוג הראשון בשורה 5 למטה.

2. הערכים המוכנסים מוצבעים ע"י שני iterators.

הה-prototype נראה כך:

list.assign(iterator start, iterator end);

שימוש ב-prototype מהסוג השני - בשורה 9.

פרוט הדוגמא:

מראה שימוש בשני ה-prototypes של assign שפורטו לעי"ל.

שורה 5 מכניסה 7 איברים שערכם 123 ל-list1. עשרת האיברים שהיו ב-list1 לפני כן, נמחקו.

שורה 9 מכניסה 5 איברים מתוך array. כרגיל, המצביע העליון (array+5), מצביע על איבר מעבר לרשימה.

1. void demonstrate_assign(){
2. list<int>list1(10,1);
3. // assign with const value:
4. print_list(list1);
5. list1.assign(7, 123);
6. print_list(list1);
7. // Assign with iterators
8. int array[] = { 1,2,3,4,5,6,7,8};
9. list1.assign(array, array+5);
10. print_list(list1);
11. }

הנה הפלט:

10

1 1 1 1 1 1 1 1 1 1 

7

123 123 123 123 123 123 123 

5

1 2 3 4 5 

ניתוח הפלט:

בתוכנית 3 פקודות הדפסה, כל אחת מדפיסה 2 שורות: גודל, תוכן ה-list.

שורות 1-2: זה המצב לפני ה-assign. ה-list מכיל 10 איברים עם הערך 1.

שורות 3-4: ה-assign מחק את תוכן ה-list הקודם והחליפו ב- 7 אברים בערך 123.

שורות 5-6: הוכנסו 5 איברים מתוך המערך שבשורה 8 למעלה. שימו לב - כמו תמיד עם ה-iterators' הגבול העליון הוא פתוח. כלומר, פקודת ה-insert נראית כך:

list1.assign(array, array+5);

אבל הוכנסו 5 איברים ולא 6. הגבול העליון תמיד מצביע על כתובת אחת מעל.

splice

splice דומה במידה מסוימת ל-insert. הפעולה מכניסה לתוך ה-list, קבוצת אלמנטים רציפה תחומה ע"י    iterators או list אחר בשלמותו.
ההבדל העיקרי לעומת insert הוא, שהאלמנטים מועברים מהרשימה ממנה הובאו ונמחקים ממנה. זו פעולת move לעומת insert שם מתבצע copy/
הבדל נוסף, האלמנטים יכולים להגיע רק מ-list. לא מ-array וגם לא constants.
הנה 3 ה-prototypes:
1. העברת   list x  בשלמותו. האיברים מוכנסים לפני המקום המוצבע ע"י position. אחרי הפעולה list x ישאר ריק. הפונקציה מקבלת reference של list x כלומר x&.

list.splice(iterator position, list <T> &x)

פרוט פרמטרים:

position - מצביע על היעד. האיברים יוכנסו לפני המצביע.

x - הרשימה המועתקת.

2. העברת  אלמנט אחד מתוך list x. 

list.splice(iterator position, list <T> &x, iterator src);

פרוט הפרמטרים:

position - מצביע על היעד. האיברים יוכנסו לפני המצביע.

x - הרשימה ממנה ילקח האיבר להעתקה.

iterator src - מצביע על האיבר שיועבר.

3.  העברת רצף של איברים מ-list x.

list.splice(iterator position, iterator first, iterator last);

פרוט הפרמטרים:

position - מצביע על היעד. האיברים יוכנסו לפני המצביע.

 iterator first - מצביע על תחילת הרשימה שתועתק.

iterator last - מצביע על סוף הרשימה שתועתק. כרגיל - ההצבעה נעשית על הכתובת שאחרי סוף הרשימה.

הנה תוכנית המדגימה שימוש ב-3 ה-prototype הנ"ל. ראה הדגשה בצהוב. הפלט מודפס למטה. אגב, את ההגדרה של פונקצית ההדפסה - print_list, אפשר למצוא בהמשך.

1. void  demonstrate_splice(){
2. list<int>list1(10,1);
3. list<int>list2(10,2);
4. // splice 1: splice a list
5. list1.splice(list1.begin(), list2);
6. print_list(list1);
7. print_list(list2);
8. //  splice 2: splice a single element
9. list<int>::iterator iter_src  = list2.end();;
10. list<int>::iterator iter_dst = list1.begin();
11. list1.assign(10,1);
12. list2.assign(5,2);
13. iter_src--;
14. iter_src--; //points 2 places before end
15. iter_dst++; //points to 2nd place
16. list1.splice(iter_dst, list2, iter_src);
17. print_list(list1);
18. print_list(list2);
19. // splice 3:
20. int array2[] = {1,2,3,4,5,6,7,8};
21. list<int>::iterator iter_dst_start = list1.begin();
22. iter_dst_start++;
23. list1.assign(10, 111);
24. list2.assign(array2, array2+6);
25. list1.splice(iter_dst_start, list1, list2.begin(), list2.end());
26. print_list(list1);
27. print_list(list2);
28. }

והנה הפלט:

20

2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 

0

11

1 2 1 1 1 1 1 1 1 1 1 

4

2 2 2 2 

16

111 1 2 3 4 5 6 111 111 111 111 111 111 111 111 111 

0

השורה הרביעית והשורה האחרונה ריקות - כי נשארו 0 איברים ב-list2.

unique

unique תומכת בשני prototypes:

1. ללא פרמטרים.

list.unique();

המתודה משווה משווה בין כל שני איברים צמודים ברשימה, ומוחקת אחד במקרה שהם זהים.
דוגמא:
הרשימה 1,2,4,4,5,6 תהפוך ל-1,2,4,5,6.
2. עם פרמטר המצביע על פונקציית predicate.

list.unique(BinaryPredicate binari_pred);

פונקציה זו תופעל על כל שני איברים צמודים ברשימה. כלומר על האיבר ה-n וה-n-1, כאשר n=1 עד n=list.size()-1.
אם היא תחזיר true, האיבר ה-n ימחק.
בדוגמא למטה נדגים  predicate function.


דוגמא לשימוש בשני ה-prototypes של unique: (מופעי unique צבועים צהוב.)

2. void demonstrate_unique(){
3. // unique 1:
4. list<int>list1(10,1);
5. int array[] = { 3,1,5,6,7,4,3,8,4};
6. list1.assign(array, array+sizeof(array)/sizeof(int));
7. list1.sort();
8. list1.unique();
9. print_list(list1);
10. // unique 2:
11. list1.assign(array, array + sizeof(array)/sizeof(int));
12. list1.unique(predicate_func);
13. print_list(list1);
14. }

לגבי ה-prototype הראשון: בשורה 7, מופעל מיון על list1 לפני הפעלת unique. אחרת, unique לא היתה מבחינה באיברים זהים צמודים, ולפיכך לא היתה מבצעת כלום.
בהזדמנות זאת ערכנו הכרות עם sort. היא ממיינת את הרשימה.

לגבי ה-prototype השני: בשורה 12, predicate_func היא ה=predicate function.

אפשר לבחור כל פונקציה. הפונקציה מקבלת את האיברים n ו-n-1, ובמקרה שהתוצאה true, האיבר ה-n ימחק.
הנה predicate_func:

bool predicate_func (int par1, int par2){

return (par1 == 2 * par2);

}

predicate_func תגרום למחיקת האיבר ה-n, אם האיבר ה-n-1 גדול ממנו פי 2.
לדוגמא, הרשימה

 3,1,5,10,4,2,3,8,4

תהפוך ל:

 3 1 5 10 4 3 8.

 האיברים שנמחקו מסומנים בצהוב.

לפניכם הפלט:

7
1 2 3 4 5 8 10
7
3 1 5 10 4 3 8

merge

משלבת בין שתי רשימות, כאשר רשימה אחת מועברת לתוך השניה תוך כדי מיון. נפרט את שני סוגי ה-prototypes.
merge דומה ל-spline. ההבדל בינהן: spline מכניסה דוחפת את הרשימה האחת לשניה בלי לשנות את סדר האיברים.

prototype 1:

list.merge(list &x);

x משולבת לתוך list. היא מוחדרת לפי סדר החוקיות הבא:
1. הסדר של איברי x לא ישתנה, כך שהאיבר ה-n ימשיך להיות אחרי האיבר ה 1-n, אם כי לא בהכרח צמוד אליו.
2. איבר x ימוקם לפני איברי הlist המקורי הגדולים ממנו, בתנאי שתנאי 1 נשמר.

דוגמא:
הנה הרשימה אליה נכניס איברים. גודלה 6:

 -3,1,5,6,7,4,3,8,4

הנה הרשימה x. גודלה 9:

-10, 2,-11,15,-16,17,-14,13,18,14

נפעיל merge:

list.merge(x);

כעת list תהיה בגודל 15 ותראה כך:

-10 -3 1 2 -11 5 6 7 4 3 8 4 15 -16 17 

x עכשיו ריקה.

מה היה קורה אם היינו ממינים את שתי הרשימות מראש?

התשובה: תוצאת ה-merge היתה רשימה ממוינת. מיון מראש היא אכן פעולה הגיונית. בתוכנית שנציג מיד, נמיין את הסדרות לפני ה-merge.

prototype 2:

list.merge(list &x, StricktWeakOrdering comp);

פרוט:
פרמטר ראשון: הסדרה אותה נשלב בתוך list.
פרמטר שני: פונקציה שמגדירה את הסדר בה ישולבו איברי x.
נציג דוגמא לשימוש בשני ה-prototypes של merge:

1. void demonstrate_sort_and_merge(){
2. list<int>list1(10,1);
3. list<int>list2(10,1);
4. 
   
5. int array[] = { -3,1,5,6,7,4,3,8,4};
6. int array2[] = { -10, 2,-11,15,-16,17,-14,13,18,14};
7. 
   
8. // merge + sort
9. list1.assign(array, array+9);
10. list2.assign(array2, array2+6);
11. // list1.sort();
12. // list2.sort(compare_func);
13. print_list(list1);
14. print_list(list2);
15. list1.merge(list2);
16. print_list(list1);
17. print_list(list2);
18. 
    
19. //merge 2
20. list1.assign(array, array+5);
21. list2.assign(array2, array2+6);
22. list1.sort();
23. list2.sort();
24. list1.merge(list2, compare_func);
25. print_list(list1);
26. print_list(list2);
27. }

לגבי שורה 24: הנה compare_func:

bool compare_func (int par1, int par2){

    return(par1 > par2);

}

הסבר פעולת compare_func

list.merge(list &x, StricktWeakOrdering comp);

ה-compare function מקבלת שני איברים כל פעם: 

par1 - זהו איבר מהסדרה -x.

par2 - זהו איבר מהסדרה list.

הנה תאור האלגוריתם:

0. התהליך יבנה רשימה משולבת משתי הרשימות.

1. לוקחים איבר משתי הרשימות. נסמן אותם כ-xq ו-listq.

2. אם  תוצאת ה-compare היא true - מעבירים למקום הפנוי הבא ברשימה המשולבת את האיבר מx. ושולפים מ-x את האיבר הבא לתוך xq.

3. אם תוצאת ה-compare היא false - מעבירים למקום הפנוי הבא את האיבר מ-list, ושולפים מ-list את האיבר הבא לתוך listq.

4. משווים את xq ו-listq וחוזרים לשלב מס 1.

הפלט של הדוגמא הנ"ל:

9
-3 1 5 6 7 4 3 8 4
6
-10 2 -11 15 -16 17
15
-10 -3 1 2 -11 5 6 7 4 3 8 4 15 -16 17
0

11
-3 1 5 6 7 -16 -11 -10 2 15 17
0

reverse:

הופכת את סדר הרשימה.

הנה דוגמא:

void demonstrate_reverse(){
list<int>list1(10,1);
int array[] = { 3,-1,5,-6,7,4,3,8,4};
list1.assign(array, array+6);
print_list(list1);
list1.reverse();
print_list(list1);
}

הפלט כולל הדפסה של הרשימה לפני ואחרי ההיפוך. הנה הפלט:

6
3 -1 5 -6 7 4
6
4 7 -6 5 -1 3

ולסיום, הנה התוכנית הכוללת את כל הפונקציות שפורטו כאן למעלה + main שמפעילה אותן.

/*
 * stl_list.cpp
 *
 *  Created on: Mar 22, 2012
 *      Author: ronen halevy
 */



#include <iostream>
#include <list>
#include <iterator>
using namespace std;



bool compare_func (int par1, int par2){
    return(par1 ==  2* par2);
}

bool predicate_func (int par1, int par2){
return (par1 == 2 * par2);
}

void print_list(list<int>tlist){
cout << tlist.size() << endl;
for (list<int>::iterator iter = tlist.begin(); iter != tlist.end(); iter++)
    cout << *iter << " ";
 cout << endl;
}


void demonstrate_constructors(){

// Demonstrate 6 types of constructors:
list<int>list1;
list<int>list2(10);
list<int>list3(10,1);
list<int>list4(list3.begin(), list3.end());
list<int>list5(list4);
int array[] = {1,2,2,3,4,5,4,6,6};
list<int>list6(array, array + sizeof(array)/sizeof(int));
print_list(list1);
print_list(list2);
print_list(list3);
print_list(list4);
print_list(list5);
print_list(list6);

}



void demonstrate_erase(){
list<int>list1(10,1);
list<int>::iterator iter = list1.begin();
iter++;
iter++;
print_list(list1);
list1.erase(iter);
print_list(list1);
list1.erase(list1.begin(), list1.end());
print_list(list1);
}

void demonstrate_insert(){

list<int>list1(5,1);
list<int>::iterator iter = list1.begin();
print_list(list1);
// insert 5 elements at begin:
list1.insert(list1.begin(), 5);
print_list(list1);
// insert 5 elements at begin + 2. val = 23:
list1.insert(list1.begin(), 5, 23);
print_list(list1);
// insert  to list1 from list 2[begin+2,list2[end])
list<int>list2(7,10);
iter = list1.begin();
iter++;
iter++;
list<int>::iterator iter_src_start = list2.begin();
list<int>::iterator iter_src_end;

iter_src_start++;
iter_src_start++;
list1.insert(iter, iter_src_start, list2.end());
print_list(list1);
}
void demonstrate_assign(){
list<int>list1(10,1);
// assign with const value:
print_list(list1);
list1.assign(7, 123);
print_list(list1);
// Assign with iterators
int array[] = { 1,2,3,4,5,6,7,8};
list1.assign(array, array+5);
print_list(list1);
}
void  demonstrate_splice(){
list<int>list1(10,1);
list<int>list2(10,2);
// splice 1: splice a list
list1.splice(list1.begin(), list2);
print_list(list1);
print_list(list2);
//  splice 2: splice a single element
list<int>::iterator iter_src  = list2.end();;
list<int>::iterator iter_dst = list1.begin();
list1.assign(10,1);
list2.assign(5,2);
iter_src--;
iter_src--; //points 2 places before end
iter_dst++; //points to 2nd place
list1.splice(iter_dst, list2, iter_src);
print_list(list1);
print_list(list2);
// splice 3:
int array2[] = {1,2,3,4,5,6,7,8};
list<int>::iterator iter_dst_start = list1.begin();
iter_dst_start++;
list1.assign(10, 111);
list2.assign(array2, array2+6);
list1.splice(iter_dst_start, list1, list2.begin(), list2.end());
print_list(list1);
print_list(list2);
}
void demonstrate_unique(){
// unique 1:
list<int>list1(10,1);
int array[] = { 3,1,5,10,4,2,3,8,4};
list1.assign(array, array+sizeof(array)/sizeof(int));
list1.sort();
list1.unique();
print_list(list1);
// unique 2:
list1.assign(array, array + sizeof(array)/sizeof(int));
list1.unique(predicate_func);
print_list(list1);
}

void demonstrate_sort_and_merge(){
list<int>list1(10,1);
list<int>list2(10,1);

int array[] = { -3,1,5,6,7,4,3,8,4};
int array2[] = { -10, 2,-11,15,-16,17,-14,13,18,14};

// merge + sort
list1.assign(array, array+9);
list2.assign(array2, array2+6);
// list1.sort();
// list2.sort(compare_func);
print_list(list1);
print_list(list2);
list1.merge(list2);
print_list(list1);
print_list(list2);

//merge 2
list1.assign(array, array+5);
list2.assign(array2, array2+6);
list1.sort();
list2.sort();
list1.merge(list2, compare_func);
print_list(list1);
print_list(list2);
}
// reverse
void demonstrate_reverse(){
list<int>list1(10,1);
int array[] = { 3,-1,5,-6,7,4,3,8,4};
list1.assign(array, array+6);
print_list(list1);
list1.reverse();
print_list(list1);
}


int main(){
demonstrate_constructors();
demonstrate_erase();
demonstrate_insert();
demonstrate_assign();
demonstrate_splice();
demonstrate_unique();
demonstrate_sort_and_merge();
demonstrate_reverse();
return 0;
}