Iterators

[The Albatross]

Iterators

מה זה לעזאזל iterators? למה אני לא יכול לעשות פעולת מחיקה בvector ע"י int פשוט? ניסיתי לעשות משהו כזה:

vector<int> v; v.push_back(1); int i = 0; v.erase(i);​

אבל הקומפיילר מתריע לי על זה שאי אפשר לעשות המרה בין int לבין iterator. אני יכול לעשות אותו דבר בלי iterator? או שאני חייב להשתמש בזה? אם כן, איך אני ממיר מint לiterator?

 

[HaRmosh]

Iterator הוא מחלקה מקוננת של

כל container מ-STL, שתפקידה לתת גישה בטוחה לאיברי ה-container ואפשרות למעבר סדרתי עליהם, עם הסתרת המימוש של ה-container מהמשתמש. כדי למחוק את האיבר שמכיל את המספר i, תשתמש בפונקציית החיפוש של הווקטור, שמקבלת במקרה זה Int ומחזירה איטרטור למקום שבו מופיע ה-int הזה, ואת האיטרטור המוחזר תן לפונקציית המחיקה. משהו כזה (הסינטקס לא זכור לי כ"כ, אבל נסה משהו בסגנון):

v.erase(v.find(i));​

 

[The Albatross]

יש פונקציית חיפוש בוקטור?

למה זה לא נמצא פה?

 

[HaRmosh]

זה כן נמצא פה, רק

לא תחת וקטור - זו פונקציה כללית של STL, התבלבלתי קצת בקטע הזה.

 

[The Albatross]

אוקיי, תודה.

 

[frangelico]

איטרטור הוא מעין מצביע

לאובייקט מסויים במקרה הזה בווקטור, מספק גישה אליו ומעבר סדרתי על האיברים. לדוגמא שלך אפשר למחוק ללא גם יצירת איטרטור ולהדפיס את האיברים עם איטרטור:

// vector_erase.cpp #include <vector> #include <iostream> int main() { std::vector<int> v; std::vector<int>::iterator it; // fill with 3 values // v.push_back(1); v.push_back(2); v.push_back(3); // print vector elements before deleting // std::cout << "vector v before deleting second element: "; for ( it = v.begin( ) ; it != v.end( ) ; it++ ) std::cout << " " << *it; std::cout << std::endl; // delete the second value only // v.erase( v.begin( ) + 0, v.begin( ) + 2 ); // print vector elements before deleting // std::cout << "vector v after deleting second element:"; for ( it = v.begin( ) + 1; it != v.end( ) ; it++ ) // v.begin( ) + 1 = index of second element std::cout << " " << *it; // it - like pointer std::cout << std::endl; return 0; }​

 

[frangelico]

תיקון

המחיקה של האיבר השני

v.erase( v.begin( ) + 1, v.begin( ) + 2 );​

 

[The Albatross]

לא כ"כ הבנתי את הפונקציה erase

בפונקציה הזאת:

v.erase( v.begin( ) + 1, v.begin( ) + 2 );​

הוא לא ימחק גם את האיבר השלישי?

 

[DadleFish]

הסבר...

תחשוב על זה ככה:

for (int i = 1; i < 2; i++) ...​

זה הרי יטפל רק ב-i=1, כי ב-i=2 הוא כבר ייצא מהלולאה. אותו דבר בדוגמה שהוצגה. מעבר לכך, הדוגמה לא טובה, כי אפשר לעשות פשוט - (v.erase(v.begin()+1, ולא צריך את הפרמטר השני.

 

[DadleFish]

דוגמה קצת יותר מסודרת

#include <algorithm> #include <iostream> #include <vector> using namespace std; template <class T> void print(T data) { cout << data << " "; } int main() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); for_each(v.begin(), v.end(), print<int>); cout << endl; v.erase(v.begin()+1); for_each(v.begin(), v.end(), print<int>); cout << endl; return 0; }​

 

[The Albatross]

סליחה, המפקד, אבל מה זה for_each?

אף פעם לא נתקלתי בזה (אלא אם מחשיבים VB

)

 

[DNile]

חייל!

אין סליחה או תודה בצבא. אתה רוצה את תשומת הלב של המפקד, אתה תפנה אליו בהקשב. בכל אופן, for_each הוא כפי ששמו מרמז. עבור כל איבר בתוך קבוצה(כאשר הקבוצה נקבעת על ידי האיבר הראשון, והאיבר האחרון, וכמובן שהיא כוללת את כל האיברים באמצע). הפקודה for_each מריצה את הפונקציה שאתה מספק "עבור-כל" איבר בתחום שאתה מספק.

 

[The Albatross]

לפי מה מגדירים קבוצה?

 

[DNile]

בכל האוספים של STL

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

 

[The Albatross]

שתי שאלות:

1. אז גם מערך רגיל הוא קבוצה? 2. מה זה רשימה מקושרת?

 

[selalerer]

שתי תשובות:

1. באופן תיאורטי כו, באופן מעשי לא תוכל להשתמש בקוד שראית פה על מערך רגיל. הקוד הזה מותאם לcontainers של STL. 2. רשימה מקושרת זה בערך מערך מבולגן. מה זאת אומרת?! זאת אומרת שזה מערך שאינו מסודר בזיכרון באופן רציף. אז איך יודעים את הסדר של האיברים?! כל איבר ברשימה מלבד המידע הרגיל שמכיל איבר במערך מכיל גם מידע על מי אחריו, בצורה של מצביע אליו (כלומר הכתובת שבה יושב האיבר הבא ברשימה. תוספות קצת: יש מספר סוגים של רשימות מקושרות, חד כיוונית (שזה בעצם מה שתיארתי עכשיו) לכל איבר יש רק מצביע לאיבר אחריו אז אפשר לסרוק את הרשימה רק מההתחלה לסוף. דו כיוונית, לכל איבר יש מצביע לאיבר אחריו וגם לאיבר לפניו אז אפשר לסרוק את הרשימה לשני הכיוונים. רשימה מעגלית, האיבר האחרון מצביע לראשון, אפשר לסרוק אותה באופן אינסופי, כאשר מעגלית יכולה גם להיות חד כיוונית וגם דו כיוונית. הבנת?

 

[אופסשםמשתמש]

ממ למה משתמשים בזה ?

למה צריך רשימות מקושרות, אפשר לקבל דוגמא לאיפה זה חשוב ? מה אפשר לעשות עם שאי אפשר לעשות בלי ?

 

[Blade2]

להוסיף איברים ב O(1)

ברשימה אתה יכול להוסיף איברים לתחילת הרשימה בסיבוכיות זמן ריצה של O(1) , במערך עם גודל מוגדר אתה לא יכול לעשות את זה.

 

[DNile]

לא רק הוספה בתחילת הרשימה,

הוספה בכל מקום ברשימה - O(1) הסרה בכל מקום ברשימה - גם O(1) הSet back, הוא שכדי להגיע למיקום הN ברשימה, זה יהיה O(N), בניגוד לO(1) במערך.

 

[zagzagzag]

../images/Emo32.gifVector

איך מממשים מבנה נתונים כמו Vector (ב-Java או ב-++C, אני לא חושב שזה משנה) ? פעם קראתי שמבחינת הסטנדרט של ++C, המימוש יכול להיות גם כרשימה מקושרת, אבל זה נראה לי קצת בזבזני.