תפריט משתמש
קורס:"++C"
מתוך הספר: ++C - מדריך מקצועי  הארכיטקטורה של STLSTL (Standard Template Library) היא ספריית מיכלים, איטרטורים ואלגוריתמים תקנית בשפת C++. STL היא ספרייה המבוססת בעיקר על מנגנון ה- templates, ומכאן שמה. STL כוללת שלושה מרכיבים עיקריים: מיכלים - כגון: vector, list, set, map. אלגוריתמים - פעולות כגון: מיון, חיפוש, מיזוג, העתקה, החלפה, הזזה, השוואות, מציאת מינימום ומקסימום, פרמוטציות. איטרטורים - הפשטה של מצביעים לאיברים במיכלים.
הטבלה הבאה מראה את המיכלים העיקריים, האלגוריתמים השכיחים והאיטרטורים כמייצגים את סידרת האיברים של המיכל:
כפי שכבר צויין בסוף הפרק הקודם, בתכנון STL נבחרה הגישה בה מחלקות המיכל אינן יורשות מבסיס משותף, והאלגוריתמים מוגדרים כ- templates של פונקציות גלובליות. בכך התאפשרה הגדרה של מרבית הפונקציות ב- STL כ- inline, ולכן מושגת יעילות גבוהה מאוד הן בזמן והן במקום. כל מרכיבי STL מוגדרים תחת מרחב השם (namespace) std. כל שמות המרכיבים בספרייה נכתבים באותיות קטנות (ללא אות רישית גדולה). דוגמאות לשמות: std::vector, std::copy(), std::list<int>::iterator, וכו'. דוגמא: תכנית ליצירת אינדקס למסמךבסעיף זה נסקור את מרכיבי STL באמצעות תכניות דוגמא הבונות אינדקס (מפתח) למסמך נתון. הרעיון הוא לקרוא את המלים מהמסמך, לארגן אותם במבנה נתונים, לבצע עליהם פעולות שונות - כגון: הוצאת סימני פיסוק, מיון ועוד - ולבסוף להציגם. אנו נתחיל במימוש ע"י שימוש במערך הפשוט של C/C++ ונראה כיצד האלגוריתמים של הספרייה התקנית פועלות גם עליו כראוי. לאחר מכן נשפר את התכנית ע"י שימוש במיכלים של הספרייה התקנית. אינדקס 1: שימוש במערך פשוטכפי שראינו כבר בפרק 2, ניתן להפעיל את אלגוריתמי STL גם על המערכים הבסיסיים של השפה. אנו נשתמש בעובדה זו בכדי לשמור את המלים של המסמך במערך מחרוזות. האלגוריתם:
קוד התכנית מובא בעמ' 470-471. הפונקציה main() פותחת את קובץ הקלט לקריאה ומעבירה את עצם הקלט ל- make_index1() ליצירת האינדקס:
void main()
{
ifstream f1("file1.txt");
make_index1(f1);
};
הפונקציה make_index1() מגדירה מערך בעל גודל קבוע של מחרוזות שישמש לקליטת המלים:
// make_index1() - using an array of strings
void make_index1(istream &in)
{
enum { MAX_WORDS=1000};
string index[MAX_WORDS];
// read text from input stream string word; for(int wc=0; in >> word; wc++) index[wc]= word;
// sort sort(index, index+wc);
wc = unique(index, index+wc) - index;
{"bear", "cat", "cat", "dog", "dog", "dog", "horse", "mouse"}
{"bear", "cat", "dog", "horse", "mouse", "cat", "dog", "dog"}
// print the index for(int i=0; i != wc; ++i) cout << index[i] << endl; } תרגולקרא/י סעיף זה בספר ובצע/י את תר' 14-1, 14-2. אינדקס 2: שימוש במיכל vectorבתכנית האינדקס בגירסה הקודמת קיימת מגבלה על מספר המלים שבמסמך (1000 מלים). זוהי מגבלה קשה מצד אחד (ייתכנו מסמכים בעלי מספר מלים רב בהרבה), ובזבזנית מצד שני (מסמכים קטנים כוללים פחות מלים). בנוסף היינו רוצים לשפר מספר נקודות נוספות בתכנית:
בגירסה השנייה של תכנית האינדקס נעשה שימוש במיכל vector<T> של STL להגדרת וקטור מילות האינדקס, וקטור שורות הטקסט המקורי ווקטור מילות היחס : vector<string> index; // index words vector vector<string> text; // source text: vector of lines vector<string> ignored; // ignored words vector
בשלב הראשון נטען את וקטור מילות היחס מקובץ נתון, ignored.txt: a am and are as do else for had have has he her his i if in into is it like no not of off out she than that the their they them then this to us we what where when which while who why yes yet
איתחול זרם קלט מהקובץ :
ifstream ig_file("ignored.txt");
ניתן לבצע את הקריאה ע"י לולאה כך: string word; while(ig_file >> word) ignored.push_back(word); בשלב הבא נבצע את לולאת הטעינה מהקלט:
while(getline(in, line))
{
text.push_back(line); // save text line
replace_if(line.begin(), line.end(), ispunct, ' ');
istringstream is1(line); while(is1 >> word) // read words from line index.push_back(word); } לאחר סיום הלולאה נמיין את וקטור האינדקס כמו קודם: sort(index.begin(), index.end()); הפעם לא מדובר במערך בעל גודל קבוע, לכן לא מעבירים כתובות אלא איטרטורים לתחילת הוקטור ולסופו:
בשלב הבא מסירים מילים כפולות ע"י האלגוריתם unique: index.erase( unique(index.begin(), index.end()), index.end());
שוב, גם כאן אנו מעבירים איטרטורים לתחילת הסדרה ולסופה לאלגוריתם unique, וזה מעביר מחרוזות כפולות לסוף, ומחזיר מצביע לסוף הסדרה. לדוגמא, הפעלת unique על הסדרה
{"bear", "cat", "cat", "dog", "dog", "dog", "horse", "mouse"}
תהפוך אותה ל
{"bear", "cat", "dog", "horse", "mouse", "cat", "dog", "dog"}
והאיטרטור המוחזר מ- unique מצביע על תחילת תת-הסדרה של האיברים המשוכפלים, כלומר על ה- "cat" המודגש. לכן, אנו מסירים את האיברים המודגשים ע"י הפונקציה erase() של הוקטור:
בשלב הבא אנו מסירים מלים המופיעות בוקטור מילות היחס, ignored, ע"י האלגוריתם set_difference(), המבצע פעולת החסרה בין שתי סדרות. ראשית נגדיר וקטור מחרוזות זמני שיכיל את תוצאת החיסור: vector<string> temp; וכעת נפעיל את set_difference() לביצוע ההחסרה <temp> = <index> - <ignored> הקריאה מתבצעת כך: set_difference(index.begin(), index.end(), // first sequence ignored.begin(), ignored.end(), // second sequence back_inserter(temp)); // result sequence set_difference() עוברת על שתי סדרות ממויינות, ומכניסה לתוך סידרת התוצאה איברים מהסדרה הראשונה שאינם מופיעים בסדרה השנייה. סידרת התוצאה מצויינת ע"י איטרטור הכנסה אחורי (back_inserter) למיכל temp. לאחר קריאה זו, ניתן להציב את התוצאה לוקטור index: index = temp; שאלה: מדוע השתמשנו באיטרטור הכנסה back_inserter על סידרת התוצאה ולא באיטרטור הרגיל לסוף המיכל, end()? תשובה: לו השתמשנו באיטרטור end(), set_difference(index.begin(), index.end(), // first sequence ignored.begin(), ignored.end(), // second sequence temp.end()); // result sequence
היתה סכנה ממשית לגלישת זיכרון: הסיבה היא שהאיטרטור end() אינו מכניס איבר חדש למיכל, אלא מניח קיומו של מקום מתאים במיכל. באופן דומה, קיים איטרטור הכנסה לתחילת הסדרה המתקבל ע"י front_inserter, וכן איטרטור הכנסה לפני מיקום מסוים במיכל, inserter.
בשלב הבא אנו מדפיסים את שורות הטקסט המקוריות, יחד עם מספר השורה: for(int i=0; i<text.size(); i++) cout << i+1 << ":" << text[i] << endl; ולבסוף מודפס וקטור האינדקס: for(i=0; i!=index.size(); ++i) cout << index[i] << endl; התכנית בכללותה מובאת בעמ' 477-479. התעלמות מהבדלי אותיות רגילות ורישיות (case ignore)כפי שניתן לראות בפלט, התכנית אינה מסירה את מילת היחס "They" מכיוון שהיא שונה באות הרישית ממילת היחס "they". באופן דומה, הפעלת התכנית על קובץ הקלט this is line 1 this is Line 2 This is line 3
מפיקה את הפלט: 1:this is line 1 2:this is Line 2 3:This is line 3 1 2 3 Line This line
לפתרון הבעיה, ניתן להשתמש באחת משתי הגישות:
template<class RandIter> void sort(RandIter first, RandIter last);
template<class RandIter, class Pred> void sort(RandIter first, RandIter last, Pred pr);
bool less_no_case(const string& s1, const string& s2)
{
return stricmp(s1.c_str(), s2.c_str())<0;
}
sort(index.begin(), index.end(), less_no_case);
bool equal_no_case(const string& s1, const string& s2)
{
return stricmp(s1.c_str(), s2.c_str())==0;
}
unique(index.begin(), index.end(), equal_no_case);
template<class InIt, class Fun>
Fun for_each(InIt first, InIt last, Fun f)
{
for( ; first!=last; first++)
f(*first);
return f;
}
void lower(char &c) { c=tolower(c); }
for_each(word.begin(), word.end(), lower); // make word lowercase
עצמי פונקציותבפתרונות שראינו בסעיפים הקודמים קיימת בעיית יעילות חמורה. למשל, בדוגמא האחרונה שראינו הפונקציה lower() תיקרא עבור כל אחד מתווי המחרוזת:
void lower(char &c) { c=tolower(c); }
for_each(word.begin(), word.end(), lower); // make word lowercase
אם המחרוזת באורך 200 תווים, הפונקציה תיקרא 200 פעם!! נסיון לפתור את הבעיה ע"י הגדרת הפונקציה כ- inline ייכשל מכיוון שכאשר מצביע לפונקציה מועבר כפרמטר לפונקציה אחרת, לא ניתן לממשה כ- inline, מכיוון שכתובת הפונקציה תהיה ידועה רק בזמן ריצה ולא בזמן הידור. הפתרון: שימוש בעצמי פונקציות (Function Objects). במקום להגדיר פונקציה, נגדיר מחלקה הכוללת פונקצית inline:
struct Lower {
void operator()(char &c) { c=tolower(c); }
};
הסבר: המחלקה כוללת פונקצית אופרטור "( )" כ- inline, המקבלת כפרמטר תו והופכת אותו ל- lowercase. המיוחד באופרטור זה הוא שניתן להגדיר עצם מהמחלקה כך, Lower low; ולקרוא לפונקציה שהוגדרה במחלקה באופן אנונימי: char c = 'A'; low(c); // make c = 'a' כלומר, אנו משתמשים בעצם המחלקה כאילו היה פונקציה! תכונה זו של עצמי פונקציות מאפשרת לנו להעבירם כפרמטרים לפונקציות המצפות בפועל לקבל מצביעים לפונקציות. לדוגמא, ניתן להעביר עצם מהמחלקה לאלגוריתם for_each() הנ"ל: Lower low; for_each(word.begin(), word.end(), low); או, באופן מקוצר יותר, ניתן להעביר עצם זמני המיוצר בקריאה לפונקציה: for_each(word.begin(), word.end(), Lower()); אם נסתכל שוב על מימוש for_each() בספרייה התקנית,
template<class InIt, class Fun>
Fun for_each(InIt first, InIt last, Fun f)
{
for( ; first!=last; first++)
f(*first);
return f;
}
נבין מדוע הפרמטר f מטיפוס Fun יכול להיות גם עצם פונקציה: הקריאה f(*first); תפעיל את פונקציה האופרטור " ( )" שבמחלקה Lower, והתו יהפוך לכן ל- lowercase. כאשר מועבר עצם פונקציה כפרמטר לפונקציה אחרת, ניתן לממש פונקצית אופרטור "( )" כ- inline, ובכך להפוך את הקריאה ליעילה יותר.
באופן דומה, ניתן לכתוב עצם פונקציה יעיל כתחליף לפונקצית ההשוואה less_no_case():
struct Less_no_case {
bool operator()(const string& s1, const string& s2)
{ return stricmp(s1.c_str(), s2.c_str())<0; }
};
תרגולקרא/י סעיף זה בספר ובצע/י את תר' 14-3 עד 14-6. אינדקס 3: שימוש במיכל mapתכנית אינדקס אמיתית כוללת לא רק את המילים שהופיעו במסמך, אלא גם את מיקומן במסמך, כלומר, מספר עמוד או מספר שורה. לכן, אנו מעוניינים להוסיף למלים את מספרי השורות במסמך בהן הן הופיעו. הדרך הפשוטה ביותר לבצע זאת היא ע"י שימוש במיכל map<Key, Val>: זהו מיכל המחזיק סדרת איברים עפ"י מפתחות מתאימים. לדוגמא, ניתן להגדיר את index כמיכל הממפה מחרוזות למספרי שורה: map<string, int> index; המפתחות במיכל יהיו מילות האינדקס, והערכים הם מספרי השורה בהן הופיעו לראשונה במסמך. תכונה חשובה במיכל map היא שהאיברים שבו ממויינים עפ"י מפתחותיהם, באופן תמידי. כלומר, אין צורך למיין את ה- map בשום שלב. כעת, בכל קריאה של מילה, word, בשורה מספר ln, ניתן להכניסה למיכל ע"י index.insert(pair<string,int>(word,ln)); הסבר: המיכל map<string,int> מכיל למעשה סידרת איברים מטיפוס pair<string, int>, הממויינים לפי המפתח (הראשון מבין הצמד שב- pair). בצורה נוחה יותר, ניתן לעשות שימוש באופרטור [ ] להכנסת צמד חדש: index[word] = ln; בשימוש באופרטור [ ], אם המילה לא קיימת היא תוכנס למיכל, יחד עם הערך שלה - ln - מספר השורה. אחרת, ערך האיבר (מספר השורה) יעודכן כ- ln. משום כך, יש לבדוק שהמילה לא קיימת במיכל לפני ההוראה הנ"ל: if(index.find(word)==index.end()) index[word] = ln; בכדי להדפיס את הטבלה, נבצע מעבר על הסדרה באמצעות איטרטור: for(map<string, int>::iterator it = index.begin(); it!=index.end(); ++it) cout << it->first << ":" << it->second << endl; הסבר: טיפוס האיטרטור הוא map<string,int>::iterator, ובתחילת הלולאה הוא מאותחל לתחילת הסדרה: map<string, int>::iterator it = index.begin() תנאי הלולאה הוא הגעה לסוף הסדרה it!=index.end() וקידום האיטרטור מבוצע ע"י ++it. בגוף הלולאה אנו מדפיסים את שני האיברים שבצמד, pair<string, int> ע"י: cout << it->first << ":" << it->second << endl; first הוא שם המפתח שבצמד, ו- second הוא שם הערך. הפעלת האופרטור it-> מחזירה איבר pair<string,int>, וממנו שולפים ומדפיסים את שני המרכיבים. שמירת מערך של מספרי שורהאנו מעוניינים בתכנית יצירת האינדקס לשמור לא רק את השורה הראשונה בה הופיעה המילה, אלא את כל מספרי השורה בהן היא הופיעה. לכן, נשתמש שוב במיכל map כאשר פרמטר הערך (הפרמטר השני ב- pair) הוא וקטור שלמים: map<string, vector<int> > index; לשם נוחות, ניתן להגדיר טיפוס ע"י typedef כך: typedef map<string, vector<int> > Index;
וכעת להשתמש בטיפוס Index להגדרת המיכל Index index;
בקריאת מילה מהקלט, נכניס את מספר השורה לוקטור המתאים: while(is1 >> word) index[word].push_back(ln); כאן יש לשים לב שאם המילה לא קיימת, היא תוכנס, ביחד עם מספר השורה. אחרת, מספר השורה החדש יוכנס לוקטור מספרי השורה של המילה. למעשה, ניתן לייעל את סינון מילות היחס כבר בשלב הכנסתן למיכל: נבדוק ע"י האלגוריתם find() אם הן אינן מופיעות בוקטור ignored לפני הכנסתן if(find(ignored.begin(), ignored.end(), word) == ignored.end()) index[word].push_back(ln);
find() מחזירה איטרטור לסוף הסדרה אם האיבר לא נמצא בה. קוד הקריאה מהקלט כולו נראה כך:
// read text from input stream
for(int ln=1; getline(in, line); ln++)
{
text.push_back(line);
replace_if(line.begin(), line.end(), ispunct, ' ');
istringstream is1(line);
while(is1 >> word)
{
// make word lowercase
for_each(word.begin(), word.end(), Lower());
// if word not in ignored vector insert into index
if(find(ignored.begin(), ignored.end(), word) == ignored.end())
index[word].push_back(ln);
}
}
וההדפסה תבוצע באופן הבא:
for(Index::iterator it = index.begin(); it!=index.end(); ++it)
{
cout << it->first << ":" ;
for(int i=0; i<it->second.size(); i++)
cout << it->second[i] << ' ';
cout << endl;
}
כפי שניתן לראות, לאחר הדפסת המילה, מבוצעת לולאה על וקטור מספרי השורה והדפסתם.
התוכנית המלאה מובאת בעמ' 485. תרגולקרא/י סעיף זה בספר ובצע/י את תר' 14-7. מיכלים (Containers)מיכלים (Containers) הם מחלקות המכילות סדרה של איברים בעלי טיפוס כללי. המימוש המדויק של כל מיכל לא מוגדר - השפה מגדירה רק את הפעולות שכל מיכל מממש וכן את הסיבוכיות שלהן. תרשים המיכל:
במיכל שבציור 4 איברים, begin() היא פונקציה של המיכל המחזירה איטרטור לעצם הראשון, ו- end() מחזירה איטרטור לאיבר אחד-אחרי-האחרון. המבנה הפנימי של המיכל יכול להיות מערך, רשימה, עץ, טבלה וכו'. המיכלים העיקריים נחלקים לשלוש קטגוריות עיקריות - סדרתיים, ממויינים ומשניים. הטבלה בעמ' 490 כוללת את פירוט המיכלים עפ"י קטגוריות, ובאיזה קובץ ספרייה הם מוכרזים. הטבלה שבעמוד 491 מפרטת את פונקציות השירות של המיכלים עפ"י קטגוריות. הטבלה שבעמוד 493 מציגה את הזמינות והסיבוכיות של שירותים שכיחים על מיכלים.
מיכלים סדרתייםהמיכלים הסדרתיים העיקריים בספרייה הם שלושה:
שלושת המיכלים הסדרתיים האחרים מוגדרים באמצעות המיכלים העיקריים:
vectorvector הוא מיכל המאפשר גישה אקראית ישירה לאיברים באמצעות האופרטור [ ] בדומה למערך הבסיסי. איברים מוספים ומוצאים בסופו ביעילות - סיבוכיות O(1). ניתן להכניס ולהוציא איברים גם במיקום כלשהו אחר - אולם זוהי פעולה יקרה - סיבוכיות O(n), כאשר n מספר האיברים בוקטור. המימוש המדוייק של המיכל vector אינו מוגדר בתקן השפה, אולם לרוב הוא ייראה בערך כך:
הסבר: vector<T> מכיל מצביע למימוש האמיתי של וקטור, כאשר זה למעשה מייוצג כסדרה של איברים בזיכרון. בדוגמא זו קיימים בוקטור 4 איברים, וישנם עוד שלושה מקומות נוספים להכנסה עתידית של איברים (reserve). שיטה זו מייעלת את מנגנון הקצאת איברים חדשים. קוד המיכל vector מובא בעמ' 494. listlist הוא מיכל המאפשר הכנסה והוצאה יעילים במיקום כלשהו בסיבוכיות O(1). כמו לגבי שאר המיכלים, גם מימושו המדוייק של list אינו מוגדר בספרייה, אלא רק סיבוכיויות הפעולות עליו. בשונה מהוקטור, list אינו מספק גישה אקראית לאיבר. לרוב list ימומש ע"י רשימה מקושרת דו כוונית של צמתים (nodes) המצביעים לאיברים עצמם:
עקב המבנה הלא רצוף בזיכרון של list, חלק מהפעולות שבדרך כלל ממומשות ע"י אלגוריתמים מסופקים במיכל list עצמו. קוד המיכל list מובא בעמ' 498. dequeהמיכל deque הוא מיכל המייצג תור דו-כווני להכנסה והוצאה של איברים מתחילתו ומסופו בסיבוכיות O(1), וכן לגישה אקראית ישירה לאיברים בסיבוכיות O(1):
deque דומה מאוד הן מבחינת מימושו והן מבחינת השירותים שלו למיכל vector למעט הבדל אחד: הוא מאפשר הכנסה והוצאה גם מתחילתו - ע"י השירותים push_front(), pop_front() - בסיבוכיות O(1). stack, queue ו- priority_queueשלושת המיכלים stack, queue ו- priority_queue מוגדרים ע"י המיכלים העיקריים שבספרייה, ולמעשה, תפקידם הוא לספק ממשקים מסוימים למשתמש, לא פונקציונליות שונה. משום כך נהוג גם לכנות אותם כמתאמים. כל אחד מהמיכלים המתאמים מוגדר באמצעות מיכל עיקרי אותו הוא מקבל כפרמטר template, והוא משתמש בו לביצוע פעולות המיכל השונות. כל המיכלים המתאמים אינם כוללים מנגנון איטרציה: הסיבה נעוצה בממשק עצמו שהם באים לספק - הכנסת איברים ושליפתם בסדר מסוים.
קוד המיכל stack מובא בעמ' 502.
תרגולקרא/י סעיף זה בספר ובצע/י את תר' 14-8. מיכלים משנייםקיימים 4 מיכלים משניים ב- C++:
int arr[10]; double arr[200]; X arr[4];
typedef basic_string<char> string;
#include <bitset> using namespace std; #include <bitset> using namespace std; bitset<10> b1; cout << b1 << endl; 0000000000 b1 = 0x12; cout << b1 << endl; 0000010010 cout << (b1>>2) << endl; 0000000100 cout << ~b1 << endl; 1111101101
bitset<20> b2("100101001");
cout << b2 << endl;
00000000000100101001 קוד template המחלקה bitset מובא בעמ' 509. מיכלים ממוייניםקיימים 4 מיכלים אסוציאטיביים ממויינים :
mapmap הוא מיכל של זוגות מפתח-ערך, כאשר המפתחות הם יחידים. זוג מוגדר ע"י המחלקה pair<key,value>. כמו שאר מיכלי STL, מימושו המדוייק של map אינו מוגדר בספרייה, אולם לרוב הוא ימומש ע"י מבנה עץ מאוזן בערך כך:
קוד המיכל map מובא בעמ' 511. multimapאם נרצה לאפשר שמות לא יחידים (non unique) בתוכנת הדואר, נעשה שימוש ב- multimap: זהו מיכל המוגדר בדומה ל- map, אך הוא יכול להכיל מפתחות זהים מרובים. ל- multimap לא מוגדר האופרטור [] לכן הכנסת האיברים מבוצעת ע"י insert(), שמקבלת כפרמטר pair<key,value>. ניתן ליצור pair במפורש ולהכניסו אח"כ ל- multimap,
multimap<string, string> mailbox;
pair<string,string> m2("Sara", "sara@mh2000.co.il");
mailbox.insert(m2);
או לייצר אותו ישירות בהכנסה:
mailbox.insert(pair<string,string>("Sara","sara@hotmail.com"));
תוצאת חיפוש ב- multimap יכולה לכלול יותר מצמד אחד, לכן משתמשים בפונקציה lower_bound(), upper_bound() לקבלת איטרטורים המציינים תחילת וסיום טווח האיברים שנמצאו. setהמיכל set דומה ל- map בכך שהוא מכיל סדרת איברים ממויינת, אולם set פשוט יותר: הוא מכיל את המפתחות בלבד, כלומר, האיברים ממויינים עפ"י יחס ההשוואה:
קוד המיכל set מובא בעמ' 516. multisetmultiset הוא מיכל דומה ל- set היכול להכיל איברים זהים. תרגולקרא/י סעיף זה בספר ובצע/י את תר' 14-9. איטרטוריםאיטרטורים הם מנגנון גישה לאיברים שבמיכלים. איטרטור הוא הפשטה של מצביע לאיברי מערך: זוהי מחלקה המספקת גישה לאלמנטים שבמיכלים ללא תלות בטיפוסי האיברים שלהם. משום כך, האיטרטורים הם למעשה החוליה המקשרת שבין המיכלים לבין האלגוריתמים:
האופרטורים ++ ו- * מוגדרים על האיטרטור באופן שניתן להתייחס אליו בדומה למצביע לאיברים במערך. קיימות מספר קטגוריות של איטרטורים עפ"י יכולותיהם: איטרטור המאפשר קריאה/כתיבה (ע"י האופרטור *), איטרטור המאפשר התקדמות (++), איטרטור דו כווני (- -) ואיטרטור בעל יכולת תנועה אקראית (+, -). קיימים איטרטורים המוגדרים כמחלקות מקוננות בתוך המיכלים, ואיטרטורים גלובליים. פונקציות שונות של המיכלים מחזירות איטרטורים מקוננים לתחילתם (begin()), לסופם (end), לאיבר שאחרי איבר שנמחק (erase()) ועוד. קטגוריות איטרטוריםהאיטרטורים נחלקים למספר קטגוריות, עפ"י סוגי הפעולות שניתן לבצע עליהם ועל האיברים המוצבעים על ידם:
כפי שניתן לראות, יכולות האיטרטורים הן עפ"י סדר הופעתם בטבלה. ברשימה הבאה נתייחס לאיטרטור בשם it ולמשתנה בשם x מהטיפוס המוצבע ע"י האיטרטור. הפעולות הבאות נגישות על it עפ"י הקטגוריה שלו:
*it = x; // output iterator x = *it; // input iterator
*it = x; it++; x = *it++; ++it;
*it++ = x; x = *it++; *it-- = x; x = *it--;
*it++ = x; x = *it++; *it-- = x; x = *it--; it = it + 5; it -= 3; *(it + 4) = x;
הטבלה שבעמ' 522 מסכמת את מכלול הפעולות הנגישות לכל קטגוריית איטרטור, תוך ציון הקיצורים לכל קטגוריה.
בכדי להבין את משמעות הקטגוריות השונות, נחזור ונתבונן באלגוריתמים שפגשנו עד כה. האלגוריתם find() למשל מוכרז כך: template<class InIter, class T> InIter find(InIter first, InIter last, const T& val);
משמעות ההכרזה היא שהאלגוריתם מצפה לקבל איטרטור מהקטגוריה הנמוכה ביותר - איטרטור קלט - ולכן כל איטרטור (מלבד פלט) יתאים באלגוריתם זה. לעומת זאת, האלגוריתם swap_ranges() מוגדר כך: template<class FwdIter1, class FwdIter2> FwdIter2 swap_ranges(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2); אלגוריתם זה מחליף בין איברי שתי הסדרות [first1..last1), [firs2..):
משום כך, על שני האיטרטורים להיות לפחות מסוג קדמי. שאלה: איזו קטגורית איטרטור מתאימה לאלגוריתם palindrome() שמתרגיל 14-2 עפ"י האילוצים שבו:
template <class Iter>
bool palindrome(Iter p1, Iter p2)
{
for(--p2 ;p1 < p2; ++p1, --p2)
if(*p1 != *p2)
return false;
return true;
}
תשובה: האיטרטורים p1,p2 מקודמים ומחוסרים בכל פעם ב- 1 בהתאמה. לכן נדרש כאן לפחות איטרטור דו כווני (BiIter). אולם פעולת ההשוואה p1 < p2 דורשת איטרטור אקראי (RandIt). לכן, כותרת הפונקציה תיכתב באופן מתועד מלא כך: template <class RandIter> bool palindrome(RandIter p1, RandIter p2); ולכן גם, ניתן להפעילה רק על מיכלים המחזירים איטרטורים אקראיים:
int arr1[] = {1, 2, 3, 2, 1};
vector<int> v1(arr1, arr1+5);
assert(palindrome(v1.begin(), v1.end()));
deque<int> d1;
copy(v1.begin(), v1.end(), back_inserter(d1));
assert(palindrome(d1.begin(), d1.end()));
list<int> l1(arr1, arr1+5);
assert(palindrome(l1.begin(), l1.end())); // error!
שגיאת ההידור המתקבלת בשורה האחרונה נובעת מכך שהאיטרטור של list הוא מסוג דו-כווני, ולכן אינו מתאים לאילוצי האלגוריתם. איטרטורים מקוננים במיכליםמחלקות המיכל מגדירות 4 מחלקות איטרטור מקוננות:
קטגורית כל אחד מהאיטרטורים היא עפ"י המיכל לו הוא משתייך (ראה/י טבלה לעיל). פונקציות שונות של המיכלים מחזירות איטרטורים אלו. לדוגמא, הפונקציה begin() של המיכלים מחזירה iterator:
string arr1[5] = { "tee", "coffee", "wine", "coke", "water"};
vector<string> v1(arr1, arr1+5);
vector<string>::iterator it = v1.begin();
כאן האיטרטור it הוא מסוג אקראי (מדוע?) והוא נע קדימה בביצוע ++:
while (it!=v1.end()) {
cout << *it << ", ";
++it;
}
ויודפס tee, coffee, wine, coke, water,
לעומת זאת, סיור על הרשימה הבאה
string arr2[6] = { "cat", "dog", "horse", "bear", "mouse", "fox"};
list<string> l1(arr2, arr2+6);
באמצעות reverse_iterator,
list<string>::reverse_iterator rit = l1.rbegin();
while (rit!=l1.rend()) {
cout << *rit << ", ";
++rit;
}
ידפיס fox, mouse, bear, horse, dog, cat,
איטרטורי const מתקבלים ע"י ורסיית ה- const של פונקציות המיכל השונות: begin(), end(), rbegin(), rend(). פונקציות אלו מופעלות על מיכלים שהוגדרו כ- const. לדוגמא, במיכל vector מוגדרות ורסיות האיטרטורים ופונקציות השליפה שלהם כך:
template<class T, class A = allocator<T> >
class vector {
public:
class iterator ... { ... };
class const_iterator ... { ... };
class reverse_iterator ... { ... };
class const_reverse_iterator ... { ... };
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
...
};
באופן דומה קיימות הגדרות אלו בשאר המיכלים. לדוגמא, בפונקציה הבאה קיימת שגיאת הידור:
void f(const vector<string> &v)
{
for(vector<string>::iterator it = v.begin(); it!=v.end(); ++it)
cout << *it << endl;
}
מהי השגיאה? הפונקציה begin() המופעלת על הוקטור שהתקבל כפרמטר const בפונקציה היא מורסיה const, ולכן היא מחזירה const_iterator. משום כך, ההוראה vector<string>::iterator it = v.begin(); אינה חוקית. על מנת לתקן את השגיאה נכתוב:
void f(const vector<string> &v)
{
for(vector<string>::const_iterator it = v.begin(); it!=v.end(); ++it)
cout << *it << endl;
}
הטבלה שבעמ' 525 מראה את ארבע מחלקות האיטרטור המקוננות במיכלים.
איטרטורים גלובלייםקיימים מספר איטרטורים גלובליים למטרות שונות. הטבלה שבעמ' 525 כוללת איטרטורים אלו. האיטרטורים הגלובליים יורשים ממחלקת בסיס משותפת, iterator, המספקת מספר הגדרות טיפוסים משותפות - ללא פונקציונליות. איטרטורי הכנסהאיטרטורי הכנסה משמשים להוספת איברים למיכלים בתחילתם, בסופם או במיקום אחר כלשהו. בכדי להבין את תפקידם, נתבונן בבעיה שבקוד הבא: נתון מערך ממשיים מטיפוס double,
double arr1[4] = {34.22, 5.9, 12, 0.1234};
וכן נתון וקטור ממשיים מטיפוס double, שהוכנסו לו שני איברים, vector<double> v1; v1.push_back(1.11); v1.push_back(2.22); כעת אנו מעוניינים להעתיק את סידרת האיברים מהמערך לסופו של הוקטור ע"י האלגוריתם copy(): copy(arr1, arr1+4, v1.end()); // runtime error!! הבעיה נובעת מכך שהאיטרטור המוחזר ע"י v1.end() אינו איטרטור מסוג הכנסה: הוא אינו מקצה מקומות חדשים בוקטור, אלא מניח שקיים כבר מקום פנוי להכנסה. הפתרון: שימוש באיטרטור back_inserter - מסוג פלט - להכנסה לסופו של מיכל. לדוגמא, ניתן להעתיק איברי מערך לאברי רשימה באופן הבא: copy(arr1, arr1+4, back_inserter(v1));
באופן דומה, front_inserter מאפשר הכנסה בתחילת המיכל. איטרטורי קלט/פלטostream_iterator הוא איטרטור מסוג פלט המאפשר שליחת איברים מתחום מסוים של מיכל לפלט. לדוגמא, שימוש באלגוריתם copy ביחד עם איטרטור זה מאפשר להדפיס איברי רשימה של מחרוזות לפלט התקני:
string sarr[6] = { "cat", "dog", "horse", "bear", "mouse", "fox"};
list<string> l3(sarr, sarr+6);
copy( l3.begin(), l3.end(), ostream_iterator<string>(cout,","));
יודפס cat,dog,horse,bear,mouse,fox,
איברי הרשימה נשלחים לאובייקט הפלט cout ע"י שימוש באיטרטור הפלט, כאשר הם מופרדים ע"י המחרוזת ",". ה- constructor של ostream_iterator מקבל כפרמטר את עצם הפלט ואת המחרוזת המפרידה. במקביל, קיים גם istream_iterator מסוג קלט המאפשר לקרוא מתוך זרם הקלט. לדוגמא, בכדי לאתחל תור מחרוזות deque<string> מתוך קובץ נתון,
ifstream in("file1.txt");
deque<string> d1;
נגדיר שני משתנים מסוג istream_iterator<string> istream_iterator<string> isi_1(in); istream_iterator<string> isi_2; האיטרטור הראשון מציין את תחילת זרם הקלט, האיטרטור השני - שמאותחל ללא פרמטרים - מציין סוף זרם (EOF). וכעת ניתן להעתיק את "סידרת" הקלט [isi_1..isi_2) לתוך התור d1, תוך שימוש בפונקציה copy() ובאיטרטור הכנסה אחורי: copy(isi_1, isi_2, back_inserter(d1)); אלגוריתמיםהאלגוריתמים ב- STL ממומשים ע"י פונקציות template הפועלות על סדרת איברים כללית. ה"דבק" המחבר בין המיכלים לאלגוריתמים הוא האיטרטורים: האלגוריתם מקבל כפרמטר template את טיפוס האיטרטור המתאים ו/או את טיפוס האיבר, ובהתאם הוא פועל עליו. לדוגמא, אלגוריתם החיפוש ממומש ע"י הפונקציה find() המוגדרת כך: template <class InIter, class T> InIter find(InIter first, InIter last, const T& val); וניתן להפעילו לדוגמא כך: vector<string>::const_iterator it; it = find(v1.begin(), v1.end(), "CCC"); if(it!=v1.end()) // found string result = *it; הסבר: הפונקציה מקבלת כפרמטרי template את
והפרמטרים לפונקציה עצמה הם first,last מסוג InIter ו- val מסוג T. הפונקציה מחפשת את האיבר val בסדרת האיברים [first,last) ומחזירה איטרטור (מסוג InIter) לאיבר שנמצא, אחרת, אם לא נמצא, מוחזר איטרטור ל- last. פירוט האלגוריתמים עפ"י קטגוריותהאלגוריתמים נחלקים למספר קטגוריות עפ"י סוג הפעולות המבוצעות בהן:
לאלגוריתמים רבים קיימת גרסת פרדיקט: בגרסה זו, הפונקציה מקבלת כפרמטר נוסף עצם פונקציה - זהו עצם ממחלקה המבצעת Overloading לאופרטור הפונקציה ( ) - לביצוע השוואה או פעולת חישוב מסוימת. לדוגמא, לאלגוריתם sort() המבצע מיון של סדרה נתונה קיימות 2 גרסאות: 1) template<class Random_Iter> void sort(Random_Iter first, Random_Iter last);
2) template<class Random_Iter, class Pred> void sort(Random_Iter first, Random_Iter last, Pred pr);
בגרסה הראשונה, האלגוריתם מבצע מיון על סדרת האיברים [first,last) ע"י ביצוע השוואה בין האיברים באמצעות האופרטור "<". בגרסה השנייה, ההשוואה בין כל זוג איברים מבוצעת ע"י עצם הפונקציה הבינרי pr(e1,e2). עצמי פונקציות (function objects) הם בשימוש נרחב ב- STL להגדרת פרדיקטים. הטבלאות המובאות בעמ' 529-534 מפרטות את שמות האלגוריתמים ואופן הפעלתם עפ"י הקטגוריות הנ"ל. כמו כן, את הממשק המדויק של כל פונקצית אלגוריתם ניתן למצוא בנספח הספר. עצמי פונקציות תקנייםכפי שכבר צויין, עצם פונקציה הוא עצם ממחלקה המבצעת Overloading לאופרטור הפונקציה ( ) - לביצוע השוואה או פעולת חישוב מסוימת. הספרייה התקנית כוללת מספר קבוצות של מחלקות המשמשות כעצמי פונקציות:
כל מחלקות עצמי הפונקציות מוכרזות בספרייה <functional>. שתי מחלקות בסיסיות משמשות להגדרת מספר טיפוסים משותפים: unary_function ו- binary_function.
הטבלה הראשונה שבעמ' 535 כוללת את מחלקות עצמי הפרדיקטים והעצמים האריתמטיים.
הטבלה השנייה שבעמ' 535 הבאה מצידה את מחלקות ה- Adapters, Binders ו- Negaters - אלו משמשים להתאמת פרמטרים בהעברת פרדיקטים.
בדוגמאות הבאות נשתמש באופרטורי הפלט עבור vector ו- list הבאים:
template <class T>
inline ostream & operator<<(ostream &out, const vector<T>& v)
{
copy(v.begin(), v.end(), ostream_iterator<T>(out, " "));
return out;
}
template <class T>
inline ostream & operator<<(ostream &out, const list<T>& l)
{
copy(l.begin(), l.end(), ostream_iterator<T>(out, " "));
return out;
}
דוגמאות לשימוש בפרדיקטים - נתונה הגדרת הוקטור הבאה:
string arr[7] = { "you", "they", "it", "She", "me", "us", "I"};
vector<string> v(arr, arr+7);
sort(v.begin(), v.end()); cout << v << endl; I She it me they us you
sort(v.begin(), v.end(), less<string>()); cout << v << endl; I She it me they us you
sort(v.begin(), v.end(), greater<string>()); cout << v << endl; you us they me it She I
struct Less_no_case {
bool operator()(const string& s1, const string& s2)
{ return stricmp(s1.c_str(), s2.c_str())<0; }
};
sort(v.begin(), v.end(), Less_no_case());
cout << v << endl;
I it me She they us you
וכעת נראה מספר דוגמאות לשימוש בעצמי הפונקציה האריתמטיים: נתונה הגדרת הרשימות הבאות:
double darr1[6] = {1.23, 44.02, 0.34, -32.98, 0, 3};
double darr2[6] = {45.1, 0.11, -23, 9, 834, 1};
list<double> l1(darr1, darr1+6);
list<double> l2(darr2, darr2+6);
list<double> l3(6);
transform(l1.begin(), l1.end(), l3.begin(), negate<double>()); // l3 = -l1 cout << l3 << endl; -1.23 -44.02 -0.34 32.98 0 -3
transform(l3.begin(), l3.end(), l3.begin(), negate<double>()); // l3 = -l3 cout << l3 << endl; 1.23 44.02 0.34 -32.98 0 3
transform(l1.begin(), l1.end(), l2.begin(), l3.begin(), multiplies<double>()); cout << l1 << endl; cout << l2 << endl; cout << l3 << endl; 1.23 44.02 0.34 -32.98 0 3 45.1 0.11 -23 9 834 1 55.473 4.8422 -7.82 -296.82 0 3
list<double> l4;
transform(l1.begin(), l1.end(), l2.begin(), back_inserter(l4), multiplies<double>()); cout << l4 << endl; 55.473 4.8422 -7.82 -296.82 0 3
הספרייה המתמטיתהספרייה התקנית מספקת תמיכה בתכנות מתמטי מדעי ע"י מספר מרכיבים:
יש לשים לב ש- C++ מספקת תמיכה מתמטית בנוסף לזו המסופקת ע"י ספרייה התקנית של C הכוללת פונקציות לטיפול בחזקות, לוגריתמים, טריגונומטריה, יצירת מספרים אקראיים וכו'. valarrayvalarray הוא termplate מחלקה המייצג מערך לחישובים וקטוריים אריתמטיים ביעילות גבוהה: ניתן לבצע פעולות מתמטיות פשוטות, פעולות בחזקות, פעולות לוגריתמיות, פעולות טריגונומטריות ועוד. valarray שונה מ- vector בכך שהוא אינו מספק ממשק להכנסת איברים ולהוצאתם, וגם לא איטרטורים לתחילת הסדרה ולסופה. זאת משום שייעודו העיקרי הוא לביצוע פעולות על מערך נתון ולא תחזוקת הסדרה. קוד המיכל valarray מובא בעמ' 538. בנוסף, מוגדרות הפונקציות הגלובליות הבאות על valarray:
דוגמאות:1. הקוד הבא מאתחל עצמי valarray מטיפוס int, ומבצע עליהם פעולות:
int arr1[] = {1, 2, 3, 4};
valarray<int > v(arr1, 4); // {1, 2, 3, 4}
valarray<int> v1 = v ; // {1, 2, 3, 4}
valarray<int> v2 = v<<2 ; // {4, 8, 12, 16}
valarray<int> v3 = -v ; // {-1, -2, -3, -4}
valarray<int> v4 = 3 * v ; // {3, 6, 9, 12}
valarray<int> v5 = v + v4; // {4, 8, 12, 16}
2. פעולות הזזה על סיביות (<<,>>) ופעולות הזזה על איברים (shift, cshift):
int arr1[] = {1, 2, 3, 4};
valarray<int > v(arr1, 4); // {1, 2, 3, 4}
valarray<int> v1 = v <<2; // {4, 8, 12, 16}
valarray<int> v2 = v >> 1; // {0, 1, 1, 2}
valarray<int> v3 = v.shift(2) ; // {3, 4, 0, 0}
valarray<int> v4 = v.shift(-1); // {0, 1, 2, 3}
valarray<int> v5 = v.cshift(2); // {3, 4, 1, 2}
valarray<int> v6 = v.cshift(-1); // {4, 1, 2, 3}
לצורך הדפסת valarrays ניתן להגדיר אופרטור >> גלובלי:
template <class T>
ostream & operator<<(ostream& out, const valarray<T>& v)
{
for(int i=0; i<v.size(); i++)
out << v[i] << " ";
return out << endl;
}
וכעת ניתן להדפיס valarrays: cout << "v1 = " << v1; cout << "v2 = " << v2; 3. הגדרת מטריצת ממשיים כ- valarray של valarrays:
double arr1[] = {1, 2, 3, 4};
valarray<double> v1(arr1, 4);
valarray<valarray<double> > mat1(5); // 5*4 double matrix
mat1[0] = v1;
for(int i=1; i<mat1.size(); i++)
mat1[i] = mat1[i-1].cshift(1);
cout << "v1 = " << v1;
cout << "mat1 = " << endl << mat1;
valarray<valarray<double> > mat2 = mat1 / v1;
cout << "mat2 = mat1 / v1 = " << endl << mat2;
הפלט: v1 = 1 2 3 4 mat1 = 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 1 2 3 4 mat2 = mat1 / v1 = 1 1 1 1 2 1.5 1.33333 0.25 3 2 0.333333 0.5 4 0.5 0.666667 0.75 1 1 1 1 complexcomplex הוא template מחלקה תקני המייצג מספרים מרוכבים. מספר מרוכב כולל שני מרכיבים: חלק ממשי וחלק מדומה. מתמטית, מספר מרוכב c1 מוגדר ע"י צמד (a,b) כך, c1 = a + bi; כאשר:
complex מספק פעולות אריתמטיות על מספרים מרוכבים. קוד template המחלקה complex מובא בעמ' 542-543. דוגמאות:
complex<double> c1(4,5); // c1 = (4,5); complex<double> c2 = c1+4.0; // c2 = (8,5) complex<double> c3 = c1 * c2; // c3 = (8,60)
c1 + 4.0 = 4 + 5i + 4.0 = 8 + 5i = (8,5)
c3 = c1 * c2 = (4+5i) * (8 + 5i) = 32 + 20i + 40 i + 25*i*i
= 32 + 60i + 25*(-1) = 7 + 60i = (7,60)
cout << "c1 = " << c1 << endl; cout << "c2 = " << c2 << endl; cout << "c3 = " << c3 << endl;
c1 = (4,5) c2 = (8,5) c3 = (7,60)
complex<int> arr[] = { complex<int>(2,4), complex<int>(5),
complex<int>(1,0), complex<int>(0,0) };
valarray<complex<int> > v1(arr, 4), v2;
v2 = v1*v1;
cout << "v1 = " << v1 << endl;
cout << "v2 = " << v2 << endl;
v1 = (2,4) (5,0) (1,0) (0,0) v2 = (-12,16) (25,0) (1,0) (0,0)
numeric_limitsnumeric_limits הוא template מחלקה הכולל הגדרות גבולות של הטיפוס הנדון. קוד template המחלקה numeric_limits מובא בעמ' 545. לדוגמא, הקוד הבא מדפיס מספר מאפיינים של טיפוסים בסיסיים בשפה:
#include <limits>
#include <iomanip>
#include <iostream>
using namespace std;
void test_limits()
{
numeric_limits<char> cl;
numeric_limits<int> il;
numeric_limits<float> fl;
numeric_limits<double> dl;
cout << left;
cout << setw(10) << "type" << setw(10) << "signed" << setw(10) << "#digits" << setw(14) << "max" << setw(14) << "min" << endl;
cout << setw(10) << "----" << setw(10) << "------" << setw(10) << "-------" << setw(14) << "---" << setw(14) << "---" << endl;
cout << setw(10) << "char" << setw(10) << cl.is_signed << setw(10) << cl.digits << setw(14) << (int) cl.max() << setw(14) << (int) cl.min() << endl;
cout << setw(10) << "int" << setw(10) << il.is_signed << setw(10) << il.digits << setw(14) << il.max() << setw(14) << il.min() << endl;
cout << setw(10) << "float" << setw(10) << fl.is_signed << setw(10) << fl.digits << setw(14) << fl.max() << setw(14) << fl.min() << endl;
cout << setw(10) << "double" << setw(10) << dl.is_signed << setw(10) << dl.digits << setw(14) << dl.max() << setw(14) << dl.min() << endl;
}
יודפס: type signed #digits max min ---- ------ ------- --- --- char 1 7 127 -128 int 1 31 2147483647 -2147483648 float 1 24 3.40282e+038 1.17549e-038 double 1 53 1.79769e+308 2.22507e-308
מעבדהבצע/י את המעבדה שבסוף פרק זה. סיכום
|
