1、Chapter 19 Vectors, templates, and exceptions,Bjarne S is the third of the lectures exploring the design of the standard library vector and the techniques and language features used to implement it. Here, we deal with changing the size of a vector, parameterization of a vector with an element type (
2、templates), and range checking (exceptions).,2,Stroustrup/Programming,Overview,Vector revisited How are they implemented? Pointers and free store Destructors Initialization Copy and move Arrays Array and pointer problems Changing size resize() and push_back() Templates Range checking and exceptions,
3、3,Stroustrup/Programming,Changing vector size,Fundamental problem addressed We (humans) want abstractions that can change size (e.g., a vector where we can change the number of elements). However, in computer memory everything must have a fixed size, so how do we create the illusion of change? Given
4、 vector v(n); / v.size()=nwe can change its size in three ways Resize it v.resize(10); / v now has 10 elementsAdd an element v.push_back(7); / add an element with the value 7 to the end of v / v.size() increases by 1 Assign to it v = v2; / v is now a copy of v2 / v.size() now equals v2.size(),4,Stro
5、ustrup/Programming,Representing vector,If you resize() or push_back() once, youll probably do it again; lets prepare for that by sometimes keeping a bit of free space for future expansionclass vector int sz;double* elem;int space; / number of elements plus “free space”/ (the number of “slots” for ne
6、w elements) public:/ ;,5,allocation:,sz:,-elements- (initialized),-free space- (uninitialized),0,Stroustrup/Programming,Representing vector,An empty vector (no free store use):A vector(n) (no free space):,6,N:,0,Stroustrup/Programming,vector:reserve(),First deal with space (allocation); given space
7、all else is easy Note: reserve() doesnt mess with size or element valuesvoid vector:reserve(int newalloc)/ make the vector have space for newalloc elements if (newalloc=space) return; / never decrease allocationdouble* p = new doublenewalloc; / allocate new spacefor (int i=0; isz; +i) pi=elemi; / co
8、py old elementsdelete elem; / deallocate old spaceelem = p; space = newalloc; ,7,Stroustrup/Programming,vector:resize(),Given reserve(), resize() is easy reserve() deals with space/allocation resize() deals with element valuesvoid vector:resize(int newsize)/ make the vector have newsize elements/ in
9、itialize each new element with the default value 0.0 reserve(newsize); / make sure we have sufficient spacefor(int i = sz; inewsize; +i) elemi = 0; / initialize new elementssz = newsize; ,8,Stroustrup/Programming,vector:push_back(),Given reserve(), push_back() is easy reserve() deals with space/allo
10、cation push_back() just adds a valuevoid vector:push_back(double d)/ increase vector size by one/ initialize the new element with d if (sz=0) / no space: grab somereserve(8);else if (sz=space) / no more free space: get more spacereserve(2*space);elemsz = d; / add d at end+sz; / and increase the size
11、 (sz is the number of elements) ,9,Stroustrup/Programming,resize() and push_back(),class vector / an almost real vector of doublesint sz; / the sizedouble* elem; / a pointer to the elementsint space; / size+free_space public:/ constructors and destructors double,10,Stroustrup/Programming,The this po
12、inter,A vector is an object vector v(10); vector* p = / we can point to a vector object Sometimes, vectors member functions need to refer to that object The name of that “pointer to self” in a member function is this,11,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,10,v:,this:,10,p:,Stroustrup/Programming
13、,The this pointer,vector / rare use made possible by operator=() returning *this/ The this pointer has uses that are less obscure one of which well get to in two minutes,12,Stroustrup/Programming,Assignment,Copy and swap is a powerful general ideavector / return a self-reference ,13,Stroustrup/Progr
14、amming,Optimize assignment,“Copy and swap” is the most general idea but not always the most efficient What if there already is sufficient space in the target vector? Then just copy! For example: a = b;,14,sz:,sz:,b:,a:,Stroustrup/Programming,Optimized assignment,vector ,15,Stroustrup/Programming,Tem
15、plates,But we dont just want vector of double We want vectors with element types we specify vector vector vector vector / vector of pointers vector / vector of vectors vector We must make the element type a parameter to vector vector must be able to take both built-in types and user-defined types as
16、 element types This is not some magic reserved for the compiler; we can define our own parameterized types, called “templates”,16,Stroustrup/Programming,Templates,The basis for generic programming in C+ Sometimes called “parametric polymorphism” Parameterization of types (and functions) by types (an
17、d integers) Unsurpassed flexibility and performance Used where performance is essential (e.g., hard real time and numerics) Used where flexibility is essential (e.g., the C+ standard library)Template definitions template class Buffer /* */ ; template void fill(Buffer thats what buf has,17,Stroustrup
18、/Programming,Parameterize with element type,/ an almost real vector of Ts: template class vector / ; vector vd; / T is double vector vi; / T is int vector vvi; / T is vector/ in which T is int vector vc; / T is char vector vpd; / T is double* vector* vvpd; / T is vector*/ in which T is double,18,Str
19、oustrup/Programming,Basically, vector is,/ an almost real vector of doubles: class vector int sz; / the sizedouble* elem; / a pointer to the elementsint space; / size+free_space public:vector() : sz(0), elem(0), space(0) / default constructorexplicit vector(int s) :sz(s), elem(new doubles), space(s)
20、 / constructorvector(const vector,19,Stroustrup/Programming,Basically, vector is,/ an almost real vector of chars: class vector int sz; / the sizechar* elem; / a pointer to the elementsint space; / size+free_space public:vector() : sz0, elem0, space0 / default constructorexplicit vector(int s) :szs,
21、 elemnew chars, spaces / constructorvector(const vector,20,Stroustrup/Programming,Basically, vector is,/ an almost real vector of Ts: template class vector / read “for all types T” (just like in math)int sz; / the sizeT* elem; / a pointer to the elementsint space; / size+free_space public:vector() :
22、 sz0, elem0, space0; / default constructorexplicit vector(int s) :szs, elemnew Ts, spaces / constructorvector(const vector,21,Stroustrup/Programming,Basically, vector is,/ an almost real vector of Ts: template class vector / read “for all types T” (just like in math)int sz; / the sizeT* elem; / a po
23、inter to the elementsint space; / size+free_space public:/ constructors and destructors T,22,Stroustrup/Programming,Templates,Problems (“there is no free lunch”) Poor error diagnostics Often spectacularly poor (but getting better in C+11; much better in C+14) Delayed error messages Often at link tim
24、e All templates must be fully defined in each translation unit (So place template definitions in header files Recommendation Use template-based libraries Such as the C+ standard library E.g., vector, sort() Soon to be described in some detail Initially, write only very simple templates yourself Unti
25、l you get more experience,23,Stroustrup/Programming,Range checking,/ an almost real vector of Ts:struct out_of_range /* */ ;template class vector / T ,24,Stroustrup/Programming,Range checking,void fill_vec(vector ,25,Stroustrup/Programming,Exception handling,We use exceptions to report errors We mus
26、t ensure that use of exceptions Doesnt introduce new sources of errors Doesnt complicate our code Doesnt lead to resource leaks,Stroustrup/Programming,26,Resource management,A resource is something that has to be acquired and must be released (explicitly and implicitly) Examples of resources Memory
27、Locks File handles Thread handles Sockets Windows,Stroustrup/Programming,27,void suspicious(int s, int x) int* p = new ints; / acquire memory/ . . .delete p; / release memory ,Resource management,Why suspicious? It is easy to make mistakes with pointers and deletevoid suspicious(int s, int x) int* p
28、 = new ints; / acquire memory/ . . .if (x) p = q; / make p point to another object/ . . .delete p; / release memory (but the wrong memory) ,Stroustrup/Programming,28,Resource management,Why suspicious? Its easy not to get to the end of the functionvoid suspicious(int s, int x) int* p = new ints; / a
29、cquire memory/ . . .if (x) return; / maybe we dont get to the end: leak/ . . .delete p; / release memory ,Stroustrup/Programming,29,Resource management,Why suspicious? Its easy not to get to the end of the functionvoid suspicious(int s, int x) int* p = new ints; / acquire memory/ . . .if (x) px = vx
30、; / vx may throw an exception: leak/ . . .delete p; / release memory ,Stroustrup/Programming,30,Resource management,Nave, ugly, fix void suspicious(int s, int x) / messy code int* p = new ints; / acquire memoryvector v;/ . . .try if (x) px = vx; / may throw/ . . . catch (. . .) / catch every excepti
31、ondelete p; / release memorythrow; / re-throw the exception/ . . .delete p; / release memory ,Stroustrup/Programming,31,Resource management,Simple, general solution RAII: “Resource Acquisition is initialization” Also known as scoped resource managementvoid f(vector/ . . . / vectors destructor releas
32、es memory upon scope exit,Stroustrup/Programming,32,Resource management,But what about functions creating objects? Traditional, error-prone solution: return a pointervector* make_vec() / make a filled vector vector* p = new vector; / we allocate on free store/ . . . fill the vector with data; this m
33、ay throw an exception . . .return p; / now users have to remember to delete / they will occasionally forget: leak!,Stroustrup/Programming,33,Resource management,But what about functions creating objects? Improved solution: use std:unique_ptrunique_ptr make_vec() / make a filled vector unique_ptr p n
34、ew vector; / allocate on free store/ fill the vector with data; this may throw an exception return p; / users dont have to delete; no delete in user code / a unique_ptr owns its object and deletes it automatically,Stroustrup/Programming,34,Resource management,But what about functions creating object
35、s? Even better solution: use std:make_unique C+14 only (unless you have an implementation of make_unique)unique_ptr make_vec() / make a filled vector auto p = make_uniquevector; / allocate on free store/ fill the vector with data; this may throw an exception return p; / no new in user code,Stroustru
36、p/Programming,35,Resource management,But what about functions creating objects? Best solution: dont mess with pointers (of any sort) at all Return the object itselfvector make_vec() / make a filled vector vector res;/ . . . fill the vector with data; this may throw an exception . . .return res; / ve
37、ctors move constructor efficiently transfers ownership / dont use pointers unless you really need them,Stroustrup/Programming,36,RAII (Resource Acquisition Is Initialization),Vector acquires memory for elements in its constructor Manage it (changing size, controlling access, etc.) Gives back (releas
38、es) the memory in the destructor This is a special case of the general resource management strategy called RAII Also called “scoped resource management” Use it wherever you can It is simpler and cheaper than anything else It interacts beautifully with error handling using exceptions Examples of reso
39、urces: Memory, file handles, sockets, I/O connections (iostreams handle those using RAII), locks, widgets, threads.,37,Stroustrup/Programming,A confession,The standard library vector doesnt guarantee range checking of You have been using Either our debug version, called Vector, which does check Or a
40、 standard library version that does check (several do)Unless your version of the standard library checks, we “cheated” In std_lib_facilities.h, we use the nasty trick (a macro substitution) of redefining vector to mean Vector #define vector Vector(This trick is nasty because what you see looking at
41、the code is not what compiler sees in real code macros are a significant source of obscure errors) We did the same for string,38,Stroustrup/Programming,What the standard guarantees,/ the standard library vector doesnt guarantee a range check in operator : template class vector / T ,39,Stroustrup/Pro
42、gramming,What the standard guarantees,Why doesnt the standard guarantee checking? Checking cost in speed and code size Not much; dont worry No student project needs to worry Few real-world projects need to worry Some projects need optimal performance Think huge (e.g., Google) and tiny (e.g., cell ph
43、one) The standard must serve everybody You can build checked on top of optimal You cant build optimal on top of checked Some projects are not allowed to use exceptions Old projects with pre-exception parts High reliability, hard-real-time code (think airplanes),40,Stroustrup/Programming,Access to co
44、nst vectors,template class vector / T / call the non-const version of : ok ,41,Stroustrup/Programming,String,A string is rather similar to a vector E.g. size(), , push_back() Built with the same language features and techniques A string is optimized for character string manipulation Concatenation (+
45、) Can produce a C-style string (c_str() input terminated by whitespace Small strings dont use free store (characters are stored in the handle),42,6,H,o,w,y,d,!,Stroustrup/Programming,0,Next lecture,An introduction to the STL, the containers and algorithms part of the C+ standard library. Here well meet sequences, iterators, and containers (such as vector, list, and map). The algorithms include find(), find_if(), sort(), copy(), copy_if(), and accumulate().,43,Stroustrup/Programming,
