Low level data structures

optimizing data structures in high-level programs and a level computing data structures
Dr.DavisHardy Profile Pic
Dr.DavisHardy,Germany,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
Managing Memory (and low level Data Structures)Programming Principle of the Day • Avoid Premature Optimization  Don‟t even think about optimization unless your code is working, but slower than you want. Only then should you start thinking about optimizing, and then only with the aid of empirical data.  "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil" - Donald Knuth. http://en.wikipedia.org/wiki/Program_optimization 2 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Low Level Data Structures • We were using the standard library data structures – containers  How are these built?  Low level language facilities and data structures  Closer to computer hardware (in semantics and abstraction level)  Why do we need to know how are these built?  Useful techniques, applicable in other contexts  More dangerous, require solid understanding  Sometimes absolute performance matters 3 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers and Arrays • Array is a kind of container, however it‟s less powerful and more dangerous • Pointers are kind of random access iterators for accessing elements of arrays • Pointers and Arrays are the most primitive data structures available in C/C++  Closely connected concepts, inseparable in real world usage 4 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • A pointer is a value representing the address of an object  Every distinct object has a distinct address denoting the place in memory it lives  If it‟s possible to access an object it‟s possible to retrieve its address • For instance: x // if ‘x’ is an object &x // then ‘&x’ is the address of this object p // if ‘p’ is the address of an object p // then ‘p’ is the object itself 5 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • The „&‟ is the address-of operator  Distinct from defining reference types • The „‟ is the dereference operator  Same as for any other iterator as well • If „p‟ contains the address of „x‟ we say that „the pointer p points to x‟ p x • Pointers are built-in data types which need to be initialized in order to be meaningful 6 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • Initialize to zero means „point to no object‟  Null pointer (special value, as no object has this address)  C++11: nullptr • Pointers have types  The address of an object of type T is „pointer to T‟  Written as: T • For instance: int x; // object of type int int p; // pointer to an int, p has type int int p; // pointer to an int, p has type int 7 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • A small (but full) example: int main() int x = 5; // p points to x int p = &x; p x: 5 cout "x = " x endl; // change the value of x through p p x: 6 p = 6; cout "x = " x endl; return 0; 8 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • Think of pointers to be iterators • They point to the single object stored in a „virtual‟ (non- existent) container 9 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arrays • Part of the language rather than standard library  Hold sequence of elements of the same type  Size must be known at compile time  No member functions, no embedded typedefs  i.e. no size_type member, use std::size_t instead • 3 dimensional point: double coords3; // or std::size_t const ndim = 3; double coordsndim; 10 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arrays • Fundamental relationship between arrays and pointers  Name of the array is interpreted as a pointer to its first element: coords = 1.5; // set first element in coords to 1.5 11 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointer Arithmetic • Pointer is a random-access iterator  If „p‟ points to the mth element of an array, then  „p+n‟ points to the (m+n)th element of the array  „p-n‟ points to the (m-n)th element of the array • Further, as first element of array has number „0‟  coords+1 points to the second, and  coords+2 points to the third element  coords+3 points to the first element after the last • Possible to use standard algorithms with arrays: vectordouble v; copy(coords, coords + ndim, back_inserter(v)); 12 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointer Arithmetic • Possible to initialize containers from arrays: vectordouble v(coords, coords + ndim); • More generally, wherever we used v.begin() and v.end(), we can use a and a+n (a: array, n: size) • If „p‟ and „q‟ are pointers  Then p-q is the distance of the two pointers, which is the number of elements in between  Further (p – q) + q == p 13 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Indexing • If „p‟ points to the mth element of an array, then pn is the (m+n)th element, not its address • Consequently, if ‟a‟ is an array, and „n‟ an integer, then an refers to the nth element inside the array „a‟. • More formally, if „p‟ is a pointer, and „n‟ an integer, then pn is equivalent to (p+n) • In C++ indexing is not a property of arrays, but a corollary to the properties of pointers and arrays and the fact that pointers are random access iterators 14 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Array Initialization • Historically, arrays can be initialized easily: int const month_lengths = // we will deal elsewhere with leap years 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ; • No size specified, it‟s automatically calculated • If size is specified, missing elements are set to zero (value- initialized) • C++11 allows the same syntax for containers std::vectorint const month_lengths = // we will deal elsewhere with leap years 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ; 15 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23String Literals Revisited • String literals are character arrays with a trailing zero byte • These are equivalent: char const hello = 'H', 'e', 'l', 'l', 'o', '\0' ; "Hello" • Null character is appended to be able to locate the end of the literal • Library has special functions dealing with „C‟ strings (string literals) 16 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23String Literals Revisited • Find the length of a string literal („C‟ string): strlen // Example implementation of standard-library function size_t strlen(char const p) size_t size = 0; while (p++ = '\0') ++size; return size; • Counting bytes (characters) excluding the null character 17 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23String Literals Revisited • Variable hello and literal “Hello” are equivalent: string s(hello); string s("Hello");  All will construct a string instance „s‟ holding “Hello” • Pointers are iterators: string s(hello, hello + strlen(hello)); 18 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers and References • Think of a reference as an automatically dereferenced pointer  Or as “an alternative name for an object”  A reference must be initialized  The value of a reference cannot be changed after initialization int x = 7; int y = 8; int p = &x; p = 9; p = &y; // ok int& r = x; r = 10; r = &y; // error (and so is all other attempts to // change what r refers to) 19 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arrays of Character Pointers • String literal is convenient way of writing address of first character of a null terminated string • Arrays can be initialized conveniently • Show how to initialize an array of character pointers from sequence of string literals • Grading (again sigh): If the grade is at least 97 94 90 87 84 80 77 74 70 60 0 Then the letter grade is A+ A A- B+ B B- C+ C C- D F 20 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23