STL-1(1).pdf

CSCI 340 Data Structures and Algorithm Analysis Introduction to STL vector Minmei Hou, Dept. Computer Science, NIU 1  STANDARD TEMPLATE LIBRARY (STL) ⚫ GENERIC LIBRARY THAT MANAGES COLLECTIONS OF DATA WITH EFFICIENT ALGORITHMS...

CSCI 340 Data Structures and Algorithm Analysis Introduction to STL vector Minmei Hou, Dept. Computer Science, NIU 1  STANDARD TEMPLATE LIBRARY (STL) ⚫ GENERIC LIBRARY THAT MANAGES COLLECTIONS OF DATA WITH EFFICIENT ALGORITHMS ⚫ TEMPLATE CLASSES, FUNCTIONS, PARAMETERS ⚫ THE SAME/SINGLE IMPLEMENTATION WORKS FOR MANY DATA TYPES ⚫ COMPONENTS: ⚫ CONTAINERS – MANAGE COLLECTIONS OF DATA − SEQUENCE CONTAINERS E.G. VECTOR, LIST, DEQUE − ASSOCIATIVE CONTAINERS E.G. SET, MAP ⚫ ITERATORS – STEP THROUGH ELEMENTS IN AN CONTAINER ⚫ ALGORITHMS – PROCEDURES THAT PROCESS THE ELEMENTS OF COLLECTIONS − E.G. FIND, REMOVE Minmei Hou, Dept. Computer Science, NIU 2 STANDARD TEMPLATE LIBRARY (STL) vector’s iterator vector list’s iterator Global algorithm methods: set’s iterator copy transform list find search set mismatch fill replace sort deque’s iterator … map’s iterator deque map Minmei Hou, Dept. Computer Science, NIU 3  VECTOR ⚫ ONE OF THE SEQUENCE CONTAINERS ⚫ THE ORDER OF ELEMENTS IN THE CONTAINER DEPENDS ON THE TIME/SPACE OF THE INSERTION(S) OF THE ELEMENTS ⚫ INDEPENDENT OF THE VALUE OF THE ELEMENTS ⚫ DYNAMIC ARRAY ⚫ RANDOM ACCESS ⚫ ADDING/REMOVING ELEMENTS AT THE END IS FAST ⚫ INSERTING/REMOVING IN THE MIDDLE/BEGINNING IS SLOW (WHY?) Vector object it [] Minmei Hou, Dept. Computer Science, NIU 4  ITERATOR ⚫ AN OBJECT THAT ITERATES/NAVIGATES OVER ELEMENTS IN THE CONTAINER ⚫ AN ABSTRACTION OF POINTER ⚫ EACH CONTAINER PROVIDES ITS OWN ITERATOR ⚫ INTERFACES OF ITERATORS OF DIFFERENT CONTAINERS ARE LARGELY THE SAME ⚫ INTERNAL BEHAVIORS DEPEND ON THE DATA STRUCTURE OF THE CONTAINER ⚫ OPERATIONS Minmei Hou, Dept. Computer Science, NIU 5  ITERATOR OPERATIONS ⚫ OPERATOR * RETURNS THE ELEMENT OF THE CURRENT POSITIONS ⚫ OPERATOR -> ACCESS A MEMBER OF THE ELEMENT ⚫ OPERATOR ++ STEP FORWARD ⚫ OPERATOR -- STEP BACKWARD ⚫ OPERATOR == AND != WHETHER TWO ITERATORS REPRESENT THE SAME POSITION ⚫ OPERATOR = ASSIGN AN ITERATOR ⚫ IMPORTANT ITERATORS: ⚫ BEGIN( ) - FIRST ELEMENT ⚫ END( ) - PAST-THE-END Minmei Hou, Dept. Computer Science, NIU 6  MEMBER METHODS OF VECTOR ⚫ CONSTRUCTORS ⚫ DEFAULT CONSTRUCTOR ⚫ COPY CONSTRUCTOR ⚫ CONSTRUCTOR WITH GIVEN RANGE − FROM ANOTHER (TYPE OF) CONTAINER − WITH AN ARRAY − FROM STANDARD INPUT − TYPE MAY BE EVEN DIFFERENT PROVIDED AUTOMATIC CONVERSION ⚫ DESTRUCTOR ⚫ CAPACITY RELATED ⚫ OBTAINING ITERATORS ⚫ ELEMENT ACCESS ⚫ MODIFIERS Minmei Hou, Dept. Computer Science, NIU 7  CONSTRUCTOR EXAMPLES VECTOR< INT > INTVEC1; // DEFAULT CONSTRUCTOR … // ADD VALUES TO INTVEC1 VECTOR< INT > INTVEC2(INTVEC1); // COPY CONSTRUCTOR INT ARR [ ] = { 2, 3, 17, 33, 45 }; VECTOR< INT > INTVEC3(ARR, ARR + SIZEOF(ARR)/SIZEOF(ARR)); // THIS IS EQUIVALENT TO ( &ARR, &ARR ) // COPY ALL ELEMENTS OF THE ARRAY INTO THE VECTOR VECTOR< FLOAT > FVEC ( INTVEC3.BEGIN( ), INTVEC3.END( ) ); // COPY ALL ELEMENTS OF INTVEC3 AS FLOATS INTO A VECTOR Minmei Hou, Dept. Computer Science, NIU 8  MEMBER METHODS OF VECTOR ⚫ DESTRUCTOR ⚫ DESTRUCT THE VECTOR OBJECT ⚫ DEALLOCATE THE WHOLE STORAGE CAPACITY ALLOCATED BY THE VECTOR ⚫ IT CALLS EACH ELEMENT'S DESTRUCTOR Minmei Hou, Dept. Computer Science, NIU 9  MEMBER METHODS OF VECTOR ⚫ CAPACITY RELATED: ⚫ SIZE - THE ACTUAL NUMBER OF ELEMENTS IN THE VECTOR ⚫ EMPTY - WHETHER THE VECTOR IS EMPTY OR NOT ⚫ MAX_SIZE - THE MAXIMUM NUMBER OF ELEMENTS A CONTAINER MAY CONTAIN. - A CONSTRAINT FROM THE SYSTEM OR LIBRARY IMPLEMENTATION. THIS IS DIFFERENT FROM CAPACITY(). ⚫ CAPACITY - THE NUMBER OF ELEMENTS A VECTOR COULD CONTAIN IN ITS ACTUAL MEMORY. ⚫ RESIZE - RESIZE THE VECTOR. IN CASE OF LARGER SIZE, FILL THE REST WITH A CERTAIN VALUE. - DIFFERENT FROM RESERVE(). ⚫ RESERVE - CHANGE THE CAPACITY OF THE VECTOR. EXCEPTION IS THROWN IF NOT SUCCESSFUL. Minmei Hou, Dept. Computer Science, NIU 10  MEMBER METHODS OF VECTOR ⚫ OBTAINING ITERATORS: ⚫ BEGIN - RETURN THE ITERATOR TO THE FIRST ELEMENT ⚫ END - RETURN THE ITERATOR TO THE POSITION AFTER THE LAST ELEMENT ⚫ RBEGIN - RETURN THE REVERSE_ITERATOR TO THE REVERSE BEGINNING (I.E. THE LAST ELEMENT) ⚫ REND - RETURN THE REVERSE_ITERATOR TO THE POSITION BEFORE THE REVERSE END (I.E. THE POSITION BEFORE THE FIRST ELEMENT) Vector object begin() rbegin() end() rend() Minmei Hou, Dept. Computer Science, NIU 11  MEMBER METHODS OF VECTOR ⚫ ELEMENT ACCESS ⚫ (THROUGH ITERATORS) ⚫ OPERATOR [ ] - ACCESS THE ELEMENT AT A CERTAIN POSITION. IT DOES NOT CHECK THE VALID RANGE. ⚫ AT – SIMILAR TO [ ]. IT CHECKS RANGE, AND THROWS EXCEPTION. ⚫ FRONT – RETURNS A REFERENCE TO THE FIRST ELEMENT ⚫ BACK – RETURNS A REFERENCE TO THE LAST ELEMENT Vector object begin() rbegin() end() front( ) [] at( ) back( ) rend() Minmei Hou, Dept. Computer Science, NIU 12  MEMBER METHODS OF VECTOR ⚫ MODIFIERS ⚫ ASSIGNMENTS − OPERATOR= : COPY FROM ANOTHER VECTOR CONTAINING THE SAME TYPE − ASSIGN : ASSIGNS NEW CONTENT TO THE CURRENT VECTOR. OVERLOADED. − SWAP : EXCHANGE TWO VECTORS. ⚫ INSERTING ELEMENTS − INSERT : INSERT NEW ELEMENT IN FRONT OF A SPECIFIED POSITION − PUSH_BACK : APPEND A NEW ELEMENT TO THE END OF THE VECTOR − EMPLACE_BACK : CONSTRUCT A NEW ELEMENT IN-PLACE AT THE END ⚫ REMOVING ELEMENTS − ERASE : REMOVE AN ELEMENT OR A RANGE OF ELEMENTS − POP_BACK : REMOVE THE LAST ELEMENT − RESIZE : CHANGE THE NUMBER OF ELEMENTS − CLEAR : REMOVE ALL ELEMENTS FROM THE VECTOR Minmei Hou, Dept. Computer Science, NIU 13  MORE ABOUT VECTOR ⚫ WHAT OPERATIONS MAY CAUSE REALLOCATION OF THE INTERNAL ARRAY ⚫ RESERVE ⚫ PUSH_BACK, EMPLACE_BACK ⚫ INSERT, EMPLACE ⚫ NOTE THAT POP_BACK, ERASE, CLEAR DO NOT CAUSE REALLOCATION ⚫ WHAT IF DO WANT TO REDUCE MEMORY SIZE FOR UNUSED POSITIONS ⚫ SHRINK_TO_FIT : REDUCE MEMORY USAGE BY FREEING UNUSED MEMORY ⚫ WHEN REALLOCATION HAPPENS, ALL REFERENCES, POINTERS, AND ITERATORS REFERRING TO ELEMENTS OF THE ORIGINAL VECTOR BECOME INVALIDATED. Minmei Hou, Dept. Computer Science, NIU 14  MORE ABOUT VECTOR Vector object it Add one more element it it Add one more element. Space is not enough. Reallocation happens. Minmei Hou, Dept. Computer Science, NIU 15  MORE ABOUT VECTOR ⚫ TIME COMPLEXITY OF THE OPERATIONS ⚫ CONSIDER WORST CASE ⚫ USE O-NOTATION ⚫ LINEAR TIME O(N): CLEAR, INSERT, ERASE, ASSIGN, RESIZE, DESTRUCTOR, OPERATOR=, COPY CONSTRUCTOR, CONSTRUCTOR WITH A GIVEN RANGE ⚫ CONSTANT TIME O(1): ALL OTHER OPERATIONS, INCLUDING PUSH_BACK, EMPLACE_BACK, POP_BACK, SWAP, OPERATOR[ ], AT... Minmei Hou, Dept. Computer Science, NIU 16  PUSH_BACK VS. EMPLACE_BACK HISTORY PUSH_BACK WAS INTRODUCED EARLIER WHEN ELEMENT TYPE IS A BUILT-IN DATA TYPE SUCH AS INTEGER NO IMPACT WHEN ELEMENT TYPE IS A CLASS OR STRUCT EMPLACE_BACK IS MORE EFFICIENT THAN PUSH_BACK EMPLACE_BACK CONSTRUCTS AN OBJECT TAKING ARGUMENT(S), AVOIDING MAKING A COPY PUSH_BACK MAKES A COPY FROM ARGUMENT Minmei Hou, Dept. Computer Science, NIU 17  WHEN TO USE VECTOR DYNAMIC SIZE WHEN THE NUMBER OF ELEMENTS IS NOT KNOW OR SUBJECT TO CHANGE SEQUENTIAL ACCESS AND ITERATION SEQUENTIAL ACCESS SIMPLICITY RANDOM ACCESS CONSTANT TIME RANDOM ACCESS TO ELEMENTS BASED ON POSITION APPENDING ELEMENTS AT END OTHER THAN REALLOCATION HAPPENS, IT IS CONSTANT TIME TO APPEND CONTIGUOUS STORAGE LEADING TO MEMORY EFFICIENCY IMPROVING CACHE LOCALITY Minmei Hou, Dept. Computer Science, NIU 18  MORE ABOUT ITERATOR THERE ARE FOUR TYPES OF ITERATORS ITERATOR // TYPICAL USE CONST_ITERATOR // YOU NEED TO USE THIS IF GIVEN CONST CONTAINER REVERSE_ITERATOR // TO USE WITH RBEGIN, REND CONST_REVERSE_ITERATOR “ITERATOR” IS MOST USED MANY CONTAINER FUNCTIONS DEMAND THE “ITERATOR” TYPE THERE ARE SOME CONVERSIONS BETWEEN SOME ITERATOR TYPES Minmei Hou, Dept. Computer Science, NIU 19