OOP C1 Introduction

Course Info

Contents

• Introduction to object-oriented programming with a strong software engineering foundation.
• aimed at producing and maintaining large, high-quality software systems.

Buzzwords

encapsulation	封装	inheritance	继承
polymorphism	多态	overriding	改写
interface		cohesion
coupling		collection classes
template		responsibility-driven design

Grading Policy

	Percentage	Notes
In-class quiz	5	学在浙大/ paper work
Assignment	16	one problem set, on PTA.
Lab/Projects	24
Mid-Term Exam	5	90-min at lab period, W9
Final	50

C and C++

Strengths and Weakness of C

Strength	Weakness
Efficient program	Insufficient type checking
Direct access to machine	Poor support for programming-in-the-large
suitable for OS and ES Flexible	Procedure-oriented programming

History of C++

1978

• BS at Cambridge, UK.
• Simulation program in Simula.
• Supports classes, inheritance, and type check Poor performance

1979

BS at AT&T Labs, Cpre, C w/ classes

1980

most C++ features but virtual functions

1983

C++ w/ virtual functions, named C++ by Rick Mascitti 1985 Cfront

1985

“The C++ Programming Language”

1990

ANSI C++ Committee ISO/ANSI Standard C++ in 1998: ISO/IEC 14882

NOTE 所有考试内容均为98标准。

The goal of C++ is to support for object-oriented programming to combine flexibility and efficiency of C.

improvements of C++

C++ builds on C, but support more styles of programming and provides more features.

• Data abstraction
• Access control
• Initialization & cleanup
• References Function
• overloading
• Streams for I/O
• Name control
• Operator overloading
• More safe and powerful memory management
• Templates
• Exception handling

Characters and String

ref Introduction to Programming with C++ Page 142-157.

Characterchar

A character data type represents a single character.

char literal: a single character enclosed in single quotation marks ' '.
string literal: must be enclosed in quotation marks " ". And quotation marks will be paired 1 by 1 in order.
e.g.

cout << "He said "Programming is fun"" << endl;

The statement has a compile error. The compiler thinks the second quotation character is the end of the string and does not know what to do with the rest of the characters.

Escape sequence

Escape Sequence	Name	ASCII Code
\b	Backspace	8
\t	Tab	9
\n	Linefeed	10
\f	Formfeed	12
\r	Carriage Return	13
\\	Backslash	92
\"	Double Quote	34

e.g.

cout << "He said \"Programming is fun\"" << endl;

NOTE

• whitespace characters: The characters ' ', '\t', '\f', '\r' and '\n'.
• \n vs. endl: Both moves the cursor to the next line. However, using endl ensures that the output is displayed immediately on all platform.

Casting

char a = 0XFF41; // The lower 8 bits hex code 41 is assigned to a
char b = 65.25;  // 65 is assigned to variable b 
int c = 'A';     // The ASCII code of character A(65) is assigned to c
int d = '2' + '3';// The ASCII code for '2' is 50 and for '3' is 51 
cout << a << " " << b << " "<< c << " "<< d << endl;
int j = 2 + 'a'; 
cout << j << " is the ASCII code for character " << static_cast<char>(j) << endl;
//display 99 is the ASCII code for character c

Comparing and Testing

Two characters can be compared using the relational operators just like comparing two numbers. This is done by comparing the ASCII codes of the two characters.

Character Functions

C++ provides several functions for testing a character and for converting a character in the <cctype> header file.

Function	Description
isdigit(ch)	Returns true if the specified character is a digit.
isalpha(ch)	Returns true if the specified character is a letter.
isalnum(ch)	Returns true if the specified character is a letter or digit.
islower(ch)	Returns true if the specified character is a lowercase letter.
isupper(ch)	Returns true if the specified character is an uppercase letter.
isspace(ch)	Returns true if the specified character is a whitespace character.
tolower(ch)	Returns the lowercase of the specified character.
toupper(ch)	Returns the uppercase of the specified character.

Stringstring

A string is a sequence of characters. string is a object type,rather a primitive type.

Objects are defined using classes. String is a predefined class in the <string> header file. An object is also known as an instance of a class.

By default, a string is initialized to an empty string(containing no characters) "".但声明空char仍为任意值。

#include<string>
string str;                      //Define variable of string
string str1 = "Hello";           //Initialize with string constant
cin >> str;                      //Read and write string
cout << str;

NOTE cin/cout 和 printf/scanf 是不同的库，有不同的IO缓冲机制。混用可能会造成混乱。同样，new/delete和malloc/free也不可混用。

Concatenation for string

string a = "aa";
string b("bb");
string c = a + b;
cout << c;                    //display aabb

string d = "aa" + "bb";       //incorrect!

It is illegal to concatenate two string literals!

instance functions

Function	Description
length()	Returns the number of characters in this string.
size()	Same as length().
at(index)	Returns the character at the specified index from this string.

NOTE C++ provides the subscript operator for accessing the character at a specified index in a string using the syntax stringName[index]. And the index must be between $0$ and $stringName.length() - 1$.

NOTEThe dot . is an operator that retrieve a member of a struct in C.

• Comparing Strings: alphabetical(ACII) order.

Reading Strings

string city;
//using cin object, input ends with a whitespace character
cin >> city;
//using getline function in <string>
getline(cin,city,'\n'); //or getline(cin,city);

getline(cin, s, delimitCharacter) , stops reading characters when the delimiter character is encountered.

The delimitCharacter is read but not stored into the string s.

The delimitCharacter has a default value '\n'.

The String Class

ref Introduction to Programming with C++ Page 392-398.

• Constructing a String

//first creates a string object using "Hi",then copies the object to s1
string s1 = "Hi"; 
//better way
string s2("Hi");
//create string from C-strings
char s[] = "Hi";
string s3(s);

• appending

  string object	overload functions	Description: all returns a string
  str	.append(string s)	Appends s into this string object str.
  str	.append(string s,int index,int n)	Appends n number of characters in s starting at the position index to str.
  str	.append(string s,int n)	Appends the first n number of characters in s to str.
  str	.append(int n,char ch)	Appends n copies of ch to str.

  string s1("Welcome");
  string s2("Welcome");
  string s3("Welcome");
  string s4("Welcome");
  
  s1.append(" to C plus plus");         //Welcome to C plus plus
  s2.append(" to C plus plus",1,6);     //Welcometo C p
  s3.append(" to C plus plus",5);       //Welcome to C
  s4.append(5,'C');                     //Welcome toCCCCC

• Assigning

  string object	overload functions	Description: all returns a string
  str	.assign(char[] s)	Assigns array of characters or a C-string s to str.
  str	.assign(string s)	Assigns string s to str.
  str	.assign(string s, int index,int n)	Assigns n number of characters in s starting at the position index to str.
  str	.assign(string s, int n)	Assigns the first n number of characters in s to str.
  str	.assign(int n, char ch)	Assigns n copies of ch to str.

  string s1("Welcome");
  string s2("Welcome");
  string s3("Welcome");
  string s4("Welcome");
  
  s1.assign("Hello Dalla");             //Hello Dalla
  s2.assign("Hello Dalla",1,6);         //ello D
  s3.assign("Hello Dalla",5);           //Hello
  s4.assign(5,'C');                     //CCCCC

• Clear, erase, and empty

  string object	overload functions	Description
  str	.clear()	Removes all characters in str, returns a string.
  str	.erase(int index,int n)	Removes n characters from str starting at position index,returns a string.
  str	.empty()	Returns true if str is empty.

  string s1("Welcome"); 
  s1.erase(2, 3)                        //Weme
  s1.clear();                           // s1 is now empty
  cout << s1.empty() << endl;           // true

• length,size,capacity and c_str()

  string object	overload functions	Description
  str	.length()	Returns the number(int) of characters in str.
  str	.size()	same as .length().
  str	.capacity()	Returns the size of the storage allocated for str.
  str	.c_str()	Returns a C-string for str.
  str	.data()	same as .c_str().

• Comparing and Obtaining

  string object	overload functions	Description
  str	.compare(string s)	Returns an integer greater than 0, 0, or less than 0 if str is greater than, equal to, or less than s.
  str	.compare(int index, int n,string s)	Compares strwith substring s(index, …, index + n - 1).
  str	.substr(int index, int n)	Returns a substring of n characters from str starting at position index.
  str	.substr(int index)	Returns a substring of str starting at position index.

  string s1("Welcome"); 
  string s2("Welcomg");
  cout << s1.compare(s2) << endl;           // –1 
  cout << s2.compare(s1) << endl;           // 1
  cout << s1.compare("Welcome") << endl;    // 0
  cout << s1.substr(3, 2) << endl;          //co
  cout << s1.substr(3) << endl;             //come

• Searching

  string object	overload functions	Description: all returns unsigned
  str	.find(char ch)	Returns the position of the first matching character for ch.
  str	.find(char ch,int index)	Returns the position of the first matching character for ch at or from the position index.
  str	.find(string s)	Returns the position of the first matching substring s.
  str	.find(string s,int index)	Returns the position of the first matching substring s starting at or from the position index.

  string s1("Welcome to Cpp");
  cout << s1.find("co") << endl;             //3
  cout << s1.find("co",6) << endl            //string:npos
  cout << s1.find('o') << endl;              //4
  cout << s1.find('o',6) << endl;            //9

  npos is a constant defined in the string class.

• Inserting and Replacing

  string object	overload functions	Description: all returns string
  str	.insert(int index,string s)	Inserts the string s into str at position index.
  str	.insert(int index,int n,char ch)	Inserts the character ch n times into str at position index.
  str	.replace(int index, int n,string s)	Replaces the n characters starting at position index in strwith the string s.

string s1("Welcome to HTML");
string s2("AA");
string s3("Welcome to HTML");
s1.insert(11, "C++ and ");       //Welcome to C++ and HTML
s2.insert(1, 4, 'B');            //ABBBBA
s3.replace(11, 4, "C++");        //Welcome to C++

On most compilers, the capacity is automatically increased to accommodate more characters for the functions append, assign, insert, and replace.

If the capacity is fixed and too small, the function will copy as many characters as possible.

Converting and splitting

from/to	integer	float	string
integer	-	(float)	.itoa(int)
float	(int)	-	using stringstream*
string	atoi(s)	atof(s)	-

*NOTE The stringstream class is in the <sstream> header, providing an interface to manipulate strings as if they were input/output streams. Use stringstream to convert or split by whitespaces.

#include<sstream>
stringstream ss;
ss << 3.1415;
string s = ss.str();

string text("Programming is fun");
stringstream sss(text);
string word;
while(!sss.eof()){
    sss >> word;
    cout << word << endl;
}

Objects with Pointers

ref Introduction to Programming with C++ Page 432-448.

Pointer variables are also known as pointers, which can be used to reference the address of any variable.

A variable’s address: address of the first byte allocated to that variable.

• dereference operator *: access the actual value at a specific memory location.

  The asterisk * can also be used in C++ as a multiplication operator or to declare a pointer variable.

• address operator & (when placed in front of a variable): returns the variable’s address.

A pointer may be initialized to 0, which is a special value to indicate that the pointer points to nothing. In <iostream>, NULL is defined as a constant with value 0.

string s;                                    //s is created and initialized
s = "hello";                                 //hello
string* ps;                                  //ps points to is not known
ps = &s;
cout << *ps << " " << ps -> length();        //same as C

const pointer

A constant pointer points to a constant memory location, but the actual value in the memory location can be changed.

double val = 1.414;
double int = 1.00;
const double* pval = &val;                  //data is constant
double* const pint = ∫                  //the pointer is constant 

Array pointer

A C++ array name is actually a constant pointer to the first element in the array.

In an array, the pointer is incremented or decremented by that integer times the size of the element to which the pointer points.

NOTE

1. *(list + 1) is different from *list + 1. * has precedence over +, so, *list + 1 adds 1 with the value of the first element in the array, while *(list + 1) dereferences the element at address list + 1 in the array,$i.e.$list[1].
2. Pointers can be compared using relational operators ==, !=, <, <=, >, >= to determine their order.

Array function:

C++ provides several functions for manipulating arrays.

functions	arguments	descriptions
min_element,max_element	(elementtype* first, elementtype* last)	return the pointer to the minimal and maximal element in an array.
sort	(elementtype* first, elementtype* last)	sort the array from first to last，acending order by default.
	(elementtype* first, elementtype* last, Compare comp)	sort the array from first to last by given order comp(a function pointer). e.g. equal_to<Type>,not_equal_to<Type>,greater<Type>,greater_equal<Type>、less<Type>,less_equal<Type> in functional.
random_shuffle	(elementtype* first, elementtype* last, RandomNumberGenerator& gen)	gen is the random number generator, rand() by default.
find	(elementtype* first, elementtype* last, const val)	return the pointer to the first found element (stops when find out!). return arr.end()when val is not found.

Internally sort is implemented as Introspective Sorting. Recursive Quick Sort($O(N\log N),O(N^2),O(NlogN)$ for Best Case, Worst Case and Average Case respectively) for large data，and it turns to Insertion Sort($O(N^2)$) when data scales under certain standard. It will turn to Heap Sort($O(N\log N)$) if the depth of recursion is too large.

The comprehensive time complexity is $O(N\log N)$.

Dynamically allocated memory

ref Introduction to Programming with C++ Page 449-453.

The new operator can be used to create persistent memory at runtime for primitive type values, arrays, and objects.

The delete operator for the pointer can be used to explicitly free the memory created by new.

//simple variable
int* p = new int;
int* q = new int(4);
int* arr = new int[*q];
Student *s = new Student(); 
Student *sarr = new Student[10]; 

delete p; 
delete q;
delete[] arr; 
delete s;
delete[] sarr;

//n*m array needs new and delete n loops
int **array2d = new int* [n];
for(int i = 0;i < n;++i) int (*array2d)[i] = new int[m];
for(int i = 0;i < n;++i) delete[] (*array2d)[i];
delete [] array2d;

NOTE 此方法中一维的数组是分开创建的，故整个二维数组的内存不连续，即不能使用array2D[i * width + j]的访问方法，可能会造成访问越界。

NOTE

1. C++ allocates local variables in the stack, but the memory allocated by new is in an area of memory called the freestore or heap. The heap memory(including memory allocated using new) remains available until you explicitly free/delete it or the program terminates.
2. The value of the pointer becomes undefined after the memory pointed by a pointer is freed. Moreover, if some other pointer points to the same memory that was freed, this other pointer is also undefined. Undefined pointers are called dangling pointers.
3. Reassigning a pointer before deleting the memory to which it points causes menmory leak. Every call to new should be matched by a call to delete!
4. Don’t use delete to free memory that new didn’t allocate, but it’s safe to apply delete to the null pointer (nothing happens).