Midterm 2 Review

Logistics
	- Bring studentID and writing utensil
		- Preferably ink or dark led
		- PLEASE WRITE LEGIBLY
	- No electronic devices
	- No books
	- No notes

Format
	- Mix of questions
	- Short answer
		- Briefly describe / define / state ...
	- Write code
	- Fill in the blank / complete the table
	- True / False, if false explain why
	- Given code, what is the output ...
	- Similar to midterm 1, expect it to take no more than ~ one hour (maybe sooner).
		- Will cover a broad range of topics, but probably not everything

Topics
	- Will cover everything up to last Wednesday's lecture (2/20)
	- Midterm 2 will be cummulative, but with a heavy emphasis on post-midterm 1 material.

Quadratic Sorting Algorithm
    - InsertionSort was not covered on Midterm 1, but may be covered in Midterm 2.

Hash Table Topics
	- Know basics of hash functions and performance
		- open-address hashing / double-hashing / chained-hashing
		- map vs unordered_map
		- Implementation details

Mergesort / Quicksort
	- Know the algorithm and how to implement it
	- Understand main ideas and how the array is manipulated as the algorithm executes
	- Know the runtime analysis (best / average / worst cases) and space requirements.

Testing
	- Understand main ideas
		- The tddFuncs way of testing
		- Unit testing
		- Test Driven Development (TDD)
		- Various cases of tests
			Normal / Error / Boundary

Inheritance
	- Understand concepts and how to implement them
	- How constructors / destructors of base / sub classes work
	- Understand memory concepts of base and sub class attributes / functions on the stack and the heap
		- Memory / Object slicing
	- Understand inheritance hierarchies and valid / accessible types

Polymorphism
	- What is polymorphism and when you may want to use it
	- How to enable polymorphism
	- Pure virtual functions and abstract classes
	- How it works in memory

Exceptions
	- Try / catch mechanisms
	- Throwing exceptions
	- Exceptions using inheritance

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {

	string s = "abcd";
	cout << s << endl;
	transform(s.begin(), s.end(), s.begin(), ::toupper);
	cout << s << endl;
}
// Output:
// abcd
// ABCD

transform(s.begin() + 2, s.end(), s.begin(), ::toupper);
// Output: 
// abcd
// CDcd

// Our defined function
int multiplyBy100(int x) { return 100 * x; }

// Function to print contents of the vector
void printVector(vector<int> &v) {
	for (int i = 0; i < v.size(); i++) 
		cout << "v[" << i << "] = " << v[i] << endl;
	cout << "---" << endl;
}

int main() {
	vector<int> v;
	for (int i = 10; i <= 15; i++) {
		v.push_back(i);
	}
	printVector(v);
	transform(v.begin(), v.end(), v.begin(), multiplyBy100); // uses our function
	printVector(v);
	return 0;
}

cout << multiplyBy100 << endl; // warning: prints 1 (but does compile correctly)
cout << reinterpret_cast<void*>(multiplyBy100) << endl; // prints an address of where the multiplyBy100 exists in memory

int main() {
	// Pointer to a function that has an int parameter and returns an int.
	int (*someFunctionPointer)(int); 

	// Assign the address of multiplyBy100 to the function pointer.
	someFunctionPointer = multiplyBy100;

	// ERROR!!, trying to assign an int to a function pointer
	// someFunctionPointer = multiplyBy100(10); 

	// Using the function pointer to call a function.
	// Dereferences the pointer as a function, and then passes the parameter
	// 2 to the function.
	cout << (*someFunctionPointer)(2) << endl;

	// syntactically OK to use the function pointer directly without
	// dereferencing it
	cout << someFunctionPointer(2) << endl; // OK

	// ERROR!! Order of operations dereferences after attempting to call the
	// function
	// cout << *someFunctionPointer(2) << endl;
}

template <class T>
void printVector(vector<T> &v) {
	for (int i = 0; i < v.size(); i++) 
		cout << "v[" << i << "] = " << v[i] << endl;
	cout << "---" << endl;
}

template <class T>
bool notEqual(T x, T y) {
	return x != y;
}

template<class T>
vector<T> filterVector(vector<T> v, T value, bool (*filterFunc)(T, T)) {
	vector<T> result;

	for (int i = 0; i < v.size(); i++) {
		if (filterFunc(v[i], value)) {
			result.push_back(v[i]);
		}
	}
	return result;
}

int main() {
	// vector of strings
	vector<string> v1;
	v1.push_back("s1");
	v1.push_back("s2");
	v1.push_back("s3");
	v1.push_back("s2");
	v1.push_back("s1");
	string remove = "s2";
	vector<string> result1 = filterVector(v1, remove, notEqual);
	printVector(result1);

	// vector of ints
	vector<int> v2;
	v2.push_back(1);
	v2.push_back(2);
	v2.push_back(3);
	v2.push_back(2);
	v2.push_back(1);
	vector<int> result2 = filterVector(v2, 1, notEqual);
	printVector(result2);
	return 0;
}