Chapter 18 Vectors and Arrays Bjarne Stroustrup www.stroustrup.com/Programming

Chapter 18 Vectors and Arrays Bjarne Stroustrup www.stroustrup.com/Programming

Chapter 18 Vectors and Arrays Bjarne Stroustrup www.stroustrup.com/Programming Overview Vector revisited How are they implemented? Pointers and free store Destructors Initialization Copy and move Arrays Array and pointer problems Changing size

Templates Range checking and exceptions Stroustrup/Programming 3 Reminder Why look at the vector implementation? To see how the standard library vector really works To introduce basic concepts and language features To see how to directly deal with memory To see the techniques and concepts you need to understand C

Free store (heap) Copy and move Dynamically growing data structures Including the dangerous ones To demonstrate class design techniques To see examples of neat code and good design Stroustrup/Programming 4 vector // a very simplified vector of doubles (as far as we got in chapter 17): class vector { int sz; // the size double* elem; // pointer to elements public: vector(int s) :sz{s}, elem{new double[s]} { } // new allocates memory ~vector() { delete[ ] elem; } // destructor // delete[] deallocates memory // constructor double get(int n) { return elem[n]; }

// access: read void set(int n, double v) { elem[n]=v; } // access: write int size() const { return sz; } // the number of elements }; Stroustrup/Programming 5 Initialization: initializer lists We would like simple, general, and flexible initialization So we provide suitable constructors, including class vector { // public: vector(int s); // constructor (s is the element count) vector(std::initializer_list lst); // initializer-list constructor // }; vector v1(20); // 20 elements, each initialized to 0 vector v2 {1,2,3,4,5}; // 5 elements: 1,2,3,4,5 Stroustrup/Programming

6 Initialization: initializer lists We would like simple, general, and flexible initialization So we provide suitable constructors vector::vector(int s) // constructor (s is the element count) :sz{s}, elem{new double[s]} { } { for (int i=0; i lst) // initializer-list constructor :sz{lst.size()}, elem{new double[sz]} { } { std::copy(lst.begin(),lst.end(),elem); // copy lst to elem } vector v1(20);// 20 elements, each initialized to 0 vector v2 {1,2,3,4,5}; // 5 elements: 1,2,3,4,5 Stroustrup/Programming 7 Initialization: lists and sizes

If we initialize a vector by 17 is it By convention use 17 elements (with value 0)? 1 element with value 17? () for number of elements {} for elements For example vector v1(17); vector v2 {17}; // 17 elements, each with the value 0 // 1 element with value 17 Stroustrup/Programming

8 Initialization: explicit constructors A problem A constructor taking a single argument defines a conversion from the argument type to the constructors type Our vector had vector::vector(int), so vector v1 = 7; // v1 has 7 elements, each with the value 0 void do_something(vector v) do_something(7); // call do_something() with a vector of 7 elements This is very error-prone. Unless, of course, thats what we wanted For example complex d = 2.3; // convert from double to complex Stroustrup/Programming

9 Initialization: explicit constructors A solution Declare constructors taking a single argument explicit unless you want a conversion from the argument type to the constructors type class vector { // public: explicit vector(int s); // constructor (s is the element count) // }; vector v1 = 7; // error: no implicit conversion from int void do_something(vector v); do_something(7); // error: no implicit conversion from int Stroustrup/Programming 10 A problem

Copy doesnt work as we would have hoped (expected?) void f(int n) { vector v(n); // define a vector vector v2 = v; // what happens here? // what would we like to happen? vector v3; v3 = v; // what happens here? // what would we like to happen? // } Ideally: v2 and v3 become copies of v (that is, = makes copies) And all memory is returned to the free store upon exit from f() Thats what the standard vector does, but its not what happens for our still-too-simple vector Stroustrup/Programming 11

Nave copy initialization (the default) By default copy means copy the data members void f(int n) { vector v1(n); vector v2 = v1; // initialization: // by default, a copy of a class copies its members // so sz and elem are copied } 3 v1: v2: 3 Disaster when we leave f()! v1s elements are deleted twice (by the destructor) Stroustrup/Programming 12 Nave copy assignment (the default) void f(int n) {

vector v1(n); vector v2(4); v2 = v1; // assignment: // by default, a copy of a class copies its members // so sz and elem are copied } v1: 3 2nd v2: 1st Disaster when we leave f()! v1s elements are deleted twice (by the destructor) memory leak: v2s elements are not deleted Stroustrup/Programming 13 Copy constructor (initialization) class vector { int sz; double* elem; public: vector(const vector&) ; //

}; // copy constructor: define copy (below) vector::vector(const vector& a) :sz{a.sz}, elem{new double[a.sz]} // allocate space for elements, then initialize them (by copying) { for (int i = 0; i

3 The destructor correctly deletes all elements (once only for each vector) Stroustrup/Programming 15 Copy assignment class vector { int sz; double* elem; public: vector& operator=(const vector& a); // copy assignment: define copy (below) // }; x=a; a: 3 1st x: 2nd 8 1 2 3

4 2 4 Memory leak? (no) 8 4 2 Operator = must copy as elements Stroustrup/Programming 16 Copy assignment vector& vector::operator=(const vector& a) // like copy constructor, but we must deal with old elements // make a copy of a then replace the current sz and elem with as { double* p = new double[a.sz]; // allocate new space for (int i = 0; i

sz = a.sz; // set new size elem = p; // set new elements return *this; // return a self-reference // The this pointer is explained in Lecture 19 // and in 17.10 } Stroustrup/Programming 17 Copy with copy assignment void f(int n) { vector v1 {6,24,42}; vector v2(4); v2 = v1; } v1: // assignment 3 6 24

42 delete[ ]d by = No memory Leak 1st v2: 2nd 6 24 42 Stroustrup/Programming 18 Copy terminology Shallow copy: copy only a pointer so that the two pointers now refer to the same object

What pointers and references do Deep copy: copy what the pointer points to so that the two pointers now each refer to a distinct object What vector, string, etc. do Requires copy constructors and copy assignments for container classes Must copy all the way down if there are more levels in the object Copy of x: x: x: y: y: Shallow copy Copy of x: Copy of y: Deep copy Stroustrup/Programming

19 Deep and shallow copy v1: v2: 2 2 2 4 4 vector v1 {2,4}; vector v2 = v1; v2[0] = 3; int b = 9; int& r1 = b; int& r2 = r1; r2 = 7; // deep copy (v2 gets its own copy of v1s elements) // v1[0] is still 2 r2:

r1: b: // shallow copy (r2 refers to the same variable as r1) // b becomes 7 Stroustrup/Programming 20 Move Consider vector fill(istream& is) { vector res; for (double x; is>>x; ) res.push_back(x); return res; // returning a copy of res could be expensive // returning a copy of res would be silly! } void use() { vector vec = fill(cin); // use vec } Stroustrup/Programming

21 What we want: Move Before return res; in fill() vec: uninitialized res: 3 After return res; (after vector vec = fill(cin); ) vec: 3 res: 0 nullptr Stroustrup/Programming 22 Move Constructor and assignment

Define move operations to steal representation class vector { int sz; double* elem; public: vector(vector&&); && indicates move // move constructor: steal the elements vector& operator=(vector&&); // move assignment: // destroy target and steal the elements // . . . }; Stroustrup/Programming 23 Move implementation vector::vector(vector&& a) // move constructor :sz{a.sz}, elem{a.elem} // copy as elem and sz { a.sz = 0; // make a the empty vector a.elem = nullptr; }

Stroustrup/Programming 24 Move implementation vector& vector::operator=(vector&& a) // move assignment { delete[] elem; // deallocate old space elem = a.elem; // copy as elem and sz sz = a.sz; a.elem = nullptr; // make a the empty vector a.sz = 0; return *this; // return a self-reference (see 17.10) } Stroustrup/Programming 25 Essential operations Constructors from one or more arguments Default constructor

Copy constructor (copy object of same type) Copy assignment (copy object of same type) Move constructor (move object of same type) Move assignment (move object of same type) Destructor If you define one of the last 5, define them all Stroustrup/Programming 26 Arrays Arrays dont have to be on the free store char ac[7]; int max = 100; int ai[max];

// global array lives forever in static storage int f(int n) { char lc[20]; // local array lives until the end of scope on stack int li[60]; double lx[n]; // error: a local array size must be known at compile time // vector lx(n); would work // } Stroustrup/Programming 27 Address of: & You can get a pointer to any object not just to objects on the free store int a; char ac[20]; p: pc:

void f(int n) { a: ac: int b; int* p = &b; // pointer to individual variable p = &a; // now point to a different variable char* pc = ac; // the name of an array names a pointer to its first element pc = &ac[0]; // equivalent to pc = ac pc = &ac[n]; // pointer to acs nth element (starting at 0th) // warning: range is not checked // } Stroustrup/Programming 28 Arrays (often) convert to pointers void f(int pi[ ]) // equivalent to void f(int* pi) { int a[ ] = { 1, 2, 3, 4 }; int b[ ] = a; // error: copy isnt defined for arrays b = pi; // error: copy isnt defined for arrays. Think of a // (non-argument) array name as an immutable pointer pi = a;

// ok: but it doesnt copy: pi now points to as first element // Is this a memory leak? (maybe) int* p = a; // p points to the first element of a int* q = pi; // q points to the first element of a } pi: 1st 2nd a: 1 2 3 4 p: q: Stroustrup/Programming 29 Arrays dont know their own size void f(int pi[ ], int n, char pc[ ]) // equivalent to void f(int* pi, int n, char* pc) // warning: very dangerous code, for illustration only,

// never hope that sizes will always be correct { char buf1[200]; strcpy(buf1,pc); // copy characters from pc into buf1 // strcpy terminates when a '\0' character is found // hope that pc holds less than 200 characters strncpy(buf1,pc,200); // copy 200 characters from pc to buf1 // padded if necessary, but final '\0' not guaranteed int buf2[300]; // you cant say int buf2[n]; n is a variable if (300 < n) error("not enough space"); for (int i=0; i

// we dont know what this will overwrite return &ch[10]; // oops: ch disappears upon return from f() // (an infamous dangling pointer) } void g() { char* pp = f(); // *pp = 'c'; // we dont know what this will overwrite // (fs ch is gone for good after the return from f) } Stroustrup/Programming 31 Why bother with arrays? Its all that C has In particular, C does not have vector There is a lot of C code out there

There is a lot of C++ code in C style out there Here a lot means N*100M lines Youll eventually encounter code full of arrays and pointers They represent primitive memory in C++ programs Here a lot means N*1B lines We need them (mostly on free store allocated by new) to implement better container types Avoid arrays whenever you can They are the largest single source of bugs in C and (unnecessarily) in C++ programs They are among the largest sources of security violations, usually (avoidable) buffer overflows

Stroustrup/Programming 32 Types of memory vector glob(10); // global vector lives forever vector* some_fct(int n) { vector v(n); // local vector lives until the end of scope vector* p = new vector(n); // free-store vector lives until we delete it // return p; } void f() { vector* pp = some_fct(17); // delete pp; // deallocate the free-store vector allocated in some_fct() } its easy to forget to delete free-store allocated objects so avoid new/delete when you can (and thats most of the time) Stroustrup/Programming

33 Vector (primitive access) // a very simplified vector of doubles: vector v(10); for (int i=0; i

5.0 6.0 7.0 8.0 9.0 34 Vector (we could use pointers for access) // a very simplified vector of doubles: class vector { int sz; // the size double* elem; // pointer to elements public: explicit vector(int s) :sz{s}, elem{new double[s]} { } // constructor // double* operator[ ](int n) { return &elem[n]; } // access: return pointer }; vector v(10); for (int i=0; i

*v[i] = i; // means *(v[i]), that is, return a pointer to // the ith element, and dereference it cout << *v[i]; } 10 0.0 1.0 2.0 3.0 Stroustrup/Programming 4.0 5.0 6.0 7.0 8.0 9.0 35

Vector (we use references for access) // a very simplified vector of doubles: class vector { int sz; // the size double* elem; // pointer to elements public: explicit vector(int s) :sz{s}, elem{new double[s]} { } // constructor // double& operator[ ](int n) { return elem[n]; } // access: return reference }; vector v(10); for (int i=0; i

Stroustrup/Programming 4.0 5.0 6.0 7.0 8.0 9.0 36 Pointer and reference You can think of a reference as an automatically dereferenced immutable pointer, or as an alternative name for an object Assignment to a pointer changes the pointers value Assignment to a reference changes the object referred to You cannot make a reference refer to a different object int a = 10;

int* p = &a; // you need & to get a pointer *p = 7; // assign to a through p // you need * (or [ ]) to get to what a pointer points to int x1 = *p; // read a through p int& r = a; r = 9; int x2 = r; // r is a synonym for a // assign to a through r // read a through r p = &x1; r = &x1; // you can make a pointer point to a different object // error: you cant change the value of a reference Stroustrup/Programming 37 Next lecture Well see how we can change vectors implementation to better allow for changes in the number of elements. Then well modify vector to take elements of an arbitrary type and add range checking. Thatll imply looking at

templates and revisiting exceptions. Stroustrup/Programming 38

Recently Viewed Presentations

  • Prof. Dr. Basavaraj K. Nanjwade M. Pharm., Ph.

    Prof. Dr. Basavaraj K. Nanjwade M. Pharm., Ph.

    Constant K=D/h Where, D is the diffusion coefficient of the dissolving material and h is the thickness of the diffusion layer Here, C will always negligible compared to Cs So, dc/dt=DSCs/h 08/10/2010 * KLECOP, Nipani PHYSICOCHEMICAL FACTORS 1) pH PARTITION...
  • BELLWORK - Writing Assignment

    BELLWORK - Writing Assignment

    Spain and Portugal: European Rivals SPAIN: Christopher Columbus PORTUGAL: Amerigo Vespucci World Map 1482 World Map 1565 "The houses of these Indians are the most beautiful I have ever seen and I swear that the closer I get to the...
  • Going West Well: Suggestions for Success in English Program ...

    Going West Well: Suggestions for Success in English Program ...

    Annotation Resources to Investigate: KWL charts, the SQ3R method, SOAPSTone. Focus on Adaptability In English courses, professors will often ask you to draw upon existing composition skill sets as you move towards greater sophistication, which is good. But you must...
  • Pour la rentre Nous avons entendu Pour la

    Pour la rentre Nous avons entendu Pour la

    Emporter mes châteaux de sable, Mon cerf-volant, des coquillages. Et le portique de la plage. I wanted in my schoolbag. Je voulais dans mon cartable. To take my sandcastles, My kite, some shells. And the swings from the beach. Opportunity...
  • Critique Templates Needs Assessment:Final ReportJune 26, 2013

    Critique Templates Needs Assessment:Final ReportJune 26, 2013

    Scope of Work 1. The purpose of this task order is to conduct a needs assessment evaluation of the NIH Reviewer Critique Templates for the Office of Extramural Programs, Office of Extramural Research, Office of the Director, National Institutes of...
  • Act Three - Weebly

    Act Three - Weebly

    Macbeth has the power to execute or banish Banquo, but he doesn't dare do so because he and Banquo share the same friends. Macbeth wants these two guys to murder Banquo, tonight, some distance from the castle, because there can...
  • Molecular Genetics for the Practicing Physician: Can the ...

    Molecular Genetics for the Practicing Physician: Can the ...

    Molecular Genetics for the Practicing Physician: Can the Cancer Genome Atlas Impact How We Treat Patients? Gabriel G. Malouf, MD, PhD. Assistant Professor
  • DBQ PRACTICE - projecttahoe

    DBQ PRACTICE - projecttahoe

    For each of the documents assigned, write six questions that will help students to understand the documents. Share your questions with your table group. TIPS. Use a variety of LOTS, MOTS, AND HOTS. Start with the lowest level questions and...