Written by ZHANG Rushan
01. be careful with the 'single quotes' and "double quotes" for char and string; 02. do not forget "break" for switch 03. be careful with the "==" in logics 04. be careful not mistakenly use for(;;); and while(); 05. expressions in for loop should be seperated with ; not , i.e.for(;;) 06. be careful with integer devision 07. check ; 08. forgetting to define variable before use 09. forgetting to return 10. forgetting to initialize 11. char[length + 1] for string (for \0) 12. new int*[] is a pointer int**, not int* 13. deleting dynamic array with delete [] x; 14. the index of the last element of x[N] is x[N-1] 15. you cannot pass a const array to another function requiring non-const array 16. assigning a string to a char array directly: x = "abc" is not allowed, strcpy(a, b) is needed 17. expected ';' after "struct" definition and "enum" definition 18. be careful not to pass by reference a nullptr 19. the "*" and "&" goes with the variable, not the data type! 20. can only assign ptr to const object to ptr to const object 21. use const reference variable for "struct" as default 22. "struct" will not help you initialize automatically 23. always think about recursion 24. forget object_name. for "struct" and "class" 25. forget +1 in recursive count 26. recursive/iterative: try to run the first few cases in heart! 27. add "const" whenever possible
1. always use extra "()" when in doubt, or to improve readability 2. "writing loops" "when writing the loop, consider:" initial situation update for the next loop exit the loop at the right point "try to verify:" The first iteration The second iteration The last iteration 3.use const to replace numbers "convension: set const value name with all upper cases" "more readable" "more easy to update" "type-checked during compilation" 1. const int PI = 3.14159 or 2. #define PI 3.14159 // define is only substituting PI with 3.14159, and it does not have a type
//datatype: how you store data 1."integer, character and character strings" int //integers char //characters 'single quotes' //text, letters special characters: '\t' //tab '\n' //newling '\b' //backspace '\n' //null character string //a sequence of basic char "double quotes" 2."float" float single-precision decimal numbers double double-precision decimal numbers precision floating-point sign-bit + mantissa + exponent exponent+ larger real number mantissa+ higher precision IEEE 754 floating-point standard: 1 sign-bit + 23 (52) mantissa + 8 (11) exponent all float literals will be seen as double to specify a float, you need to add an "f" e.g. 1.23f 3."boolean" every number except 0 is true 0 is false true = 1 false = 0 4."size of datatypes" on 32-bit machine: type size range bool 1 {true, false}; char 1 [-128, 127]; short 2 [-32768, 32767]; int 4 [-2147483648, 2147483647]; long 4 [-2147483648, 2147483647]; float 4 double 8 // you cannot compare two float values with == // the proper way is to do abs(x - y) < epsilon unsigned "not negative, get double maximum" 5."coercion" the automatic conversion of the data type e.g. float + int -> float + float // float has more information char - char -> int - int // integral promotion // it is converted to int, then converted back to char // rules: if either is long double, then it will be converted to long double if either is double, then it will be converted to double if either is float, then it will be converted to double else it will run integral promotion (for the char case) 6."manual type casting" "to change a variable to another type: manual type casting " static_cast<data-type> (variable/value) e.g. int k = 5; float x = static_cast<double>(k); 7."enum" internally: integers act like: const int e.g. enum shapes { TEXT, LINE, RECT, CIRCLE }; // 0, 1, 2, 3 enum bloodtype { A, B, AB = 10, O }; // 0, 1, 10, 11
1."usable characters" numbers //The first character cannot be a digit (0–9). letters (lowercase or uppercase) //C++ is case sensitive underscore _ 2."reserver words" you do not really have to memorise when you use a reserver word, you will get an error right away 3."ways_to_separate_words" capitalize "TwoSeparatedWords" underscore "two_separated_words"
1."principle" named memory location that we can write to, retrieve from, and manipulate 2."terminologies" "definition" allocate memory space for a variable "declaration" declare that a variable exist (often in sepearted compilations) "initialization" assign the initial value for a variable when you "define" a variable: a space is allocated to this variable when you "initialize" a variable: a space is allocated and the value is set when you pass by value: a new space is allocated, with the same value as the previous one when you pass by reference: a new name is created for the same previous memory space "illegal without initialization" const variables reference variable const pointer "pointer to const object okay!" "default initialized to 0" global variable "otherwise, without initialization, garbage data!" 3."lvalue and rvalue" lvalue: the location of the variable read and write rvalue: value in storage read only e.g. (x + 6) = 3; //incorrect LHS: the value of expression (x + 6) //rvalue cout << ++++++x; //correct, print out x + 3 returns a "lvalue" "similar to rbr" cout << x++++++; //incorrect returns an "rvalue" "similar to rbv" reference operation: &x //the location of x 4."constants" literal constants char constants: 'a', '5', '\n' string constants: "hello world" int constants: 123, 456, -89 double constants: 123.456, -2.90E+11 // all float literals will be seen as double symbolic constants must be initialized when definition cannot be changed in most cases, no memory is allocated for constants
1."arithmetic" Assignment + Addition - Subtraction * Multiplication / Division % Modulus "strictly speaking, only defined on positive integers" "a % b = a - (a / b) * b" "If it is negative, it may be different on different compilers" "Only used on integers" "int and float" "Arithmetic expressions involving only integers use integerarithmetic" "Arithmetic expressions involving only floating-point numbersuse floating-point arithmetic" "be careful with integer devision!" 2."increment operators" x++ "post-increment" ++x "pre-increment" adding 1 to x x-- --x subtracting 1 from x "difference between putting it before or putting it after" "++x returns the lvalue of the incremented variable" "x++ returns the rvalue of the original variable" e.g. int x = 3, y; y = x++; //you get x = 4 and y = 3 //this is because adding 1 to x happens after assigning x to y int x = 3, y; y = ++x; //you get x = 4 and y = 4 //this is because adding 1 to x happens before assigning x to y e.g. int x = 3; cout << x++; //you get 3 int x = 3; cout << ++x; //you get 4 3."shorthand assignment" += -= *= /= %= ... 4."relation" == Equal to != Not equal to > < >= <= "the value of =, e.g. x = y, will be the final value of x" "therefore, statements like x = 3 will always be true, since its value is 3" 5."logical" && And || Or ! Negation e.g. !(a > 10) a <= 10 "0 is regarded as false" 6."Precedence" //left-right . -> a++ a-- //right-left *a //dereferencing operator ! //logical not -a //minus ++a --a //left-right * / % //left-right + - //left-right > < >= <= //left-right == != //left-right && //and //left-right || //or //right-left = //assignment
1."statement" statement does not have a value statement is an expression that ends with a semicolumn ";" 2."expression" expression has a value 3."return values of an expression" x = y the final value of x x == y the true value of the statement
1."if-else" if (/* condition */) { /* code */ } else if (/* condition */) { /* code */ } else { /* code */ } //if there is only one line, then the braces "{}" are not necessary "else always belongs to the nearest if" 2."ternary choice" e.g. grade = (percentile >= 85) ? 'A' : ((percentile >= 85) ? 'B' : ((percentile >= 85) ? 'C' : ((percentile >= 85) ? 'D': 'F' ) ) ); or grade = (percentile >= 85) ? 'A' : ((percentile >= 85) ? 'B' : ((percentile >= 85) ? 'C' : ((percentile >= 85) ? 'D' : 'F'))); or grade = (percentile >= 85) ? 'A': (percentile >= 85) ? 'B': (percentile >= 85) ? 'C': (percentile >= 85) ? 'D' : 'F'; 3."switch" switch (expression) { case /* constant-expression */: /* code */ break; case /* constant-expression */: case /* constant-expression */: /* code */ break; default: break; } "case is the entry point" "break is the exit point" "if no break, it will execute till the end of the switch"
1."while loop" while (/* condition */) { /* code */ //this can be empty } "if you do this:" while (x > 0); { /* code */ //this can be empty } // if x > 0, it will get stuck "you can ask for input using:" while (cin >> x) { /* code */ } "when writing the loop, consider:" initial situation update for the next loop exit the loop at the right point "try to verify:" The first iteration The second iteration The last iteration 2."do-while loop" do { /* code */ } while (/* condition */); 3."difference:" while will check the condition before entering the loop do-while will ensure the loop will be executed at least once 4."for l```op" ## for initialization"; "exit condition"; "change of loop variable ```c++ /* code */ } // the "initialization" will be excecuted once before entering the loop sequence: 1."initialization" 2."exit condition" 3./* code */ 4."change of loop variable" 5.back to 2. the "initialization"; "exit condition"; "change of loop variable" can be empty but the semi column ";" should stay "you can even have a for loop in one line:" for (int j = 1; j <= number; factorial *= j++); 5. break; jump out of loop continue; skip one iteration
1."parameter" <formal-parameter-list> "in function definition" a list of variable "declarations" separated by commas <actual-parameter-list> "in function call" a list of "objects" passed to the called function 2."principles" when you call a function: 1. the control flow goes from caller function to the callee function 2. the parameters are passed to the function when to return back to the caller: 1. when it goes to the end of function 2. or when there is a return // only one value can be returned "to return more than one thing" 1. "to return a class" 2. "use array" 3. "use Pass By Reference" 3."passing variables in functions" if no variable is needed, write "void", or nothing for return type, if nothing is returned, write "void" if you want to exit the whole program, write exit() to return something to the system, write exit(/* the thing you want to return */) "PBV: pass by value" only the value is allocated to the function variable "PBR: pass by reference" reference variable: a variable with a "&" symble another name of the previous variable it can refer to an array element "must be initialized when definition" "cannot be rebound" more efficient for larger variable passing const int &x "read only PBR" callee function cannot modify the variable "syntex errors involving PBR" const int &x const variable √ a specific number √ changeable variable √ int &x const variable × a specific number × changeable variable √ "RBV: return by value" int function_name() "RBR: return by reference" int& function_name() // the access right is also passed it is not allowed to do this: int& find_larger(const int &x, const int &y); should be: const int& find_larger(const int &x, const int &y); "the use of global variable is not encouraged" 4."function prototype or interface" "return type" "name" "signature" the input variables and its type 5."declaration and definition" "declaration" "writing down the prototype" "you can only call the functions that is declared before the caller function" "definition" "writing down the prototype" and "the body" "can be defined only once, but declared for many times" "forward declaration" you can declare all the functions at the very top of your code, so that you do not need to check the interference between the functions "it is also possible to declare inside the caller function" 6."overloading" only the signature will be considered i.e. "input variables numbers and type" it will compare all the functions already declared, and determine which one to call i.e. "the one that fits most will be called" a. exact match b. match after type promotion char/bool/short -> int -> long float -> double c. match after standard type conversion integral <-> floating 7."default arguments" "all at the end of the formal parameter list" "can be in function declaration or definition, but not both" e.g. void func(int, float&, char = 'M', bool = true);
1."general rules" "should be of the same type" cannot be reference variable can be pointers the size of array must be set with a constant value e.g. // you cannot do this, but some compiler allow this: int n = 3; double x[n]; // even this is not allowed: int a; const int b; cin >> a; b = a; double x[b]; range: the size of array cannot be set negative you cannot use negative index you cannot use index out of [0, N-1] // even though this may work, this is just your luck! "the index of the last element of x[N] is x[N-1]" array definition int b[5] = {1, 2}; //{1, 2, 0, 0, 0} int c[5] = {}; //{0, 0, 0, 0, 0} int d[] = {1, 2, 3}; //{1, 2, 3} int c[5]; //5 garbage data int e[5] = c; not allowed "once defined, the above syntaxes are no longer allowed:" e = {1, 2, 3}; not allowed f = e; not allowed "you cannot define an array of reference variables:" int &e[3] = {x, y, z}; not allowed "you can define a constant array:" const int x[5] = {1, 2, 3, 4, 5} 2."how does array work?" all elements are located consecutively the location of the array is calculated 3."when you pass an array to a function, it is always done by pass by pointer" to avoid an accident change: use constant array: e.g. int function_name(const int x[]) "you cannot pass a const array to another function requiring non-const array" 4."high-dimensional array" "to improve readability:" int x[5][4] = { {2, 3, 4, 1}, {2, 2, 1, 3}, {2, 4, 1, 3}, {6, 2, 3, 1}, {2, 1, 4, 3}}; "when passing a high-dimensional array to a function, the number of column is necessary" int function_name(int x[][4])
1."initialization" char x[] = "string"; //allowed after initialization "you have to use strcpy to copy a string to another string" when you assign a string to a char array e.g. char x[8] = "abc"; the rest of the array will be initialized as '\0' i.e. x[8] = {'a', 'b', 'c', '\0', '\0', '\0', '\0', '\0'}; 2."principles" for a string of length N, there will be another char '\0' as the (N + 1)th element e.g. "string" == {'s','t','r','i','n','g','\0'}; "Do not forget to prepare an additional space for the '\0'" if the '\0' is forgoten, it will keep printing out garbage data until it meets '\0' "you are not allowed to print out any array except a "char" array" if you have an array of strings it will be a 2-D array e.g. char x[3][6] = { "str_1", "str_2", "str_3" } you are allowed to write: cout << x[2]; 3."getting input" if you get input with char x[20]; cin >> x; "it will keep getting input until it reaches a white space" to get a sentence with white spaces: cin.getline(char_array, max_number_of_char, terminator); "the terminator will be removed" e.g. cin.getline(char_array, 8, '$'); this will get input and store it into str_variable it will stop geting input after pressing "enter" if: your input exceeds "8 - 1 = 7" or your input contains $ else: it will keep getting input even if you pressed "enter" if you do not specify terminator, it will be automatically set to "enter" e.g. cin.getline(char_array, 8);
think recursively
write recursive function
1. validation
2. base cases (e.g. 0)
3. recursive cases
you may call more than one recursive functions
"draw backs compared to iterated solution (e.g. for loop, while loop)"
1. more memory required
2. repeat calculation
1."global scope" "file scope" outside functions "global variables" "when defined, automatically initialized to 0" 2."local scope" "function scope" inside functions "block scope" inside structures e.g. for while if 3."general rule" "all variable exists only after it is defined," "and disappears when it reaches the end of its scope" "all functions also only exists (can be called) after it is declared" the usage of global variable is not recommended we can have two identifiers of the different scope "the inner most is to be called"
1."basic rules" include libraries again define global const variables again // in both main.cpp and other_function.cpp e.g. const int MAX_CALLS = 40; declare global variables with extern // not define // this should be defined in main.cpp // in other_function.cpp e.g. extern bool debug; declare external functions with extern // not define // in both main.cpp and other_function.cpp e.g. extern bool odd(int); 2."header file" basically putting the codes into where it used to be e.g. my_include.h // in both main.cpp and other_function.cpp // system or user defined header files #include <iostream> using namespace std; // constants definitions const int ONE = 1; // external function declaration extern int add(int x); external_variables_declaration.h // in other_function.cpp extern bool debug; external_variables_definition.h // in main.cpp 3."basic model" my_include.h // in both main.cpp and other_function.cpp // user defined datatype // library (other headerfiles, like iostream) // global constant definitions // external function definitions external_variable_declaration.h // in other_function.cpp // global variable declaration external_variable_definition.h // in main.cpp // global variable definition
"defining a new datatype" struct Point { double x; double y; }; "defining a struct variable" Point a = { 24.5, 123.0 }; // can no longer be used after definition Point b; "accessing a struct content" p.x p.y // <struct_variable>.<member_variable> "memberwise copy" // you are allowed to copy two struct directly Point a, b; a.x = 3; a.y = 4; b = a; // b.x = 3; b.y = 4; "even if there is an array in the struct, this is also allowed" "this copy is a bit-to-bit copy" "assignment" // Separate memberwise assignments b.x = 24.5; b.y = 123.0; "for a relatively big struct, you may write a function to do that" or // memberwise copy b = a; "initialization" e.g. struct Date { unsigned int year; unsigned int month; unsigned int day; }; enum Dept { CSE, ECE, MATH }; struct record { char name[32]; unsigned int& id; char gender; Dept dept; Date entry; }; Student a = {"Adam", 2718, 'M', CSE, {2017, 9, 1}} // {char array, int, char, enum, struct} "there is a struct within a struct" "function passing" // it is wise to pass a struct by reference // to avoid accident modification, set it to const "always ask youself: what is the data type? what is the rule for this type?" "we can have an array of structures"
1."basic syntaxes" "you need to specify the type of the pointer you are pointing to" e.g. "int x" // = 20 0x7ffeeb6b9836 // the address of x 0x7ffeeb6b9837 0x7ffeeb6b9838 0x7ffeeb6b9839 "definition: saving the address of x" int *c = &x; // the type is strict "reading the content of that address" "dereferencing operation" jump back! *c; // 20 this is a lvalue, which can be edited "reading the address" c; // 0x7ffeeb6b9836 2."size of pointer" "the size of address" // and therefore all pointers have the same size // exact size is system dependent 3."pointers can point to:" basic types: char short int long float double etc; user defined: struct class etc; another pointer; function; 4."const" int x = 5, y = 10; "const pointer""life long merrage" int* const xcp = &x; // must initialize when definition // during the whole execution, xcp is binded to x; cout << *xcp; // allowed *xcp = 6 // allowed // xcp = &y; wrong!! "pointer to const object" const int* xp_c = &x; // may not initialize when definition // xp_c can point to other variables, but cannot change the value of the variables xp_c = &y; // allowed // *xp_c = 5 wrong! y = 5; // allowed "const pointer to const object" const int* const xcp_c = &x; // must do initialization when defining // xcp_c = &y; wrong! // *xcp_c = 5 wrong! x = 6 // allowed *xcp = 7 // allowed small tip: read from right to left int* "pointer" const "constant" xcp = &x; const "to constant object" int* "pointer" xp_c = &x; const "to constant object" int* "pointer" const "constant" xcp_c = &x; 5."pointer to struct" struct Point { double x; double y; }; Point a; // a contains garbage data Point* ap = &a; "the dereferencing way:" (*ap).x = 3.5; (*ap).y = 9.7; "the -> operator:" ap -> x = 3.5; ap -> y = 9.7; // ap -> x is the same as (*ap).x // always ask yourself: what is the data type? 6."special notice" a."on passing by pointer" if you have a function header with pointer variable, you have to send the address to that function e.g. void print(const int* x) { cout << *x; } // in main: print(&x); // sending the address b."on array" we can create an array of pointers, but not an array of references
1."static object and dynamic object" "static object" (float int ...) usually allocated sequently (inverse) in the stack the allocation and deallocation is done automatically have a fixed size at definition; if out of scope: deallocated "dynamic object" usually allocated sequently (positive) in the heap memory allocation and deallocation at run time always write new, delete in a pair "it will not be deallocated automatically, so it is not restricted by the scope" 2."operator new" "find from heap an amount of memory equal to the size of the datatype and return the address" int* ip = new int; 3."operator delete" "deallocate the memory space the pointer is pointing to" delete ip; // now ip is a dangling pointer ip = nullptr; // if a pointer is not pointing to anyone, just set it to null "*ip now is an unexpected behaviour" 4."common errors" dangling pointer: pointing to a static object which is already out of scope (or anything that is deallocated) memory leak: lose access of some memory address a dynamically allocated memory no longer needed is not released 5."pointer as an array" a dynamic array int *x = new int[1000]; "to delete a dynamic array" delete [] array_name; "don't forget the [] for arrays (when creating and deleting)" pbr = pbv + pointer
1."array vs linked list" array advantage efficient, head to tell, works well with loops and recursion disadvantage size of the array is determined linked list advantage dynamic, it grows and shrinks to any size as you want disadvantage requires additional memory for the linking "pointers" not so "efficient" 2."typical linked lists" head -> value,pointer_to_next -> value,pointer_to_next -> ... -> value,nullptr //tail e.g. struct ll_node { int data; // value ll_node* next; // pointer_to_next }; the "pointer_to_next" for the last node should be nullptr 3."walking ptr" e.g. for (ll_node* p = first_p; p != nullptr; p = p->next) cout << p->data; 4."basic operations" 0.struct struct ll_node { char data; int* next = new ll_node; }; 1.create 2.search use travelsal for (ll_node* p = head; p != nullptr; p = p->next) { /* code */ } 3.delete "for delete, pass by reference (node*& head) is needed" "because you need to set the pointer variable itself to nullptr" "duplicate the pointer first" 4.insert 5."cautions" always think: who remembers the address of the next node? always think: whether a sequence of modifying will lose track of the next node always copy the next pointer first before you modify the last pointer always keep the address of the head node "special case" 1. at first, at last 2. empty "when it is empty, be careful with head->next" 3. only one node when using pass pointer by reference, always ask: what does it reference to?
1."pointer arithmetic" pointer_variable + 1; "pointer_variable_address + 1 * sizeof(type of the variable)" an array name has two role: 1.name of array 2.const pointer pointing to the first element cout << &array_name; //grab addr of the array x, x is the name of the array (role 1) cout << array_name; //print the const pointer, which is the address of the first element cout << &array_name[0]; //access the first element, print out its address "both means the address of the first element" When getting access to the last element of an array, remember to use start+length-1 if you write const char* s1 = "creative"; This is okay. char* s1 = "creative"; Not right. 2."dynamic array" "to create a dynamic array" int *x = new int[<integer expression>]; // can have a length defined by variable "to delete a dynamic array" delete [] array_name; "don't forget the [] for arrays (when creating and deleting)" 3."multi-dimensional array" To create a 2D array: 1. Allocate a 1D array of M int* 2. Allocate a 1D array for each of the element e.g. // to create int** x = new int* [num_rows]; for (int i = 0; i < num_rows; i++) { x[i] = new int[num_lines]; } // to get access *(*(x + j) + k); or x[j][k]; // to delete for (int i = 0; i < num_rows; i++) { delete [] x[i]; } delete [] x; "When an array is dereferenced, the last element is always deleted first"
class = data + operations + access control member functions constructor "create" // done when defining a class object // either by build-in constructor or user-defined constructor accessor "read" // by public functions mutator "write" // by public functions destructor "delete" object: the data; //instantiation //? e.g. class student_record { private: // access control // internal usage char gender; unsigned int id; char name[30]; public: // access control // accessor char get_gender() const { return gender; } "'const' is reminding the compiler: double check: do not change data number!" unsigned int get_id() const { return id; } void print() const { cout << name << endl << id << endl << gender << endl; } // mutator void set(const char my_name[], unsigned int my_id, char my_gender) { strcpy(name, my_name); gender = my_gender; id = my_id;} void copy(const student_record& r) { set(r.name, r.id, r.gender); } // the data is accessible by their own member functions }; // calling member function: student_record amy; amy.set("Amy", 20711102, 'F'); "variables in private can only be accessed through functions in public" "this is to protect the data stored in private area" "information hiding and protection" stop not permitted reading and writing protect data from improper modification "you can just declare functions in class definition" "and place definition in other places" // when defining member functions outside class: student_record::set(const char my_name[], unsigned int my_id, char my_gender) { ... } "the :: is scope operator, restricting the scope of the function" "user-defined constructor" class_name::class_name() {...} // class_name:: not needed if defined in class definition "we can use function overload to define default constructor and explicit constructor" e.g. temperature::temperature() { degree = 0.0; } temperature::temperature(double d, char s) { set(d, s); } // to call explicit constructor: temperature y(10, 'K'); "user-defined destructor" class_name::~class_name() { delete ...; ...} "we can have at most define one destructor" "usually used when you use dynamic memory" "destructor and constructor both do not need data type" constructor function and the destructor can only be called automatically;
1."ADT" abstract data type 2."stack" "LIFO" last in first out top: getting the value of the top push: adding a new item pop: removing from top 3."queue" "FIFO" first in first out front: getting the value of the front enqueue: add to the back dequeue: remove from the front