Midterm Review Flashcards
Crush that shit
what are npos and endpos and how can you use them
- npos: Represents a not found result and is a special constant value (typically -1).
- End Position: Refers to the index after the last character in the string (str.size()), used when iterating or accessing string content.
std::string str = “hello”;
if (str.find(“x”) == std::string::npos) {
std::cout «_space;“Substring not found” «_space;std::endl;
}
- End Position: Refers to the index after the last character in the string (str.size()), used when iterating or accessing string content.
Array
Access: array[index]
* Important Functions:
* None (Arrays do not have dynamic methods like vectors)
* Other Ideas: Fixed size, cannot resize once declared
* Big O:
* Access: O(1)
* Insertion/Deletion: O(n) (shifting required)
Vector
Access: vector[index]
* Important Functions:
* push_back(value): Adds value to the end
* pop_back(): Removes last element
* insert(iterator, value): Inserts value at the position specified by the iterator (e.g., vec.insert(vec.begin(), value) to insert at the front)
* size(): Returns the number of elements
* empty()
* resize(newSize): Resizes the vector
* Other Ideas: Dynamic resizing, random access
* Big O:
* Access: O(1)
* Insertion at end: O(1) (amortized)
* Insertion/Deletion in middle/front: O(n) (requires shifting)
* Size: O(1)
* can’t use [] without adding elements first
* accessed like
stack
- Access: Only the top element
- Important Functions:
- push(value): Adds value to the top
- pop(): Removes top element
- top(): Returns the top element
- size(): Returns the number of elements
- empty(): Checks if stack is empty
- Other Ideas: LIFO structure
- Big O:
- Push: O(1)
- Pop: O(1)
- Access top: O(1)
- Size: O(1)
queue
Queue (FIFO - First In, First Out)
* Access: Only the front and back elements * Important Functions: * push(value): Adds value to the back * pop(): Removes front element * front(): Returns the front element * back(): Returns the back element * size(): Returns the number of elements * empty(): Checks if queue is empty * Other Ideas: FIFO structure * Big O: * Push: O(1) * Pop: O(1) * Access front/back: O(1) * Size: O(1)
Map
Access: map[key]
* Important Functions:
* map[key]: Access or insert a value associated with the key
* count(key): Returns 1 if the key exists, otherwise 0
* erase(key): Removes the key-value pair
* size(): Returns the number of key-value pairs
* Other Ideas: Keys are unique and sorted, supports key-based access
* Big O:
* Access by key: O(log n)
* Insertion: O(log n)
* Deletion: O(log n)
* Size: O(1)
String
- Access: string[index]
- Important Functions:
- find(substring): Finds the position of a substring
- substr(start, length): Returns a substring starting at index start and of length length
- size() or length(): Returns the number of characters
- npos: Used to indicate “not found” in find()
- Other Ideas: Functions similarly to vectors but with character-related utilities
- Big O:
- Access: O(1)
- Find: O(n)
- Substring: O(k), where k is the length of the substring
Selection Sort
Selection Sort
* Purpose: Sorting algorithm that repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted element. * Time Complexity: O(n²) * Two nested loops: One to iterate over the unsorted part, and another to find the minimum element. * Space Complexity: O(1) (in-place sorting).
linear search
Linear Search:
* Purpose: A simple search algorithm that checks each element in a list or array sequentially until the target value is found. * Time Complexity: O(n) * Linear search examines each element one-by-one, so in the worst case, it has to check every element. * Space Complexity: O(1) * Linear search only requires a constant amount of extra memory, regardless of the input size.
binary search
- Purpose: Efficiently find a target value in a sorted array by repeatedly halving the search space.
- Time Complexity: O(log n) (search space is halved at each step)
- Space Complexity: O(1) (iterative version) or O(log n) (recursive version)
How it Works:
1. Set two pointers: left at the beginning, right at the end. 2. Calculate the middle index (mid). 3. If target == vec[mid], return mid. 4. If target < vec[mid], search the left half (right = mid - 1). 5. If target > vec[mid], search the right half (left = mid + 1). 6. Repeat until the target is found or left > right.
Requirements:
* Array must be sorted before performing binary search.
Recursion
when a function calls itself to solve a smaller instance of the same problem. eventually the function parameter will reach the value associate with the base case, at which point the recurision will end and the function will return some non recursive result.
Helper Function
You need one during recursion when the main function does not provide enough information or parameters for the recursion to work correctly
Operator Overloading
- Purpose: Redefine operators for custom behavior with class objects.
friend std::ostream& operator«(std::ostream& os, const MyClass& obj) {
os «_space;obj.value;
return os;
}
friend functions
a friend function has access to private and protected members of a class but is itself not a member of the class. you use the friend keyword ( friend bool operator<(const Money& left, const Money& right);
) bool operator<(const Money& left, const Money& right)
{
// don’t need if else here
return (left.mCents < right.mCents);
}
const keyword
either on variables: const int CONSTATN = 10;
on const reference parameters (const int& constInt)
class member functions that cannot alter member variables
int aFunction() const {
streams
used for input and output operations. represent flows of daya, either from a source input or to a destination output. three main types
console (cin, cout)
file
string streams
cin»number – this is the extraction operator to read input into number
cout«“enteranumber” this is the insertion operator to print output.
you have to use #include <iostream>
remember std::endl</iostream>
file stream
include <fstream></fstream>
#include <iostream></iostream>
int main() {
// Writing to a file
std::ofstream outFile(“example.txt”);
if (outFile.is_open()) {
outFile «_space;“Hello, file!” «_space;std::endl;
outFile.close();
}
// Reading from a file
std::ifstream inFile("example.txt");
std::string line;
if (inFile.is_open()) {
while (std::getline(inFile, line)) {
std::cout << line << std::endl; // Output file content to console
}
inFile.close();
}
return 0; }
string streams
include <sstream></sstream>
#include <iostream></iostream>
int main() {
// Writing to a string stream
std::stringstream ss;
ss «_space;“Hello, “ «_space;“world!” «_space;std::endl;
// Reading from a string stream std::string output = ss.str(); // Get the entire string std::cout << output; // Outputs: Hello, world! // String to number conversion using stringstream std::string numStr = "123"; int num; std::stringstream(numStr) >> num; // Convert string to int std::cout << "Number: " << num << std::endl; // Outputs: Number: 123 return 0; }
dynamic memory
used when you want to request memory from the heap during runtime (as opposed to the stack)
you do it as follows
int* ptr = new int;
*ptr = 10;
delete p;
can member functions of a class have access to private member of any instance of that class?
yes, not just the current instance
how would you do a -= operator overload with the money class
Money& Money::operator-=(const Money& right)
{
// simple arithmetic
mCents -= right.mCents; return *(this); }
how would you do a != operator overload
bool operator!=(const Money& left, const Money& right)
{
// just returning the result of the boolean expression
return (left.mCents != right.mCents);
}
how would you do a divided operator overload
Money operator/(const Money& left, double right)
{
// simple arithmetic
long long updatedCents = left.mCents / right;
return Money(updatedCents);
}
how would you do «_space;overload
std::ostream& operator«(std::ostream& out, const Money& money)
{
// we’re storing the value in cents to avoid tricky arithmetic issues that could arrise if we use a floating point number
long long dollars = std::abs(money.mCents/100);
long long cents = std::abs(money.mCents % 100);
bool negative = (money.mCents<0);
// i realized that if the cents were like 6 it would get appended as .6 instead of .06
out << "$" ;
if (negative)
{
out <<"-";
}
out << dollars << "." ;
//realized that this needed to be made abosolute in order to not have issues with negative cents
if (cents<10) {
out << "0";
}
out << cents;
return out; }
how wouldyou do»_space; overload
std::istream& operator»(std::istream& in, Money& money)
{
// create a double variable, assign it the input from in, multiply by 100 to get cents, assign to member cents variable
double dollarsIn;
in >> dollarsIn; money.mCents = dollarsIn * 100; return in; }
