Ch03List,Stacks,andQueues课件.ppt

Vector and list in the STL STL:Standard Template Library Collection or container Two popular implementations of the List ADT: Vector : provides a growable array implementation list : provides a doubly linked list implementation 3 methods available for all the STL containers: Int size() Void clear() Bool empty() methods available for vector and list: Void push_back(const Object x) Void pop_back() Const Object back() const Const Object front() const methods available for list only: Void push_front(const Object x) Void pop_front() methods available for vector only: Object operator[](int idx) Object at(int idx) Int capacity() const Void reserve(int new capacity) Iterator Liststring::iterator Vectorint::iterator Getting the iterator Iterator begin(): Iterator end() Iterator methods Itr++,++itr *itr Itr1==itr2 Itr1! Container operations that require iterators Iterator insert(iterator pos,const object x) Iterator erase(iterator pos) Iterator erase(iterator start,iterator end) Example:using erase on a list Const-iterators Implementation of vector Some important features of C++ primitive arrays: The array is simply a pointer variable to a block of memory; the actual array size must be maintained separately by the programmer. The block of memory can be allocated via new[],but then must be freed via delete[]. The block of memory cannot be resized(but a new presumably larger block can be obtained and initialized with the old block, and then the old block can ben freed). The main details of Vector The Vector will maintain the primitive array, the array capacity, and the current number of items stored in the Vector. Will implement the Big-Three to provide deep-copy semantics for the copy constructor and operator=,and will provide a destructor to reclaim the primitive array. Will provide a resize routine that will change the size of the Vector and a reserve routine that will change the capacity of the Vector. Will provide an implementation of operator[] Will provide