optimizing data structures in high-level programs and a level computing data structures
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
Advise:Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.
