map

בפוסט הזה נדון על סוג נוסף של container, הפעם ממשפחת ה-associative containers. זהו הפוסט השלישי בסדרת ה-STL containers. הפוסט הראשון בנושא - לחץ לקישור אליו - הציג הקדמה והתמקד ב-vector container. הפוסט השני בנושא - לחץ לקישור אליו - הוקדש ל-list container.

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

Sequential Containers. 1 - האלמנטים בקבוצה מסודרים שם אחד אחרי השני, בלי קשר לתוכנם. אפשר כמובן לשנות מיקום של כל אלמנט, כולל אפשרות למיינם על פי התוכן. אבל הגישה לאלמנטים נעשית לפי מיקומם ברשימה. שני ה-containers שכבר נדונו בפוסטים קודמים - הvector וה-list הם sequential containers.

2. Associative Container - האלמנטים ב-associative container מורכבים מ- key ו-value. ערכו של ה-key הוא המזהה של האלמנט. ה-key וה-value יכולים להיות גם ישות אחת - למשל ב-container מסוג set. הפוסט הזה  דן ב-map, שם ה-key וה-type נפרדים.

כדי להבהיר את מהות ה-Associative Container הנה דוגמא: ספר טלפונים.
ניקח ספר טלפונים בו כל רשומה מורכבת משני שדות:

1. שם מנוי

2. מס טלפון.

למשל:

david cohen 052333223

sara toto   03232322

sheli siso  092323232 

yosi david 054323232 

המשתמש בספר הטלפונים מעוניין לשלוף מספר טלפון המתאים לשם המנוי. למשל: מה המספר של david cohen?

מה הדרך הנוחה יותר לנהל את ספר הטלפונים הזה?

נניח שהיינו בוחרים ב-sequential list. כדי למצוא מספר של מנוי, היינו צריכים לכתוב תוכנית שתסרוק את הרשימה, ותחפש מנוי עם השם המבוקש. 

ב-associative containers החיפוש אחר אלמנט עם key מתאים מובנה ב-class. ה-class כבר ממוין לפי ה-key בהתאם לשיטת סידור כלשהי (ברירת המחדל היא לפי סדר ערכים עולה של ה-key). ה-Associative Containers כוללות מתודות כגון find לצורך חיפוש. מכאן נראה שבהחלט עדיף יהיה להשתמש ב-associative container עבור ספר הטלפונים.

המתודות של map

map  הוא ה-container שנדון בו כאן. נציג  את רשימת המתודות של map. הרשימה מחולקת לשתי קבוצות - מתודות שכבר ראינו כשסקרנו את vector ואת list, ומתודות שאינן נתמכות ע"י שני ה-containers הנ"ל.

בהמשך נדגים את השימוש במתודות הצבועות צהוב.

מתודות הנתמכות גם ע"י vector ו-set:

constructor();

begin();

clear();

empty();

end();

erase();

insert();

max_size();

rbegin();

rend();

size();

swap();

מתודות שאינן נתמכות ע"י vector ו-set

 operator[];

key_comp();

value_comp();

find();

count();

lower_bound();

upper_bound();

equal_range();

דוגמאות לשימוש במתודות של map

הנה דוגמאות למתודות הצהובות מהרשימה למעלה.  אחרי הדוגמאות אפשר למצוא את התכנית הכוללת את  הדוגמאות ו-main שמפעילה אותן.


constructor

נציג בדוגמא את שלושת סוגי ה-constructors הנתמכים עבור map. בנוסף, עבור כל אחד מהסוגים מוצגות שתי וריאציות:

1. שימוש בפונקציית compare שמסופקת כ-default.

2. שימוש בפונקציית compare שהוגדרה כאן.

פונקציית ה-compare קובעת את צורת ההשוואה בין ה-keys, ומכאן את האופן בו ה-map מסודר. אם לא מגדירים במפורש פונקציית compare ב-constructor, ה-map ישתמש  בפונקציית ברירת המחדל. 
פונקציית ה-compare בברירת המחדל נראית כך (לא צריך לממש אותה בקוד, אבל היא מוצגת כאן רק לצורך ההסבר):

bool compare (const T& first_key, const T& second_key) const

  {

 return first_key<second_key;

  }

היא מחזירה true אם ה-low element קטן מה-high element. כתוצאה מכך, האלמנטים יהיו מסודרים בסדר עולה - לפי ערכי ה-key כמובן.

נדגים גם שימוש בפונקציית customized compare. נגדיר אותה כך שההשוואה תהיה הפוכה מזו של ה-default compare. . התוצאה:ה-map יהיה מסודר בסדר יורד. (נראה שהמימוש פשוט -  הפיכת הכיוון של >) 

ה-customized compare function  ממומשת כ-operator overloading method בתוך class.  המימוש  עם operator overloading יתאים בקלות ל-prototype של ה-constructor כפי שנראה מיד.

הנה ה-class הכולל את פונקציית ההשוואה החדשה:

class  MyCustomCompare{

public:

  bool operator() (const string& first_key, const string& second_key) const

  {

 return first_key>second_key;

  }

};

והנה התוכנית המדגימה את 3 סוגי ה-constructors, כשבכל פעם נדגים שתי וריאציות constructor ללא customized constructor ואתו - סה"כ 6 צורות.

הסבר רקע לתוכנית:

התוכנית מחולקת ל-6 חלקים צבועים ב-6 צבעים. 

שורות 3-10: default constructor עם default compare.

שורות 11-17: default constructor שמפעיל את ה-customized compare שב-MyCustomCompare.

שורות 18-20: iterator constructor. האלמנטים שיוכנסו ל-map נקבעים ע"י שני  iterators. בדוגמא הנ"ל, ה-iterators מצביעים על ההתחלה והסוף של map אחר, בשם phonebook.

שורות 21-23: iterator constructor, עם customized compare.

שורה 24-26: copy constructor. אל תוך ה-map מועתקים כל האלמנטים של map אחר. בדוגמא הנ"ל: של phonebook1.

שורה 27-29: copy constructor עם ה-customized compare.

אחרי כל אחד מה-constructors מופיעה פונקציה שמדפיסה את כל איברי  ה-map מהתחלה עד הסוף.
פונקציית ההדפסה נראית כך: 

void print_map(map<string, string> my_map){

map<string,string>::iterator iter;

cout << " <<print map with default compare>>" << endl;

for ( iter=my_map.begin(); iter != my_map.end(); iter++ )

    cout << (*iter).first << ", " << (*iter).second << endl;

}

הפלט של פקודות ההדפסה מוצג למטה מתחת לתוכנית.

1. void demo_constructor(){
2. //default constructor:
3. map<string,string> phonebook;
4. phonebook.insert(pair<string, string>("david levi", "052-4534333"));
5. phonebook.insert(pair<string, string>("sami ere", "052-4534333"));
6. phonebook.insert(pair<string, string>("asami", "052-4534333"));
7. phonebook.insert(pair<string, string>("tasami", "052-4534333"));
8. 
   
9. print_map(phonebook);
10. //default constructor + compare function:
11.     map<string,string,MyCustomCompare> phonebook_compare;      //with customized compare
12. 
    
13.     phonebook_compare.insert(pair<string, string>("david levi", "052-4534333"));
14.     phonebook_compare.insert(pair<string, string>("sami", "052-4534333"));
15.     phonebook_compare.insert(pair<string, string>("asami", "052-4534333"));
16.     phonebook_compare.insert(pair<string, string>("tasami", "052-4534333"));
17.     print_map_comp(phonebook_compare);
18. // iterator constructor
19. map<string,string> phonebook1 (phonebook.begin(),phonebook.end());
20. print_map(phonebook1);
21. // iterator constructor + compare function
22. map<string,string,MyCustomCompare>phonebook1_compare (phonebook.begin(),phonebook.end());
23. print_map_comp(phonebook1_compare);
24. //copy constructor
25. map<string,string> phonebook2 (phonebook1);;
26. print_map(phonebook2);
27. // copy constructor+ compare function
28. map<string,string,MyCustomCompare> phonebook2_compare(phonebook_compare) ;
29. print_map_comp(phonebook2_compare);
30. }

הנה הפלט - הצבעים בהתאם לקטע הקוד המתאים:

 <<print map with default compare>>

asami, 052-4534333

david levi, 052-4534333

sami ere, 052-4534333

tasami, 052-4534333

 <<print map with customized compare>>

tasami, 052-4534333

sami, 052-4534333

david levi, 052-4534333

asami, 052-4534333    phonebook_compare.insert(pair<string, string>("asami", "052-4534333"));

 <<print map with default compare>>

asami, 052-4534333

david levi, 052-4534333

sami ere, 052-4534333

tasami, 052-4534333

 <<print map with customized compare>>

tasami, 052-4534333

sami ere, 052-4534333

david levi, 052-4534333

asami, 052-4534333

 <<print map with default compare>>

asami, 052-4534333

david levi, 052-4534333

sami ere, 052-4534333

tasami, 052-4534333

 <<print map with customized compare>>

tasami, 052-4534333

sami, 052-4534333

david levi, 052-4534333

asami, 052-4534333

התיחסות לפלט:

שימו לב - לכל ה-maps הכנסנו בדיוק את אותם אלמנטים.

הפלט של ה-maps הראשון השלישי והחמישי מסודרים בסדר עולה - בהתאם ל-key.

הפלט של ה-maps השני, רביעי ושישי מוסדרים בסדר יורד.

הסיבה - שימוש בפונקצית compare שונה.

insert

המתודה insert מכניסה אלמנטים ל-map קיים. אם אלמנט בעל key זהה כבר קיים, ה-value שלו יוחלף. "אין מצב" ששני אלמנטים עם אותו key יהיו באותו map. (אגב, ה-multimap container יכול להחזיק אלמנטים עם key זהה).

האלמנטים ימוקמו ב-map עפ"י ה-key שלהם ובהתאם לפונקציית ה-compare, שהוגדרה ע"י ה-constructor. אם לא הוגדרה, אז לפי ה-default compare שיסדר את האלמנטים בסדר עולה, כפי שהוסבר למעלה בהקשר ל-constructors

map תומכת ב-3 prototypes של insert:

1. הכנסת אלמנט יחיד.

3. הכנסת קבוצה של אלמנטים המוצבעים ע"י iterators.

2. הכנסת אלמנט יחיד, עם hint -רמז לגבי המקום בו הוא אמור להכנס. ה"רמז" הוא iterator המצביע למקום ממנו ה-insert יתחיל לחפש את המקום המתאים.

הנה התוכנית:

1. void demo_insert(){
2. 
   
3. //1: insert a single pair, return a <iter, bool> value
4. map<string, string>  phonebook;
5. pair<map<string,string>::iterator,bool> ret_pair;
6. ret_pair = phonebook.insert(pair<string, string>("david levi", "052-4534333"));
7. cout << "ret_pair.first->first: " << ret_pair.first->first << ", ret_pair.first->second: " << ret_pair.first->second <<", ret_pair.second: "<< ret_pair.second << endl;
8. phonebook.insert(pair<string, string>("sara jackson", "031232323"));
9. phonebook.insert(pair<string, string>("yair tal", "0543434343"));
10. pair<string, string> my_pair("sami yaya", "343434343");
11. map<string,string>::iterator iter;
12.         phonebook.insert(my_pair);
13. cout << " print map elements" << endl;
14. for ( iter=phonebook.begin(); iter != phonebook.end(); iter++ )
15.    cout << (*iter).first << ", " << (*iter).second << endl;
16. 
    
17. //2: insert from a range by  iterators
18. map<string, string>  phonebook1;
19. phonebook1.insert( phonebook.begin(),phonebook.end());
20. cout << " print map elements" << endl;
21. 
    
22. for ( iter=phonebook1.begin(); iter != phonebook1.end(); iter++ )
23.    cout << (*iter).first << ", " << (*iter).second << endl;
24. //3: insert a single element, with a hint iterator. returns an iterator pointing to the inserted element.
25. iter = phonebook1.insert(phonebook.begin(), pair<string, string>("tutu rere", "05490034343"));
26. cout << " print map elements" << endl;
27. for ( iter=phonebook1.begin(); iter != phonebook1.end(); iter++ )
28.    cout << (*iter).first << ", " << (*iter).second << endl;
29. 
    
30. }

הסברים לתוכנית:

שורה 6 מכניסה אלמנט יחיד לתוך ה-map:

ret_pair = phonebook.insert(pair<string, string>("david levi", "052-4534333"));

דגשים לגבי שורה 6:

א. האלמנטים של map המורכבים תמיד מ-key ו-value. הם  מסודרים באובייקט pair שמכיל את שניהם.

ב. ה-prototype הזה של insert מחזיר שני ערכים, מסודרים ב-pair - ראה ret_pair.
הסבר על ה-ret_pair: 

ret_pair.first - הוא iterator המצביע על המקום שבו הוכנס האלמנט החדש.

ret_pair.second - הוא משתנה מסוג bool שערכו יהיה true אם האלמנט הוכנס, ו-false אם האלמנט החליף אלמנט עם אותו key.

שורה 7: ההדפסה של ret_pair (ראה הסבר בפסקה קודמת).

שלושה ערכים הודפסו:

ret_pair.first->first - מצביע על ה-key של האלמנט שהוכנס.

ret_pair.first->second - מצביע על ה-value שהוכנס/

ret_pair.second - מצביע על ה-bool שמוחזר. ראה הסבר למעלה לגבי שורה 6.

שורה 19 - insert מהסוג השני - ה-input מוצבע ע"י iterators.

שורה 25 - insert מהסוג השלישי - הכנסת אלמנט יחיד, כשערך ה-iterator קובע באיזה מקום להתחיל את החיפוש אחר המקום המתאים. הרמז נועד לקצר את  הפעולות הכרוכות ב-insert.

הערך המוחזר ע"י מתודת insert זו הוא ה-iterator המצביע על המקום של האלמנט שהוכנס.

הנה הפלט:

ret_pair.first->first: david levi, ret_pair.first->second: 052-4534333, ret_pair.second: 1

 print map elements

david levi, 052-4534333

sami yaya, 343434343

sara jackson, 031232323

yair tal, 0543434343

 print map elements

david levi, 052-4534333

sami yaya, 343434343

sara jackson, 031232323

yair tal, 0543434343

 print map elements

david levi, 052-4534333

sami yaya, 343434343

sara jackson, 031232323

tutu rere, 05490034343

yair tal, 0543434343

התייחסות לפלט:

שורת הפלט הראשונה, היא תוצר של שורה 7 בתוכנית. ההדפסה מתבססת על
 ה <pair<iterator, bool - ראה למעלה הסברים לתוכנית.

יתר שורות ההדפסה מתייחסות לקוד לפי הצבעים.

הסבר על יתר המתודות עדיין לא גמור - אבל התוכנית עם דוגמאות נוספות נמצאת כאן למטה.

סוגריים מרובעים []: 

- להוסיף הסבר.

דוגמא:

/* [] : Element Access */

void demo_paran(){

 map<string,string> phonebook;

 phonebook[" rere ww"]="043334343";

 phonebook[" name sis"]="8823232323";

 phonebook[" qwer ty"]= "232323233";

 cout << " phone number of  rere ww   is:"  << phonebook[" rere ww"] << endl;

 cout << " phone number of   name sis is "  << phonebook[" name sis"] << endl;

 cout << " phone number of   qwer ty  is "  << phonebook[" qwer ty"] << endl;

}

find

- להוסיף הסבר.

דוגמא:

void demo_find(){

 map<string, string> phonebook;

 phonebook.insert(pair<string, string>("sisi david", "054454545"));

 phonebook.insert(pair<string, string>("did rot", "054454545"));

 phonebook.insert(pair<string, string>("keli  spot", "054454545"));

 map<string,string>::iterator iter;

 string user_name = "keli  spot";

 iter=phonebook.find(user_name);

 if(iter != phonebook.end())

 cout << "phone number of hit " << iter->first << " is " << iter->second << endl;

 else

 cout << "phone number of " << user_name << " was not found " << endl;

  user_name = "jack robinson";

 iter=phonebook.find(user_name);

 if(iter != phonebook.end())

 cout << "phone number of hit " << iter->first << " is " << iter->second << endl;

 else

 cout << "phone number of " << user_name << " was not found " << endl;

}

key_comp

- להוסיף הסבר.

דוגמא:

void demo_key_comp(){

//default constructor + compare function:

    map<string,string> phonebook;                 // class as Compare

    map<string,string>::key_compare compare_func;

    phonebook.insert(pair<string, string>("sis erer", "053-4534333"));

    phonebook.insert(pair<string, string>("davd levi", "052-4534333"));

    phonebook.insert(pair<string, string>("asaf david", "052-4534333"));

    compare_func = phonebook.key_comp();

    string cmparison("davd levi");

    map<string ,string>::iterator iter ;

    for(iter = phonebook.begin(); iter != phonebook.end();*iter++){

if((compare_func(cmparison, iter->first) ))

cout << cmparison << " comes before or equals" << iter->first << endl;

else

cout << cmparison << " comes after " << iter->first << endl;

    }

//default constructor + compare function:

    map<string,string, MyCustomCompare> phonebook_compare;                 // class as Compare

    map<string,string, MyCustomCompare>::key_compare compare_func1;

    phonebook_compare.insert(pair<string, string>("sis erer", "053-4534333"));

    phonebook_compare.insert(pair<string, string>("davd levi", "052-4534333"));

    phonebook.insert(pair<string, string>("asaf david", "052-4534333"));

    compare_func1 = phonebook_compare.key_comp();

    for(iter = phonebook_compare.begin(); iter != phonebook_compare.end();*iter++){

if((compare_func(cmparison, iter->first) ))

cout << cmparison << " comes before " << iter->first << endl;

else

cout << cmparison << " comes after or equals" << iter->first << endl;

    }

}

לצורך נוחות ההעתקה - הנה התוכנית כולה - כולל main שמפעיל את הדוגמאות:

/*

 * stl_map.cpp

 *

 *  Created on: Mar 25, 2012

 *      Author: ronen halevy

 */

#include <iostream>

#include <map>

using namespace std;

class  MyCompare{

public:

  bool operator() (const string& first_key, const string& second_key) const

  {

 return first_key<second_key;

  }

};

class  MyCustomCompare{

public:

  bool operator() (const string& first_key, const string& second_key) const

  {

 return first_key>second_key;

  }

};

void print_map(map<string, string> my_map){

map<string,string>::iterator iter;

cout << " <<print map with default compare>>" << endl;

for ( iter=my_map.begin(); iter != my_map.end(); iter++ )

   cout << (*iter).first << ", " << (*iter).second << endl;

}

void print_map_comp(map<string, string, MyCustomCompare> my_map){

map<string,string>::iterator iter;

cout << " <<print map with customized compare>>" << endl;

for ( iter=my_map.begin(); iter != my_map.end(); iter++ )

   cout << (*iter).first << ", " << (*iter).second << endl;

}

void demo_constructor(){

//default constructor:

map<string,string> phonebook;

phonebook.insert(pair<string, string>("david levi", "052-4534333"));

phonebook.insert(pair<string, string>("sami ere", "052-4534333"));

phonebook.insert(pair<string, string>("asami", "052-4534333"));

phonebook.insert(pair<string, string>("tasami", "052-4534333"));

print_map(phonebook);

//default constructor + compare function:

    map<string,string,MyCustomCompare> phonebook_compare;                 // class as Compare

    phonebook_compare.insert(pair<string, string>("david levi", "052-4534333"));

    phonebook_compare.insert(pair<string, string>("sami", "052-4534333"));

    phonebook_compare.insert(pair<string, string>("asami", "052-4534333"));

    phonebook_compare.insert(pair<string, string>("tasami", "052-4534333"));

    print_map_comp(phonebook_compare);

// iterator constructor

map<string,string> phonebook1 (phonebook.begin(),phonebook.end());

print_map(phonebook1);

// iterator constructor + compare function

map<string,string,MyCustomCompare>phonebook1_compare (phonebook.begin(),phonebook.end());

print_map_comp(phonebook1_compare);

//copy constructor

map<string,string> phonebook2 (phonebook1);

print_map(phonebook2);

// copy constructor+ compare function

map<string,string,MyCustomCompare> phonebook2_compare(phonebook_compare) ;

print_map_comp(phonebook2_compare);

}

void demo_insert(){

map<string, string>  phonebook;

//1: insert a single pair, return a <iter, bool> value

pair<map<string,string>::iterator,bool> ret_pair;

    ret_pair = phonebook.insert(pair<string, string>("david levi", "052-4534333"));

cout << "ret_pair.first->first: " << ret_pair.first->first << ", ret_pair.first->second: " << ret_pair.first->second <<", ret_pair.second: "<< ret_pair.second << endl;

phonebook.insert(pair<string, string>("sara jackson", "031232323"));

phonebook.insert(pair<string, string>("yair tal", "0543434343"));

pair<string, string> my_pair("sami yaya", "343434343");

map<string,string>::iterator iter;

    phonebook.insert(my_pair);

cout << " print map elements" << endl;

for ( iter=phonebook.begin(); iter != phonebook.end(); iter++ )

   cout << (*iter).first << ", " << (*iter).second << endl;

//2: insert from a range by  iterators

map<string, string>  phonebook1;

phonebook1.insert( phonebook.begin(),phonebook.end());

cout << " print map elements" << endl;

for ( iter=phonebook1.begin(); iter != phonebook1.end(); iter++ )

   cout << (*iter).first << ", " << (*iter).second << endl;

//3: insert a single element, with a hint iterator. returns an iterator pointing to the inserted element.

iter = phonebook1.insert(phonebook.begin(), pair<string, string>("tutu rere", "05490034343"));

cout << " print map elements" << endl;

for ( iter=phonebook1.begin(); iter != phonebook1.end(); iter++ )

   cout << (*iter).first << ", " << (*iter).second << endl;

}

/* [] : Element Access */

void demo_paran(){

 map<string,string> phonebook;

 phonebook[" rere ww"]="043334343";

 phonebook[" name sis"]="8823232323";

 phonebook[" qwer ty"]= "232323233";

 cout << " phone number of  rere ww   is:"  << phonebook[" rere ww"] << endl;

 cout << " phone number of   name sis is "  << phonebook[" name sis"] << endl;

 cout << " phone number of   qwer ty  is "  << phonebook[" qwer ty"] << endl;

}

void demo_find(){

 map<string, string> phonebook;

 phonebook.insert(pair<string, string>("sisi david", "054454545"));

 phonebook.insert(pair<string, string>("did rot", "054454545"));

 phonebook.insert(pair<string, string>("keli  spot", "054454545"));

 map<string,string>::iterator iter;

 string user_name = "keli  spot";

 iter=phonebook.find(user_name);

 if(iter != phonebook.end())

 cout << "phone number of hit " << iter->first << " is " << iter->second << endl;

 else

 cout << "phone number of " << user_name << " was not found " << endl;

  user_name = "jack robinson";

 iter=phonebook.find(user_name);

 if(iter != phonebook.end())

 cout << "phone number of hit " << iter->first << " is " << iter->second << endl;

 else

 cout << "phone number of " << user_name << " was not found " << endl;

}

void demo_key_comp(){

//default constructor + compare function:

    map<string,string> phonebook;                 // class as Compare

    map<string,string>::key_compare compare_func;

    phonebook.insert(pair<string, string>("sis erer", "053-4534333"));

    phonebook.insert(pair<string, string>("davd levi", "052-4534333"));

    phonebook.insert(pair<string, string>("asaf david", "052-4534333"));

    compare_func = phonebook.key_comp();

    string cmparison("davd levi");

    map<string ,string>::iterator iter ;

    for(iter = phonebook.begin(); iter != phonebook.end();*iter++){

if((compare_func(cmparison, iter->first) ))

cout << cmparison << " comes before or equals" << iter->first << endl;

else

cout << cmparison << " comes after " << iter->first << endl;

    }

//default constructor + compare function:

    map<string,string, MyCustomCompare> phonebook_compare;                 // class as Compare

    map<string,string, MyCustomCompare>::key_compare compare_func1;

    phonebook_compare.insert(pair<string, string>("sis erer", "053-4534333"));

    phonebook_compare.insert(pair<string, string>("davd levi", "052-4534333"));

    phonebook.insert(pair<string, string>("asaf david", "052-4534333"));

    compare_func1 = phonebook_compare.key_comp();

    for(iter = phonebook_compare.begin(); iter != phonebook_compare.end();*iter++){

if((compare_func(cmparison, iter->first) ))

cout << cmparison << " comes before " << iter->first << endl;

else

cout << cmparison << " comes after or equals" << iter->first << endl;

    }

}

int main()

{

demo_constructor();

demo_insert();

demo_paran();

demo_find();

demo_key_comp();

return 0;

}