C++ STL Containers PDF

Cours de C++ 2 STL Containers Cécile Braunstein [email protected] EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 1/1  Introduction Container...

Cours de C++ 2 STL Containers Cécile Braunstein [email protected] EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 1/1  Introduction Containers - Why ? Help to solve messy problems Provide useful function and data structure Consistency between containers Containers Collection of objects Defined with the template classes : Seperate the container from the type of the data inside. Each containers type is optimized for a specific use (access/modification). Main containers: list, vector, stack, queue, map EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 2/1  Example : vector Operations Action Method Insert an element v.push_back() Remove an element v.pop_back() Remove all elements v.clear() Returns a value that denotes the first element v.begin() Returns a value that denotes (one past) the last v.end() element Returns a value that denotes the i th element v[i] Take the vector size v.size() Check emptiness v.empty() Attention : The first element is indexed by 0 and the last by size-1. EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 3/1  Container’s type list Insert and remove anywhere in constant time Automatic memory management vector General purpose Fast access by index (constant time) Remove an element at the end in constant time Other insert and remove in linear time set, map Access an element by a key in constant time Fast search of an element EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 4/1  Containers constructors  #include using namespace std; list one_list ; // empty list of double list second_list(10,4.22); // ten doubles with walue 4.22 list third_list (second_list) ; // a copy of the second list    #include using namespace std; vector one_vector; // empty vector of string vector two_vector(4); // 4 ints with undefined value   EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 5/1  Containers constructors container c; Empty container container c(c2); Copy of c2 container c(n); With n elements value-initialized ac- cording to T container c(n,t); With n elements copies of t container c(b,e); Copy of the elements an other con- tainer between [b,e) EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 6/1  Container’s properties Containers have their own elements Elements of a container have to support the copy and assigment instruction (=) All containers have a method empty() and size() in constant time All containers have a method begin() and end() EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 7/1  Which constructors are called ? 1/2  int main() { Point p1(1,3); Point p2(2,3); Point p3(3,5); std :: list liste_de_point ; liste_de_point.push_back(p1); liste_de_point.push_back(p2); liste_de_point.push_back(p3); return 0; }   EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 8/1  Which constructors are called ? 2/2  int main() { std :: list liste_de_point ; std :: list liste_de_point_2(3); std :: list liste_de_point_3(liste_de_point ) ; liste_de_point.push_back(p1); liste_de_point.push_back(p2); liste_de_point.push_back(p3); liste_de_point_2 = liste_de_point ; return 0; }   EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 9/1  How to choose ? What is the purpose ? How we want ot access the element (randomly, in one order...) Which modification on the collection of data (add/remove elements, sort...) Programm performance Access time/ Modification time Time depends on the number of elements Types of times : linear, log, exponential... Memory usage... EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 10 / 1  How to access element ? Iterator Purpose Pointer generalization Use for a sequential access to elements Optimisation regarding the container’s type Iterator Definition An iterator is a value that Identifies a container and an element in the container Lets us examine the value stored in that element Provides operations for moving between elements in the container Restricts the available operations to correspond to what the container can handle efficently EISE4/MAIN4 : Cours de C++ - STL Containers - [email protected] , 11 / 1  First example   vector v; vector v; // v is full // v is full vector::size_type vector::iterator iter ; i; for( iter = v.begin() ; for( i = 0; i != v.size () ; ++i) iter != v.end(); ++iter ) { { cout