יום שבת

Intro to STL, Containers, Vector

ה-STL היא ספריה של C++  המכילה classes מאד שימושיים. היא מחולקת ל-4 חלקים עיקריים:
1. Containers
2. Iterators
3. Algorithms
4. functors

אני מתכנן לכתוב מספר פוסטים בנושאים הנ"ל.
בפוסט הזה נתחיל  עם הסבר כללי על Containers, ובהמשך נתייחס ונתין דוגמא ל-vector שהוא אחד ה-classes השימושיים מסוג container.
בכל אופן, מומלץ להכיר את נושא ה-templates - הנה קישור לפוסט שדן ב-templates.




אז מי הם ה-containers?  זהו class שמאחסן קבוצה של אובייקטים - בדומה למערך. ה-containers בנויים כ-templates, כך ש-container יכול להכיל כל סוג של data type.
ה-containers מחולקים לשתי קבוצות משנה: sequence containers  ו-associative containers.
הסבר על שני סוגי ה-containers:
sequence containers - כאן האובייקטים שב-container מאופיינים ע"י מיקומם ברשימה.
דוגמאות: vector. הוקטור מסודר בדיוק כמו מערך: רשימה של איברים, לכל אחד מספר סידורי, שמבטא את מיקומו בקבוצה.
דוגמא נוספת: list. גם כאן מדובר בקבוצה מסודרת. המיקום של כל איבר נקבע בזמן הכנסתו. הסדר יכול כמובן להשתנות ע"י פעולות שיעשו לאחר הכנסת האלמנט. למשל: הכנסה של אלמנטים נוספים, מיון, היפוך סדר וכו.
associative containers - כאן סדר האובייקטים ברשימה נקבע ע"י פעולת מיון הקשורה לתוכן של האובייקטים. לכל אובייקט כאן  שני ערכים המאפיינים אותו: value type - שהוא התוכן של האובייקט. key_type - זהו המפתח על פיו ממוינת הרשימה. ישנם containers בהם ה-key type וה-value_type הם אותה ישות.


הנה רשימה של ה-containers הסטנדרטים:

Sequence Containers:
vector
list
dequeu

:Associative Containers
map
multimap
set 
multiset
bitset

בנוסף יש containers נוספים שאינם שייכים לרשימה הסטנדרטית:
hash_map
hash_multimap
hash_set
hash_multiset


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

אז ניגש כאן להכרות עם אחד ה-containers הנפוצים - vector.
כולנו מכירים את המערך (array) בשפת c.
אפשר להגדיר מערך בצורה סטטית, כמו בדוגמא הבאה:
int a[10];
החיסרון הבולט: גודל המערך נקבע בזמן הקומפילציה. הוא כמובן לא ניתן להגדלה באופן דינמי.
אפשר גם להקצות את המערך באופן דינאמי. הנה דוגמא:
int array_size = 100;
int *a = new int[array_size];
כאן יש לדאוג להחזרת הזכרון בסיום (delete), ועדיין לא ניתן להגדיל\להקטין את גודל הזיכרון המוקצה.

נראה בהמשך שה-vector container מאפשר הקצאה דינאמית, והגדלת\הקטנת הקצאת הזיכרון אפשרית בכל שלב. אלו רק חלק מהיכולות של vector.

כמו כל ה-container, ה-vector הוא template class. ההגדרה שלו נראית כך:


template <class T, class Allocator = allocator<T>>
class vector{

..
..
..
}


ה-template של vector כולל שני ארגומנטים:
T: זהו ה-type של האלמנטים של ה-vector.
Allocator: ה-type של האובייקטים שמוגדרים עבור ה-storage allocation. זהו פרמטר אופציונלי, וברירת המחדל היא T.


נתחיל עם רשימת המתודות של vector.  לאחר הרשימה נציג דוגמאות לשימוש במתודות, ונפרט את  הפעולה של כל אחת מהן.

רשימת המתודות של vector לפי סדר אלפאבתי:



assign();
at();
back();
begin();
capacity();
clear();
data();
empty();
end();
erase();
front();
insert();
max_size();
operator =();
operator []();
pop_back();
push_back();
rbegin();
rend();
reserve();
resize();
size();
swap();




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

 ==
!=
 <
>
 <=
 >=



לפני שנציג דוגמא שמפעילה את המתודות הנ"ל, נציג אובייקט נוסף- iterator.
ה-iterator הוא התחליף לשימוש ב-pointer ומשמש לצורך גישה לאלמנטים של ה-containers ושל ה-vector בפרט.
(בסוף הדוגמא כמה מילים על סיבוכיות.)

הנה דוגמא ל-iterator:

  1. vector<int> vec;
  2. vector<int>::iterator iter;
  3. iter = vec.begin();
  4. iter++;
  5. *iter = 5;

הסבר קטע הקוד הנ"ל:
שורה 1: יצירת וקטור מסוג int.
שורה 2: יצירת iterator מסוג int.
שורה 3: המתודה begin מחזירה iterator מצביע על תחילת הוקטור.
שורה 4: הגדלת ה-iterator. כעת יצביע על האלמנט השני בוקטור.
שורה 5: כתיבת הערך 5 לאלמנט השני בוקטור.

כעת, עם מושג כלשהו על iterators, נראה דוגמא המשתמשת במתודות של vector.

לפנינו תוכנית שמשתמשת בכל המתודות של vector. התוכנית אורגנה כך שסדר ההופעה של המתודות  הוא  לפי הסדר האלפביתי (פרט ל begin ו-end שהסתננו קודם, כי התוכנית דרשה זאת...). 
ליד כל מתודה בהופעתה הראשונה מצורף הסבר על פעולתה- ראה רקע צהוב. מעבר לכך, ה-comments בתוכנית מספקים הסבר מפורט. כדי להמנע מסרבול לא הוספתי פרוט בעברית.
אפשר כמובן להעתיק את התוכנית ולהריץ אותה (כרגיל).




  2. /*
  3.  * vector.cpp
  4.  *
  5.  *  Created on: Mar 19, 2012
  6.  *      Author: ronen
  7.  */



  11. #include <vector>        // Must include the vector header file
  12. #include <iostream>
  13. using namespace std;


  16. int main(){
  17. vector<int> vec; // here vec is created with size 0


  20. /* assign elements to the vector with size and value*/
  21. vec.assign(20,7); // here vec size is set to 20, objects value are all 7

  23. vector<int>::iterator iter1; // create an iterator
  24. vector<int>::iterator iter2; // create an iterator
  25. vector<int> new_vec; // create another int vector

  27. /** begin()
  28.   *  Returns a read/write iterator that points to the first
  29.   *  element in the %vector.  Iteration is done in ordinary
  30.   *  element order.
  31.   */
  32. iter1 = vec.begin() + 4; // iter1 points to the 5th element of vec.
  33. /** end()
  34.   *  Returns a read/write iterator that points one past the last
  35.   *  element in the %vector.  Iteration is done in ordinary
  36.   *  element order.
  37.   */
  38. iter2 = vec.end(); // iter2 points to the place after the last element of vec
  39. /* assign - iterator first ,iterator last */
  40. new_vec.assign(iter1, iter2);
  41. /* assign iterators anonymously: */
  42. new_vec.assign(vec.begin(), vec.end());//  now new_vec[] will have 20 elements, contents copied from vec

  44. /**at(n)
  45.   *  @brief  Provides access to the data contained in the vector.
  46.   *  @param n -The index of the element for which data should be
  47.   *  accessed.
  48.   *  @return  Read/write reference to data.
  49.   *  @throw  std::out_of_range  If @a n is an invalid index.
  50.   *
  51.   *  This function provides for safer data access.  The parameter
  52.   *  is first checked that it is in the range of the vector.  The
  53.   *  function throws out_of_range if the check fails.
  54.   */
  55. int a = vec.at(6); // a=vec[6] which is now 7.
  56. cout << " check result of vec.at. vec.at(6)= " << vec.at(6) << " vec[6] = " << vec[6]<<endl;

  58. /** back()
  59.    *  Returns a read/write reference to the data at the last
  60.    *  element of the %vector.
  61.    */
  62. a = vec.back(); // a will get value of last element of vec which is vec[19] equals 7.

  64.  /** capacity()
  65.   *  Returns the total number of elements that the %vector can
  66.   *  hold before needing to allocate more memory.
  67.   */
  68. a = vec.capacity(); // here the capacity is according to the size set by assign. it equals vec.size(). This may change if we use vec.reserve.
  69.  /** clear()
  70.   *  Erases all the elements.  Note that this function only erases the
  71.   *  elements, and that if the elements themselves are pointers, the
  72.   *  pointed-to memory is not touched in any way.  Managing the pointer is
  73.   *  the user's responsibility.
  74.   */
  75. vec.clear();

  77. /** empty()
  78.   *  Returns true if the %vector is empty.  (Thus begin() would
  79.   *  equal end().)
  80.   */
  81.    if(!vec.empty())
  82.   cout << "vec is not empty" << endl;
  83.    else
  84.   cout << " vec is empty"<<endl;


  87. vec.assign(20,7); // // After the vec.clear. vec is surely empty!. Let's assign it again with 20 elements
  88. /** end()
  89.   *  Returns a read/write iterator that points one past the last
  90.   *  element in the %vector.  Iteration is done in ordinary
  91.   *  element order.
  92.   */
  93. iter1 = vec.end(); // note: iter1 point to the entry beyond the vector's last element.
  94. /* erase vector at iterator position */
  95.    vec.erase(vec.begin()+5); // the 6th element of the vector is erased. The vector is now shrinked to 19 elements.
  96. /* erase range between iterators positions */
  97.    vec.erase(vec.begin(), vec.begin() + 10);// 1st to 10th elements are erased (range is always [ist, last) i.e. last element not included.
  98.    //  vector has now only 9 elements
  99.    cout << "size of vector: " << vec.size() << endl;
  100. /** front
  101.    *  Returns a read/write reference to the data at the first
  102.    *  element of the %vector.
  103.    */
  104.    a = vec.front(); // a=vec[0];
  105.    vec.front() = 4;// same as saying: vec[0] = 4;

  107. /* insert: insert new elements to the vector */
  108.    vec.insert(vec.begin() + 3, new_vec.begin(), new_vec.begin()+5); // here 6 elements form new_vec are inserted after vec's 4th element.

  110.    vec.insert(vec.begin(),20);// 20 is inserted after the first element
  111.    vec.insert(vec.begin(),10, 5);// 10 elements with value of 5 are inserted after first element
  112. /** max_size() Returns the size() of the largest possible %vector.  */
  113.    vec.max_size();// have no idea which is the max possible size. let's print it
  114.    cout << " vec.max size = " << vec.max_size()<< endl;
  115. //vec.operator =();
  116.    vec = new_vec; // vec is assigned with new_vec's value
  117. //vec.operator []();
  118.     a = vec[4]; // can read and write directly to the nth element.

  120.     /*  pop_back() @brief  Removes last element.
  121.   *
  122.   *  This is a typical stack operation. It shrinks the %vector by one.
  123.   *
  124.   *  Note that no data is returned, and if the last element's
  125.   *  data is needed, it should be retrieved before pop_back() is
  126.   *  called.
  127.   */
  128.     vec.pop_back();// last element is popped. Vector shrinks by 1. Can't get the popped value from this method.
  129. /** push_back(n)
  130.    *  @brief  Add data to the end of the %vector.
  131.    *  @param  x  Data to be added.
  132.    *
  133.    *  This is a typical stack operation.  The function creates an
  134.    *  element at the end of the %vector and assigns the given data
  135.    *  to it.  Due to the nature of a %vector this operation can be
  136.    *  done in constant time if the %vector has preallocated space
  137.    *  available.
  138.    */
  139.     vec.push_back(11); // 11 is added to the end of vec. vec.size() is incremented by 1
  140.     vec.push_back(12); // 12 is added to the end of vec. vec.size() is incremented by 1
  141.     vec.push_back(13); // 13 is added to the end of vec. vec.size() is incremented by 1
  142.     vec.push_back(14); // 14 is added to the end of vec. vec.size() is incremented by 1
  143. /** rbegin()
  144.    *  Returns a read/write reverse iterator that points to the
  145.    *  last element in the %vector.  Iteration is done in reverse
  146.    *  element order.
  147.    */
  148.     /* rbegin() returns a reverse iterator, so let's create one:
  149.      *
  150.      */
  151.     vector<int>::reverse_iterator riter1;
  152.     vector<int>::reverse_iterator riter2;
  153.     riter1 = vec.rbegin(); // now riter1 points to vec's last element. Note:Remember that vec.end() points one place after that.
  154. /** rend()
  155.    *  Returns a read/write reverse iterator that points to one
  156.    *  before the first element in the %vector.  Iteration is done
  157.    *  in reverse element order.
  158.    */
  159.     riter2 = vec.rend(); // riter2 points on the place before vec's first element.
  160. // let's print vec in reverse order:
  161.     vector<int>::reverse_iterator riter;
  162.     cout << " vec in reverse order: " << endl;
  163.     for ( riter=riter1 ; riter <riter2; ++riter )
  164.        cout << *riter << ", ";
  165.   // as a reference: here is the non reverse order:
  166.     cout << "\nsame vec in regular order: " << endl;
  167.     iter1 = vec.begin();
  168.     iter2 = vec.end();
  169.     vector<int>::iterator iter;
  170.     for ( iter=iter1 ; iter <iter2; ++iter )
  171.        cout << *iter << ", ";



  175.  /* reserve(n) Set the allocated storage of the vector. It doesn't change the size of the vector, but the reserved capacity can avoid the expensive memory
  176.   * relocation when expending the vector's size
  177.   */

  179.     vec.reserve(2); // here it will do nothing because capacity is more than 2
  180.     vec.reserve(200); // the vector is preserved with a total of 200 elements. size is not changed.
  181.     cout << " 200 places were resreved without affecting  size:\n";
  182. cout << "vec.capacity() = " << vec.capacity() << ", vec.size() = " << vec.size() << endl;

  184. /** resize(n)
  185.    *  @brief  Resizes the %vector to the specified number of elements.
  186.    *  @param  new_size  Number of elements the %vector should contain.
  187.    *  @param  x  Data with which new elements should be populated.
  188.    *
  189.    *  This function will %resize the %vector to the specified
  190.    *  number of elements.  If the number is smaller than the
  191.    *  %vector's current size the %vector is truncated, otherwise
  192.    *  the %vector is extended and new elements are populated with
  193.    *  given data.
  194.    */

  196.     vec.resize(50); // here size of vector is changed to 50 elements. No relocation is needed, as the vector is reserved with 200 elements.
  197.     vec.resize(40, 3); // size is changed to 40 entries with value = 3
  198. /**  Returns the number of elements in the %vector.  */
  199.     vec.size(); // size is 40 now
  200.     cout << "\ncurrent vec size is " << vec.size();
  201. /** swap(vector)
  202.   *  @brief  Swaps data with another %vector.
  203.   *  @param  x  A %vector of the same element and allocator types.
  204.   *
  205.   *  This exchanges the elements between two vectors in constant time.
  206.   *  (Three pointers, so it should be quite fast.)
  207.   *  Note that the global std::swap() function is specialized such that
  208.   *  std::swap(v1,v2) will feed to this function.
  209.   */
  210.   // let print vectors before and after swap:
  211.    cout << "\nprint vec before swap" << endl;
  212.      for ( iter=vec.begin() ; iter < vec.end(); ++iter )
  213.         cout << *iter << ", ";
  214.      cout << "\nprint new_vec before swap" << endl;
  215.          for ( iter=new_vec.begin() ; iter < new_vec.end(); ++iter )
  216.             cout << *iter << ", ";


  219.     vec.swap(new_vec); // here vec and new_vec are swapped.

  221.     cout << "\nprint vec after swap" << endl;
  222.        for ( iter=vec.begin() ; iter < vec.end(); ++iter )
  223.           cout << *iter << ", ";
  224.        cout << "\nprint new_vec after swap" << endl;
  225.            for ( iter=new_vec.begin() ; iter < new_vec.end(); ++iter )
  226.               cout << *iter << ", ";


  229. }



עוד על constructors של vector. הנה הצורות הקימות:
יצירת וקטור ריק.
  1. vector<T>vect;                                      
יצירת וקטור עם n אלמנטים

  1. vector<T>vect(size_type n);
יצירת וקטור עם n אלמנטים שערכם t
  1. vector<T>vect(size_type n, const T &t);
יצירת וקטור שגודלו ותוכנו בהתאם לתחום המוגדר ע"י שני ה-iterators:
  1. vector<T>vect(begin_iterator, end_iterator);


כל 4 סוגי ה-constructors הנ"ל משולבים בקטע הקוד הבא.

מודגשים בצהוב - ה-constructors.
מודגשות בירוק - פקודות שליחה ל-output.
מתחת לסוף התוכנית - העתק הפלט שודפס על המסך.

  1. /*
  2.  * vector_const.cpp
  3.  *
  4.  *  Created on: Mar 20, 2012
  5.  *      Author: ronen halevy
  6.  */

  8. #include <vector>
  9. #include <iostream>
  10. using namespace std;
  11. int main(void){
  12. vector <string>vect1;
  13. vector<string> vect2(5);
  14. string str = "start";
  15. vector<string> vect3(5, str);
  16. vector<string>vect_source(10, "asd");
  17. vector<string>vect4(vect_source.begin(), vect_source.end());
  18. vector<string>::iterator iter; // create an iterator
  19. cout << "\nvector <string>vect1; " << endl;
  20. for ( iter=vect1.begin() ; iter < vect1.end(); ++iter )
  21. cout << *iter << ", ";
  22. cout << "\nvector<string> vect2(5); " << endl;
  23. for ( iter=vect2.begin() ; iter < vect2.end(); ++iter )
  24. cout << *iter << ", ";
  25. cout << "\n vector<string> vect3(5, str);" << endl;

  27. for ( iter=vect3.begin() ; iter < vect3.end(); ++iter )
  28. cout << *iter << ", ";
  29. cout << "\nvector<string>vect4(vect_source.begin(), vect_source.end()); " << endl;

  31. for ( iter=vect4.begin() ; iter < vect4.end(); ++iter )
  32. cout << *iter << ", ";
  33. cout << endl;
  34. }

הפלט לשהודפס על המסך:

  1. vector <string>vect1; 

  3. vector<string> vect2(5); 
  4. , , , , , 
  5. vector<string> vect3(5, str);
  6. start, start, start, start, start, 
  7. vector<string>vect4(vect_source.begin(), vect_source.end()); 
  8. asd, asd, asd, asd, asd, asd, asd, asd, asd, asd, 


הסבר הפלט (מספרי השורות לא שייכים לפלט המקורי): 
הפלט מציג את תוכנם 4 הוקטורים שנוצרו ע"י 4 ה-constructors.
שורות 1.3.5.7 - הן רק כותרות.
 שורות 2,4,6,8 - הדפסה של 4 הוקטורים שאותחלו ע"י 4 ה-constructors:
שורה 2: ריקה כצפוי.
שורה 4: 5 אלמנטים לא מאותחלים בערך - הם blanks.
שורה 6: 5 אלמנטים עם הערך "start"
שורה 8: 10 אלמנטים עם הערך "asd"


כמה מילים על סיבוכיות:








פורסם על ידי ב-

2 תגובות:

  1. אנונימי22 במאי 2012 בשעה 2:13

    יפה מאוד !!
    שימושי מאוד !!

    השבמחק
  2. אנונימי1 ביוני 2012 בשעה 9:29

    יש מצב שאתה מסיר איך לעשות השמה : נניח יש לי מערך א" של פוינטרים (הוגדר ע"י וקטור) ואני מגדיר עוד מערך של פוינטרים ב"
    איך אני עושה השמה ביניהם.

    השבמחק

הירשם ל- תגובות לפרסום (Atom)