Computer Science Study Notes Help

C++ Programming

Ⅰ C++ Fundamentals

1 C & C++ Introduction

Properties:

  • C/C++ is a compiled language.

  • C/C++ compilers map C/C++ programs into architecture-specific machine code (string of 0s and 1s).

    • Unlike Java, which converts to architecture-independent bytecode (run by JVM => Java Virtual Machine).

    • Unlike Python, which directly interprets the code.

    • Main difference is when your program is mapped to low-level machine instructions, CPU will directly interprets and runs.

Compilation Advantages:

  • Excellent run-time performance:

    Generally much faster than Python or Java for comparable code because it optimizes for the given architecture.

  • Fair compilation time:

    Enhancements in compilation procedure (Makefiles) allow us to recompile only the modified files.

Compilation Disadvantages:

  • Compiled files, including the executable, are arcitecture-specific (CPU type and OS).

    • Executable must be rebuilt on each new system.

    • i.e. "porting your code" to a new architecture.

  • Instead of "Edit -> Run [repeat]" cycle, "Edit -> Compile -> Run [repeat]" iteration cycle can be slow.

Compilation

2 Types and Structs

2.1 Primitive Types

Fundamental Types

Example

Memory

int

int val = 5;

32 bits (usually)

char

char ch = 'F';

8 bits (usually)

float

float decimalVal1 = 5.0;

32 bits (usually)

double

double decimalVal2 = 5.0;

64 bits (usually)

bool

bool bVal = true;

1 bit

std::string

std::string str = "Haven";

Depends on architecture

2.2 Structs

Definition:

Struct: A struct is a group of named variables, each with their own type, that allows programmers to bundle different types together!

Example:

struct Student { string name; // these are called fields string state; // separate these by semicolons int age; }; Student s; s.name = "Haven"; s.state = "AR"; s.age = 22; // use . to access fields
typedef struct { char name[50]; char state[3]; int age; } Student; Student s; strcpy(s.name, "Haven"); strcpy(s.state, "AR"); s.age = 22; // use . to access fields

3 Initialization & References

3.1 Initialization

There are three types of initialization:

  1. Direct Initialization:

    int numOne = 12.0; // numOne = 12, doesn't type check with direct initialization

  2. Uniform Initialization (C++ 11):

    int numTwo {12.0}; // narrowing conversion of '1.2e+1' from 'double' to 'int' // type checks with uniform initialization

  3. Structured binding (C++ 17): Can access multiple values returned by a function.

    #include <iostream> #include <tuple> #include <string> std::tuple<std::string, std::string, std::string> getclassInfo() { std::string className = "CS106L"; std::string buildingName = "Turing Auditorium"; std::string language = "C++"; return {className, buildingName, language}; } int main() { auto [className, buildingName, language] = getclassInfo(); std::cout << "Come to " << buildingName << " and join us for " << className << " to learn " << language << "!" << std::endl; // Output: Come to Turing Auditorium and join us for CS106L to learn C++! return 0; }

Advantages for Uniform Initialization:

  1. It's safe! It doesn't allow for narrowing conversions — which can lead to unexpected behaviour (or critical system failures)

  2. It's ubiquitous! it works for all types like vectors, maps, and custom classes, among other things!

3.2 References

Example:

int x = 5; int& ref = x; // ref is a reference to x ref = 10; // x is now 10

A classic reference-copy bug:

// We are modifying the std::pair's inside of nums void shift(std::vector<std::pair<int, int&gtl> &nums) { // nums passed by reference for (auto [num1, num2] : nums) { // num1 and num2 are copies num1++; num2++; } }
// Correct Way void shift(std::vector<std::pair<int, int>> &nums) { for (auto& [num1, num2] : nums) { num1++; num2++; } }

4 Streams

4.1 Strings

For more information on strings, please visit strings in Java.

Examples in C++:

std::string str = "Hello, World!"; std::cout << str[1] << std::endl; // e str[1] = 'a'; // Hallo, World!

4.2 Stringstreams

  • Constructors with initialtext in the buffer.

  • Can optionally provide "modes" such as ate (start at end) or bin (read as binary).

4.2.1 Output Stringstreams

Examples

std::ostringstream oss("Ito-En Green Tea"); std::cout << oss.str() << std::endl; // Ito-En Green Tea oss << "16.9 Ounces"; std::cout << oss.str() << std::endl; // 16.9 Ouncesn Tea std::ostringstream oss("Ito-En Green Tea", std::ostringstream::ate); oss << "16.9 Ounces"; std::cout << oss.str() << std::endl; // Ito-En Green Tea16.9 Ounces

Positioning Functions:

  1. tellp()

    Returns the current position of the put pointer in the output string stream.

    #include <iostream> #include <sstream> int main() { std::ostringstream oss; oss << "Hello"; std::streampos currentPos = oss.tellp(); std::cout << "Current put pointer position: " << currentPos << std::endl; // Output: 5 oss << " World!"; currentPos = oss.tellp(); std::cout << "New put pointer position: " << currentPos << std::endl; // Output: 12 return 0; }

  2. seekp(pos)

    Moves the put pointer to a specific position within the output string stream.

    The position can be an absolute offset from the beginning of the stream, or a relative offset from the current position (using std::ios::beg, std::ios::cur, or std::ios::end as a second argument).

    #include <iostream> #include <sstream> int main() { std::ostringstream oss; oss << "Hello World!"; // 1. Absolute positioning (from the beginning) oss.seekp(0); // Move to the beginning oss << "Hi"; // Overwrite "Hello" std::cout << oss.str() << std::endl; // Output: Hi World! // 2. Relative positioning (from the end) oss.seekp(-2, std::ios::end); // Move 2 positions back from the end oss << "???"; // Overwrite "d!" std::cout << oss.str() << std::endl; // Output: Hi Worl??? // 3. Using std::ios::beg (from the beginning) oss.seekp(5, std::ios::beg); // Move 5 positions from the beginning oss << "-"; // Insert "-" std::cout << oss.str() << std::endl; // Output: Hi Worl-??? // 4. Using std::ios::cur (from the current position) oss.seekp(2, std::ios::cur); // Move 2 positions forward from the current position oss << "+"; // Insert "+" std::cout << oss.str() << std::endl; // Output: Hi Worl-?+?? return 0; }
4.2.2 Input Stringstreams

Examples

std::istringstream iss("16.9 Ounces"); double amount; std::string unit; iss >> amount >> unit; // amount = 16.9, unit = Ounces std::istringstream iss("16.9 Ounces"); int amount; std::string unit; iss >> amount >> unit; // amount = 16, unit = ".9"

Positioning Functions:

  1. tellg()

    Returns the current position of the get pointer in the input string stream.

    #include <iostream> #include <sstream> int main() { std::istringstream iss("Hello World"); iss >> std::ws; // Skip leading whitespaces std::cout << "Current position: " << iss.tellg() << std::endl; // Output: 0 std::string word; iss >> word; // Read "Hello" std::cout << "Current position after reading 'Hello': " << iss.tellg() << std::endl; // Output: 5 (or 6 if there's a space after Hello) return 0; }

  2. seekg(pos)

    Moves the put pointer to a specific position within the output string stream.

    The position can be an absolute offset from the beginning of the stream, or a relative offset from the current position (using std::ios::beg, std::ios::cur, or std::ios::end as a second argument).

    #include <iostream> #include <sstream> int main() { std::istringstream iss("Hello World"); // Using absolute position from the beginning iss.seekg(7); // Move to the 7th position from the beginning (equivalent to iss.seekg(7, std::ios::beg)) char char1; iss.get(char1); std::cout << "Character read after seeking to absolute position 7: " << char1 << std::endl; // Output: o // Using ios::beg (beginning) iss.seekg(6, std::ios::beg); // Move to the 6th position from the beginning std::string word1; iss >> word1; std::cout << "Word read after seeking from beginning: " << word1 << std::endl; // Output: World // Using ios::cur (current) iss.seekg(2, std::ios::cur); // Move 2 positions forward from the current position (which is after "World") char char2; iss.get(char2); std::cout << "Character read after seeking from current: " << char2 << std::endl; // Output: d // Using ios::end (end) iss.seekg(-5, std::ios::end); // Move 5 positions backward from the end std::string word2; iss >> word2; std::cout << "Word read after seeking from end: " << word2 << std::endl; // Output: World return 0; }
4.2.3 Getline
std::istream& getline(std::istream& is, std::string& str, char delim);

  • is: The input stream from which to read.

  • str: The string where the read line will be stored.

  • delim: The delimiter character that specifies where to stop reading (optional, by default '\n').

Exampless

std::string input; std::cout << "Enter a line of text: "; std::getline(std::cin, input); std::cout << "You entered: " << input << std::endl;
4.2.4 State Bits

  1. Good bit - ready for read /write. (Nothing unusal, on when other bits are off)

  2. Fail bit - previous operation failed, all future operations frozen. (Type mismatch, file can't be opened, seekg failed)

  3. EOF bit - previous operation reached the end of buffer content (reached the end of buffer).

  4. Bad bit - external error, like irrecoverable.(e.g. the file you are reading from suddenly is deleted)

Examples

std::istringstream iss("17"); int amount; iss >> amount; std::cout << (iss.eof() ? "EOF" : "Not EOF") << std::endl; // There also exist iss.good(), iss.fail() & iss.bad()

4.3 Input Streams

There are four standard iostreams

  • cout: Standard Output Stream .

  • cin: Standard Input Stream (buffered).

  • cerr (Standard Error Stream): used to output errors (unbuffered).

  • clog (Standard Logging Stream): used for non-critical event logging (buffered).

cin

  • The program hangs and waits for user input when the position reaches EOF, past the last token in the buffer.

  • The position pointer skips whitespace after the token with each >> operation.

  • The position pointer does the following:

    • consume all whitespaces (spaces, newlines, '\t', '\n', etc .)

    • reads as many characters until:

      • a whitespace is reached, or...

      • for primitives, the maximum number of bytes necessary to form a valid variable.

      • Example: if we extract an int from "86.2", we'll get 86, with pos at the decimal point.

Examples

#include <iostream> #include <string> int main() { double pi, r; std::string name; std::cin >> pi; std::cin.ignore(); // ignore the newline character std::getline(std::cin, name); std::cin >> r; std::cout << "Hello, " << name << "!" << std::endl; std::cout << "Value of pi: " << pi << std::endl; std::cout << "Value of r: " << r << std::endl; return 0; }
#include <iostream> #include <string> int main() { double pi, r; std::string name; std::cin >> pi; std::getline(std::cin, name); // read '\n' from previous input std::getline(std::cin, name); // read name std::cin >> r; std::cout << "Hello, " << name << "!" << std::endl; std::cout << "Value of pi: " << pi << std::endl; std::cout << "Value of r: " << r << std::endl; return 0; }

4.4 Output Streams

cerr & clog

#include <iostream> int main() { std::cerr << "Error: Could not open the file!" << std::endl; std::clog << "Log: User logged in successfully." << std::endl; return 0; }

Input File Streams & Output File Streams

ifstream

ofstream

Purpose

Input from a file

Output to a file

Mode

Opens a file in read mode

Opens a file in write mode

Default behavior

If the file doesn't exist, it fails to open.

If the file doesn't exist, it creates a new one. If it exists, it overwrites the content by default.

Operators

Primarily used with the extraction operator (>>) to read data from the file.

Primarily used with the insertion operator (<<) to write data to the file.

Similarities

  1. They share many common methods like open(), close(), is_open() , good(), bad(), fail(), eof(), etc. for managing the file stream .

  2. Both inherit properties and methods from the base class fstream .

Example:

#include <iostream> #include <fstream> int main() { // ifstream for reading from a file std::ifstream inputFile("myInput.txt"); if (inputFile.is_open()) { std::string line; while (std::getline(inputFile, line)) { std::cout << line << std::endl; } inputFile.close(); } else { std::cerr << "Unable to open input file." << std::endl; } // ofstream for writing to a file std::ofstream outputFile("myOutput.txt"); if (outputFile.is_open()) { outputFile << "This is some text for the output file." << std::endl; outputFile.close(); } else { std::cerr << "Unable to open output file." << std::endl; } return 0; }

5 Modern C++ Types

5.1 Auto

  • When a type name is too long and a simpler alias makes the code more readable, use it.

  • In libraries there is a common name for a type within each class. Example:

    • vector::iterator, map::iterator, string::iterator

    • vector::reference, map::reference, string::reference

5.2 Pair/Tuple

A pair is simply two objects bundled together.

Examples

std::pair<double, int> price(3.4, 5); // make_pair/tuple (C++ 11) automatically deduces the type! auto prices = std::make_pair(3.4, 5); auto values = std::make_tuple(3, 4, "hi"); // access via get/set prices.first = prices.second; // prices = {5, 5} get<0>(values) = get<1>(values); // values = {4, 4, "hi"} // structured binding (C++ 17) - extract each binding auto [a, b] = prices; // a = 5, b = 5 const auto& [c, d, e] = values; // c = 4, d = 4, e = "hi"

5.3 Conversions

Exampless

int v1 = static_cast<double>(3.14); // v1 = 3
const int v3 = 3; int* v4 = const_cast<int*> (&v3); // v4 = 3

5.4 initializer_list

Definition: An initializer list is a lightweight vector that can be used as a parameter.

Example:

#include <iostream> #include <vector> #include <initializer_list> class MyContainer { private: std::vector<int> data; public: // Constructor using initializer_list MyContainer(std::initializer_list<int> values) { // Iterate through the initializer_list and populate the vector for (int value : values) { data.push_back(value); } } void print() const { for (int value : data) { std::cout << value << " "; } std::cout << std::endl; } }; int main() { // Using initializer_list to initialize MyContainer MyContainer container1 = {1, 2, 3, 4, 5}; container1.print(); MyContainer container2{6, 7, 8}; container2.print(); return 0; }
std::vector<int> v1(3, 10) // v1 = {10, 10, 10} std::vector<int> v2{3, 10} // v2 = {3, 10}

5.5 using

Create type aliases with the using keyword.

std::pair<bool, std::pair<double, double>>;
using Zeros = std::pair<double, double>; using Solution = std::pair<bool, Zeros>;

Ⅱ Standard Template Library (STL)

The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators.

The C++ Standard Library is a collection of classes and functions, which are written in the core language and part of the C++ ISO Standard itself.

6 Containers

6.1 Sequence Containers

Sequence Containers: Containers which provide access to a linear sequence of elements.

  • std::vector<T>

  • std::deque<T>

  • std::array<T>

  • std::list<T>

  • std::forward_list<T>

6.1.1 Vector

Vector: An array with changeable size.

Example

#include <iostream> #include <vector> int main() { std::vector<int> vec; // Create an empty vector std::vector<int> vec2(5); // Create a vector with 5 copies of 0 std::vector<int> vec3{5, 1}; // Create a vector with 5 copies of value 1 vec.push_back(1); // Add 1 to the end of the vector vec.clear(); // Clear vector if (vec.empty()) { // Check if vector is empty std::cout << "Vector is empty" << std::endl; } int k = vec2[0]; // Get the element of index 0 int l = vec2.at(0); // Get the element of index 0 vec2.at(0) = 2; // Replace the element at index 0 vec2[0] = 2; // Replace the element at index 0 return 0; }

vec[index]

vec.at(index)

Bounds Checking

No

Yes

Speed

Fast

Slow

Advantages:

  • Fast, lightweight & intuitive.

  • Grow efficiently in one direction.

Disadvantages:

  • cannot push_front!

6.1.2 Deque

Deque: A deque is a doubly ended queue.

Implementation

Instead of storing all elements in a single contiguous block, deque internally manages a collection of fixed-size arrays called "chunks" or "buffers." => separate subarrays and allocated independently

Deque maintains a dynamic array (usually a small array or a tree-like structure) called a "map" or "central index". This map stores pointers to the beginning of each chunk.

Advantages:

  • Can push_front!

Disadvantages:

  • For other operations, vector outperform deque.

6.2 Container Adapters

  1. Stacks:

    • The standard containers std::vector, std::deque, std::list satisfy these requirements.

    • Just limit the functionality of a vector/deque to only allow push_back and pop_back.

  2. Queues:

    • The standard containers std::deque and std::list satisfy these requirements.

    • Just limit the functionality of a deque to only allow push_back and pop_front.

6.3 Associative Containers

Associative containers: Data is accessed using the key instead of index.

Class TemplatesBased on ordering property of keysKeys need to be comparable using < operatorstd::map<T1, T2>std::set<T>Based on hash functionYou need to define how the key can be hashedstd::unordered_map<T1, T2>std::unordered_set<T>

6.4 Iterators

Four iterator operations:

  • Create iterator:

    std::set<int>::iterator iter = mySet.begin()

  • Dereference iterator to read value currently pointed to:

    int val = *iter

  • Advance iterator:

    iter++; or ++iter

  • Compare against another iterator (especially .end() iterator)

Map Iterators:

std::map<int, int> m; std::map<int, int>::iterator i = m.begin(); std::map<int, int>::iterator end = m.end(); while (i != end) { std::cout << (*i).first << " " << (*i).second << std::endl; i++; }

Random_Access

Bidirectional

Forward

Input

Output

6.4.1 Input Iterators

For sequential, single-pass input.

Read only, i.e. can only be dereferenced on right side of expression.

Example:

vector<int>::iterator iter = myVector.begin(); int val = *iter;
6.4.2 Output Iterators

For sequential, single-pass output.

Read only, i.e. can only be dereferenced on left side of expression.

Example:

vector<int>::iterator iter = myVector.begin(); *iter = 5;
6.4.3 Forward Iterators

Combines input and output, plus can make multiple passes.

Can read from and write to (if not const iterator).

Example:

// multiple passes vector<int>::iterator iter1 = myVector.begin(); vector<int>::iterator iter2 = myVector.begin(); iter1++; iter2++; if (iter1 == iter2) { cout << "Equal" << endl; } // Equal
6.4.4 Bidirectional Iterators

Same as forward iterators, plus can go backwards with the decrement operator (--).

Use cases: std::map, std::set, std::list

6.4.5 Random Access Iterators

Same as bidirectional iterators, plus can be implemented or decremented by arbitrary amounts using + and -.

Use cases: std::vector, std::deque, std::string

7 Templates

We can use templates to keep the logic, but change the type!

7.1 Template Functions

Example

template <typename T> std::pair<T, T> my_minmax(T a, T b) { if (a < b) return {a, b}; else return {b, a}; }

The following code:

my_minmax(cout, cout);

Semantic error: you can't call operator < on two streams.

Conceptual error: you can't find the min or max of two streams.

The compiler deduces the types and literally replaces the types. Compiler will produce semantic errors, not conceptual error.

template <typename Collection, typename DataType> int countOccurences(const Collection& list, DataType val) { int count = 0; for (size_t i = 0; i < list.size(); ++i) { if (list[i] == val) ++count; } return count; }

Problem lies in indexing list[i].

template <typename Collection, typename DataType> int countOccurences(const Collection& list, DataType val) { int count = 0; for (auto iter = list.begin(); iter != list.end(); ++iter) { if (*iter == val) ++count; } return count; }

Or:

template <typename Collection, typename DataType> int countOccurences(const Collection& collection, const DataType& val) { int count = 0; for (const auto& element : collection) { if (element == val) { ++count; } } return count; }

7.2 Template Classes

Template Class

  1. Add template declaration for class

  2. Add all the member type aliases

  3. Add the template declaration to every single class member

  4. Move everything to the .h file => separate compilation template classes are not classes themselves

8 Functions and Algorithms

8.1 Lambda Functions

auto isLessThanLimit = [limit](auto val) -> bool { return val < limit; };

  • auto: We don't know the type, ask compiler.

  • [limit]: Capture clause, gives access to outside variables.

  • (auto): Parameter list, can use auto!

  • -> bool: Return type, optional.

Two types of capture clause: By reference or by value.

// capture all by value, except teas is by reference auto func1 = [=, &teas](parameters) -> return-value { // body }; // capture all by reference, except banned is by value auto func2 = [&, banned](parameters) -> return-value { // body };

std::bind adapts existing function objects to create new ones with specific argument values pre-filled.

int multiplyAndAdd(int a, int b, int c) { return (a * b) + c; } int main() { auto operation = std::bind(multiplyAndAdd, std::placeholders::_1, std::placeholders::_2, 4); std::cout << operation(2, 3) << std::endl; // Output: 10 ((2*3) + 4) }

  • std::placeholders::_1 means "take the first argument passed to operation".

  • std::placeholders::_2 means "take the second argument passed to operation".

  • 4 is the third argument of multiplyAndAdd.

8.2 Algorithms

8.2.1 std::sort

Syntax:

#include <algorithm> // Required header // 1. Basic Usage (Sorting using < operator) template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); // 2. Custom Comparison Function template <class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Example:

std::vector<int> numbers = {3, 1, 4, 1, 5}; std::sort(numbers.begin(), numbers.end()); // Sort the entire vector std::sort(numbers.begin(), numbers.end(), std::greater<int>()); // Sort in descending order

Parameters:

  1. first (iterator): An iterator pointing to the beginning of the range you want to sort.

  2. last (iterator): An iterator pointing to one position past the end of the range to be sorted.

  3. comp (comparison function) (optional): A binary function (takes two arguments) that defines the sorting criterion. It should return true if the first argument should come before the second in the sorted order, and false otherwise.

Important notes:

  • You can sort a portion of the entire vector, array, etc.

    std::vector<int> data = {5, 2, 8, 1, 9, 3}; std::sort(data.begin(), data.begin() + 4); // Result: data = {1, 2, 5, 8, 9, 3}

  • You can overload operator < to define default sorting behavior.

    struct Item { int id; std::string name; }; // Stable Comparison bool compareByNameStable(const Item& a, const Item& b) { if (a.name == b.name) { return a.id < b.id; // Keep original order based on 'id' if names are equal } return a.name < b.name; } int main() { std::vector<Item> items = { {1, "Apple"}, {2, "Banana"}, {3, "Apple"} }; std::sort(items.begin(), items.end(), compareByNameStable); }

  • Average case:

8.2.2 std::nth_element

Syntax:

#include <algorithm> template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); // Optional: You can provide a custom comparison function template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

Example:

std::vector<int> numbers = {5, 2, 8, 1, 9, 3}; std::nth_element(numbers.begin(), numbers.begin() + 2, numbers.end()); // Output: 2 1 3 8 9 5 (The element at index 2 is now '3', // which is the 3rd smallest, but the rest are not sorted)

Parameters:

  1. first: Iterator to the beginning of the range.

  2. nth: Iterator pointing to the position you want the nth element to be placed in.

  3. last: Iterator to one past the end of the range.

  4. comp (optional): A binary comparison function, similar to std::sort.

Important notes:

  • With this, you can efficiently find the median of a dataset without fully sorting it, or determine the smallest or largest element.

  • It sorts so element is in correct position, and all elements smaller to left, larger to right, but the elements before the element are not guaranteed to be sorted among themselves, and neither are the elements after it.

  • Average case:

8.2.3 std::stable_partition

Syntax:

#include <algorithm> // Required header template <class BidirectionalIterator, class UnaryPredicate> BidirectionalIterator stable_partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);

Parameters:

  1. BidirectionalIterator: A template parameter indicating the type of iterators used. These iterators must support bidirectional movement (like those from std::list, std::vector, std::deque).

  2. first (BidirectionalIterator): An iterator to the beginning of the range you want to partition.

  3. last (BidirectionalIterator): An iterator to one past the end of the range to be partitioned.

  4. UnaryPredicate: A template parameter representing the type of the predicate function.

  5. pred (UnaryPredicate): A function that takes a single argument (an element from the range) and returns a bool:

    • true: The element satisfies the partitioning criterion.

    • false: The element does not satisfy the criterion.

Example:

#include <iostream> #include <vector> #include <algorithm> #include <string> // A simple struct to represent a course (you can customize this) struct Course { std::string name; }; int main() { // Sample course data std::vector<Course> courses = { {"CS101"}, {"MATH101"}, {"CS202"}, {"PHYS101"}, {"CS301"} }; std::string dep = "CS"; // Lambda function to check if a course belongs to the "CS" department auto isDep = [dep](const Course& course) { return course.name.size() >= dep.size() && course.name.substr(0, dep.size()) == dep; }; // Partition the courses vector, keeping "CS" courses at the beginning auto iter = std::stable_partition(courses.begin(), courses.end(), isDep); // Remove non-"CS" courses courses.erase(iter, courses.end()); // Output the remaining "CS" courses std::cout << "CS Courses:\n"; for (const Course& course : courses) { std::cout << course.name << std::endl; } return 0; }
8.2.4 std::copy_if

Syntax:

#include <algorithm> // Required header template <class InputIterator, class OutputIterator, class UnaryPredicate> OutputIterator copy_if (InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred);

  1. InputIterator: Type of iterator used for the input range.

  2. OutputIterator: Type of iterator used for the output range (where copied elements go).

  3. first (InputIterator): An iterator to the beginning of the input range.

  4. last (InputIterator): An iterator to one past the end of the input range.

  5. result (OutputIterator): An iterator to the beginning of the output range.

  6. UnaryPredicate: Type of the predicate function.

  7. pred (UnaryPredicate): A function that takes a single argument (an element from the input range) and returns:

    • true: Copy the element to the output range.

    • false: Skip the element.

Example:

#include <iostream> #include <vector> #include <algorithm> #include <string> struct Course { std::string name; }; int main() { std::vector<Course> csCourses = { {"CS101"}, {"MATH101"}, {"CS202"}, {"PHYS101"}, {"CS301"} }; std::vector<Course> filteredCourses; std::string dep = "CS"; auto isDep = [dep](const Course& course) { return course.name.size() >= dep.size() && course.name.substr(0, dep.size()) == dep; }; // Copy matching courses to 'filteredCourses' // Use back_inserter to add more space! std::copy_if(csCourses.begin(), csCourses.end(), std::back_inserter(filteredCourses), isDep); std::cout << "Filtered CS Courses:\n"; for (const Course& course : filteredCourses) { std::cout << course.name << std::endl; } return 0; }
8.2.5 std::remove_if

Syntax:

#include <algorithm> // Required header template <class ForwardIterator, class UnaryPredicate> ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred);

  1. ForwardIterator: Type of iterator used for the range. Must support forward movement.

  2. first (ForwardIterator): An iterator to the beginning of the range.

  3. last (ForwardIterator): An iterator to one past the end of the range.

  4. UnaryPredicate: Type of the predicate function.

  5. pred (UnaryPredicate): A function that takes a single argument (an element from the range) and returns:

    • true: The element should be "removed."

    • false: The element should be kept.

Ⅲ Object-Oriented Programming

9 Classes and Consts

9.1 Classes

Definitions:

  • Class: a template for a new type of objects, defines how objects of a particular type behave.

  • Object: Entity that combines state and behavior, instance of a class.

  • Member variables (instance variables, fields): Define state inside each object.

  • Member functions (methods): Define behavior inside each object.

  • Constructor: Initializes the state of newly created objects.

  • Destructor: Called when the object is deleted by the program.

    • Delete any pointers stored as private members.

    • delete[] any arrays stored as private members.

  • Client code: Code that uses the objects defind.

  • Encapsulation: Hiding implementation details from the client code.

C++ separates classes into two kinds of files:

  • Header File (.h, .hh, .hpp): Containing the interface (declarations).

  • Source File (.cpp, .cc, .cxx, .c++, .C): Containing definitions (method bodies).

Classes have three main parts:

  • Constructor and destructor

  • Member variables

  • Member functions

Example (header file):

// Protection in case multiple .cpp files include this header, so // that its contents won't get declared twice. #ifndef MYCLASS_H #define MYCLASS_H class MyClass { public: MyClass(); // Constructor ~MyClass(); // Destructor void myMethod(); // Member function (behavior inside each function) int getMyVariable(); private: int myVariable; // Member variable (data inside each object) }; // Semicolons! #endif // MYCLASS_H

Example (source file):

#include "MyClass.h" MyClass::MyClass() { myVariable = 0; // Initialize member variable } void MyClass::myMethod() { myVariable++; } MyClass::~MyClass() { // Simple destructor implementation } int MyClass::getMyVariable() { return myVariable; }

9.2 Consts

Consts: A qualifier for objects that declares they cannot be modified.

Consts help us find bugs, and allow us to reason about whether a variable will be changed.

Within a function that takes a const parameter, you cannot call non-const member functions (if the parameter is an object) or modify the value (if it's a fundamental type or a pointer to const data) of that parameter.

Example for value:

int plus(const int& x) { return x + 1; // Error: x is const } int plus(const int x) { return x + 1; // OK: x is a copy }

Example for member functions:

struct Planet { int countPopulation() const; void deathStar(); }; int Planet::countPopulation() const { return 42; } void Planet::deathStar() { std::cout << "BOOM" << std::endl; } void evil(const Planet &p) { // OK: countPopulation is const std::cout << p.countPopulation() << std::endl; // ERROR: deathStar isn't const p.deathStar(); }
9.2.1 Const Pointers
// constant pointer to a non-constant int // (*p)++; OK! // p++; NOT allowed! int * const p; // non-constant pointer to a constant int const int* p; int const* p; // constant pointer to a constant int const int* const p; int const* const p;
9.2.2 Const Iterators
const vector<int>::iterator itr = v.begin(); *itr = 5; // OK! changing what itr points to ++itr; // ERROR! can’t modify itr vector<int>::const_iterator itr = v.begin(); *itr = 5; //ERROR! can’t change value of itr ++itr; //OK! changing v int value = *itr; //OK! reading from itr

10 Operators

10.1 Basic Operators

There are 40 (+4) operators you can overload!

Operators

Examples for default operators behaviors:

std::vector<std::string> v{"Hello", "World"}; std::cout << v[0]; v[1] += "!";
std::vector<std::string> v{"Hello", "World"}; std::cout.operator << (v.operator[](0).c_str()); v.operator[](1).operator += ("!");

In STL,

ostream& operator<<(ostream& s, const string& val) { ... } string& vector<string>::operator[](size_t index) const { ... }

10.2 Operator Overloading

General rule of Thumb: (Member & Non-Member)

  1. Some operators must be implemented as members (e.g., [], (), ->, =) due to C++ semantics.

  2. Some must be implemented as non-members (eg. <<, if you are writing class for rhs, not lhs).

  3. If unary operator (eg. ++), implement as member.

  4. If binary operator and treats both operands equally (eg. both unchanged) implement as non-member (maybe friend). Examples: +, < .

  5. If binary operator and not both equally (changes lhs), implement as member (allows easy access to lhs private members). Examples: +=

Examples

Member Function:

#include <iostream> class MyClass { private: int data[10]; public: // Subscript operator ([]) int& operator[](int index) { return data[index]; } // Function call operator () int operator()(int a, int b) { return data[a] + data[b]; } // Assignment operator (=) MyClass& operator=(const MyClass& other) { if (this != &other) { // Avoid self-assignment for (int i = 0; i < 10; ++i) { data[i] = other.data[i]; } } return *this; } }; int main() { MyClass obj; obj[2] = 5; // Using the subscript operator obj[3] = 10; // Using the subscript operator int sum = obj(2, 3); // Using the function call operator std::cout << "Sum: " << sum << std::endl; MyClass obj2; obj2 = obj; // Using the assignment operator return 0; }

Non-Member Function:

#include <iostream> class Point { private: int x, y; public: Point(int xVal, int yVal) : x(xVal), y(yVal) {} // Friend declaration for the output stream operator friend std::ostream& operator<<(std::ostream& out, const Point& p); }; // Non-member output stream operator (<<) std::ostream& operator<<(std::ostream& out, const Point& p) { out << "(" << p.x << ", " << p.y << ")"; return out; } }; int main() { Point p(5, 10); std::cout << "Point coordinates: " << p << std::endl; // Using the overloaded << return 0; }

10.3 Principle of Least Astonishment (POLA)

From the C++ Core Guidelines (section C ):

  • Design operators primarily to mimic conventional usage.

  • Use nonmember functions for symmetric operators.

  • Use nonmember functions for symmetric operators.

    • Compound operators return reference to *this

    • Arithmetic operators return copies

    • In/decrement prefix vs. postfix rules

    • Indexing requires const and non-const versions

    • Look at the C++ reference for common patterns!

  • Always provide all out of a set of related operators.

10.4 Interesting Operators

Advanced Multithreading Support (C++ 20) :

awaiter operator co_await() const noexcept { return awaiter{ *this }; }

Spaceship operator (C++20):

std::strong_ordering operator<=> (const Time& rhs) { return hour <=> rhs.hour; }

11 Special Member Functions

Six types of special member functions:

Every class has them by default.

These functions are generated only when they're called (and before any are explicitly defined by you):

  • Default constructor: Takes no parameters and creates a new object.

  • Destructor: Called when an object goes out of scope.

  • Copy constructor: Creates a new object as a member-wise copy of another.

  • Copy assignment operator: Assigns an already existing object to another.

  • Move constructor

  • Move assignment operator

Example:

MyVector<int> function(MyVector<int> vec0) { // copy constructor MyVector<int> vec1; // default constructor MyVector<int> vec2{3, 4, 5}; // initializer list constructor MyVector<int> vec3(); // function declaration - C++’s most vexing parse MyVector<int> vec4(vec2); // copy constructor MyVector<int> vec5{}; // default constructor MyVector<int> vec6{vec3 + vec4}; // move constructor MyVector<int> vec7 = vec4; // copy constructor vec7 = vec2; // copy assignment operator return vec7; // move constructor

11.1 Copy Constructor & Copy Assignment Operator

By default, the copy constructor will create copies of each member variable.

Examples

/** Problem with the following code: * When the vectors go out of scope, their destructor tries to free the array. */ IntVector operator+(const IntVector & vec, int elem) { IntVector copy = vec; // default copy constructor, copy a pointer to the same array copy += element; return copy; }
Copy Constructor

Copy constructor:

  • Use initializer list to copy members where assignment does the correct thing. e.g., int, other objects, etc.

  • Deep copy all members where assignment does not work. e.g., pointers to heap memory.

Copy assignment operator:

  • Clean up any resources in the existing object about to be overwritten.

  • Copy members using initializer list when assignment works.

  • Deep copy members where assignment does not work.

11.2 Delete Operations

Setting a special member function to delete removes its functionality.

We can also keep the default copy constructor if we declare other constructors.

Examples

#include <iostream> class NonCopyable { public: NonCopyable() = default; // Default constructor NonCopyable(const NonCopyable&) = delete; // Delete copy constructor NonCopyable& operator=(const NonCopyable&) = delete; // Delete copy assignment NonCopyable(NonCopyable&&) = default; // Default move constructor NonCopyable& operator=(NonCopyable&&) = default; // Default move assignment void print() { std::cout << "NonCopyable object" << std::endl; } }; int main() { NonCopyable obj1; obj1.print(); NonCopyable obj2 = std::move(obj1); // Move construction is allowed obj2.print(); // NonCopyable obj3 = obj2; // Error: Copy construction is deleted // obj1 = obj2; // Error: Copy assignment is deleted return 0; }

11.3 Rule of Zero/Three

Rule of Zero: If the default operations work, don't define your own custom ones!

When the default one generated by the compiler does not work, you need to write your own special member functions.

Most common reason: ownership issues. A member is a handle on a resource outside of the class (e.g., pointers, mutexes, filestreams) .

Rule of Three: If you explicitly define (or delete) a copy constructor, copy assignment, or destructor, you should define (or delete) all three.

11.4 Copy Elision and Return Value Optimization (RVO)

Examples

int main() { StringVector words; words = findAllWords(“words.txt”); // print words } StringVector findAllWords(const string& filename) { StringVector words; // read from filename using an ifstream return words; }
RVO

12 Move Semantics

12.1 lvalues & rvalues

Definitions

  • lvalue: An l-value is an expression that has a name (identity).

  • rvalue: An r-value is an expression that does not have a name (identity).

l-value

r-value

Find address using address-of operator (&var)

Yes

No

Intuitive Definition

Can appear either left or right of an assignment *

Can appear only on the right of an assignment *

Lifetime

Decided by scope

Ends on the very next line (unless you purposely extend it!)

Value References

An l-value reference can bind to an l-value.

auto& ptr2 = (ptr += 3);

An r-value reference can bind to an r-value.

auto&& v4 = v1 + v2;

A const l-value reference can bind to either l or r-value.

const auto& ptr2 = (ptr += 3); const auto& v4 = v1 + v2;

Examples

int val = 2; // val: lvalue, 2: rvalue int* ptr = &val; // ptr: lvalue, &val: rvalue std::vector<int> v1{1, 2, 3}; // v1: lvalue, {1, 2, 3}: rvalue auto v4 = v1 + v2; // v4: lvalue, v1 + v2: rvalue => + returns a copy to a temporary size_t size = v1.size(); // size: lvalue, v1.size(): rvalue val = static_cast<int>(size); // val: lvalue, static_cast<int>(size): rvalue // cast returns a copy of size
Value References

12.2 Move Semantics

13 Inheritance

13.1 Namespace

Namespace: Namespace is an abstract container or environment created to hold a logical grouping of unique identifiers or symbols (i.e. names).

Goal: To resolve identifier clash. The same identifier can be independently defined in multiple namespaces. That is, an identifier defined in one namespace may or may not have the same meaning as the same identifier defined in another namespace.

Most modern languages use namespaces to fix this.

#include <iostream> #include <vector> int main() { std::vector<int> v = {1, 2, 3}; // std:: is namespace for (int i : v) { std::cout << i << std::endl; } return 0; }
import numpy as np a = np.array([1, 2, 3]) // np. is namespace
import java.util.ArrayList; // Java packages before identifier public class Main { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); for (int i : list) { System.out.println(i); } } }
const fs = require('fs'); const data = fs.readFileSync('file.txt', 'utf8'); // fs. is namespace

13.1 Overriding and Overloading

Definition:

  • Overloading: Methods with the same name but different signature.

  • Overriding: A subclass to provide a specific implementation of a method that is already provided by its parent class or interface.

// part of code from Quicksort public static void sort(Comparable[] a) { sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); sort(a, lo, j - 1); sort(a, j + 1, hi); }
class Shape { public void calculateArea(int side) { System.out.println("Area of a square: " + (side * side)); } } class Rectangle extends Shape { public void calculateArea(int length, int width) { System.out.println("Area of a rectangle: " + (length * width)); } } public class Main { public static void main(String[] args) { Rectangle myRectangle = new Rectangle(); myRectangle.calculateArea(5); // Calls Shape's calculateArea (inherited) myRectangle.calculateArea(4, 6); // Calls Rectangle's calculateArea (overloaded) } }
interface Animal { void makeSound(); // Abstract method declaration } class Dog implements Animal { // Implementing the interface @Override public void makeSound() { System.out.println("Woof!"); } } class Cat implements Animal { // Implementing the interface @Override public void makeSound() { System.out.println("Meow!"); } } public class Main { public static void main(String[] args) { Animal myDog = new Dog(); Animal myCat = new Cat(); myDog.makeSound(); // Output: Woof! myCat.makeSound(); // Output: Meow! } }

13.2 Types of Inheritance

Interface Inheritance:

Specifying the capabilities of a subclass.

  • Interface: The list of all method signatures.

  • Specifies what the subclass can do, but not how.

Examples

#ifndef SHAPE_H #define SHAPE_H class Shape { public: virtual void draw() const = 0; // Pure virtual function virtual ~Shape() = default; // Virtual destructor }; #endif //SHAPE_H
#ifndef CIRCLE_H #define CIRCLE_H #include "Shape.h" #include <iostream> class Circle final : public Shape { public: void draw() const override { std::cout << "Drawing Circle" << std::endl; } }; #endif //CIRCLE_H
#ifndef SQUARE_H #define SQUARE_H #include "Shape.h" #include <iostream> class Square final : public Shape { public: void draw() const override { std::cout << "Drawing Square" << std::endl; } }; #endif //SQUARE_H
public interface Shape { double getArea(); double getPerimeter(); String toString(); }
public class Circle implements Shape { private final double radius; public Circle(double radius) { this.radius = radius; } public double getArea() { return Math.PI * radius * radius; } public double getPerimeter() { return 2 * Math.PI * radius; } public String toString() { return "Circle with radius " + radius; } }

Implementation Inheritance: Subclasses can inherit signatures AND implementation.

Examples

#ifndef ANIMAL_H #define ANIMAL_H #include <iostream> class Animal { public: virtual void makeSound() const { std::cout << "Generic animal sound" << std::endl; } virtual ~Animal() = default; }; #endif //ANIMAL_H
#ifndef DOG_H #define DOG_H #include "Animal.h" #include <iostream> class Dog final : public Animal { public: void makeSound() const override { std::cout << "Bark" << std::endl; } }; #endif //DOG_H
interface Animal { default void makeSound() { System.out.println("Generic animal sound"); } void eat(); } class Dog implements Animal { @Override public void eat() { System.out.println("Dog is eating"); } } class Cat implements Animal { @Override public void eat() { System.out.println("Cat is eating"); } @Override public void makeSound() { System.out.println("Meow!"); } } public class Main { public static void main(String[] args) { Dog myDog = new Dog(); Cat myCat = new Cat(); myDog.makeSound(); // Output: Generic animal sound (using default) myDog.eat(); // Output: Dog is eating myCat.makeSound(); // Output: Meow! (overridden) myCat.eat(); // Output: Cat is eating } }

Ⅳ Modern C++

14 RAII

Last modified: 25 November 2024
Artificial IntelligenceComputer Architecture