CPP CHEATSHEET

// int, long, long long, unsigned int, unsigned long, unsigned long long 
// double, long double 
// char, string, bool 
// vector<T>, pair<T1, T2>, set<T> 
// map<T1, T2>, unordered_map<T1, T2> 
// queue<T>, stack<T> 
//priority_queue<T> (by default max heap), priority_queue<int, vector <int>, greater <int>> (min heap)  

1. int: 32 bits
2. long: 32 bits
3. long long: 64 bits
4. unsigned int: 32 bits
5. unsigned long: 32 bits
6. unsigned long long: 64 bits
7. double: 64 bits (15 digits after decimal point) 
8. long double: 80 bits (19 digits after decimal point) 
9. char: 8 bit ASCII character 
10. string: a sequence of characters in memory, like an array of char 
11. bool: can take one of two values, true or false (1 or 0)

1. cin and cout: reads and writes data 
2. getline: reads a whole line of data 
3. printf and scanf: C-style input/output; useful when the number of variables or the type of variables is not known 
4. stringstream: adds C++ style syntax to C-style input/output (C++ only)
5. ifstream and ofstream: reads and writes data from/to files (C++ only)
6. fread, fwrite: reads and writes binary files (C only)
7. fopen, fclose, fscanf, fprintf: file operations; use for text files (C only)
8. freopen: redirects one stream to another (C only) 
9. getchar, putchar: reads/writes a single character 

1. begin(container): returns an iterator pointing to the first element in a container
    Example usage:
              for (auto it = begin(container); it != end(container); it++)
               // This will iterate through all the elements in the container
2. end(container): returns an iterator pointing to one element past the last element in a container
3. rbegin(container): returns a reverse iterator pointing to the last element in a container
4. rend(container): returns a reverse iterator pointing to one element before the first element in a container
5. size(container): returns the size of a container
6. empty(container): returns true if the container is empty, false otherwise
7. back(container): returns a reference to the last element in the container
8. front(container): returns a reference to the first element in the container
9. push_back(container, element): adds an element to the end of the container 
10. pop_back(container): removes the last element from the container

	1. vector<T>: a sequence of variables in memory that can be accessed by their position in the sequence (like an array). Efficiency: O(1) random access, O(logN) insertion and deletion.
	2. vector<bool>: a special data type that is more efficient than using a vector<int> for storing booleans. Efficiency: O(1) access and modification.
	3. vector<T>::iterator: the type of an iterator for a vector<T>.

1. set<T>: a container that stores unique elements in sorted order. Efficiency: O(logN) insertion and deletion, O(logN) search.
2. multiset<T>: a container that stores elements in sorted order. Efficiency: O(logN) insertion and deletion, O(logN) search.
3. set<T>::iterator: the type of an iterator for a set<T>.
//Vector methods with efficiency.
1. set<T>::erase(position): removes the element pointed to by position from the set. Efficiency: O(logN).
2. set<T>::erase(first, last): removes all elements in the range [first, last). Efficiency: O(logN + N), where N is the number of elements in the range.
3. set<T>::find(element): searches for an element in the set, and returns an iterator pointing to that element if it is found. Efficiency: O(logN).
4. set<T>::count(element): returns the number of copies of element in the set. Efficiency: O(logN).
5. set<T>::lower_bound(element): returns an iterator pointing to the first element in the set that is not less than element. Efficiency: O(logN).
6. set<T>::upper_bound(element): returns an iterator pointing to the first element in the set that is greater than element. Efficiency: O(logN).
7. set<T>::equal_range(element): returns a pair of iterators pointing to the first and one element past the last element in the set that is equal to element. Efficiency: O(logN).

	
	1. map<T1, T2>: a container that stores key-value pairs in sorted order. Efficiency: O(logN) insertion and deletion, O(logN) search.
	2. multimap<T1, T2>: a container that stores key-value pairs in sorted order. Efficiency: O(logN) insertion and deletion, O(logN) search.
	3. map<T1, T2>::iterator: the type of an iterator for a map<T1, T2>.
	4. map<T1, T2>::value_type: a data type that is a pair<const T1, T2>.

1. unordered_set<T>: a container that stores unique elements in an unordered fashion. Efficiency: O(1) insertion and deletion, O(1) search.
2. unordered_multiset<T>: a container that stores elements in an unordered fashion. Efficiency: O(1) insertion and deletion, O(1) search.
3. unordered_set<T>::iterator: the type of an iterator for a unordered_set<T>.
4. unordered_set<T>::value_type: a data type that is a pair<const T1, T2>.

1. bitset<N>: a data type that allows bitwise operations on 0 to N-1, inclusive.
2. bitset<N>::count(): returns the number of 1's in the bitset.
3. bitset<N>::flip(): flips all bits in the bitset.
4. bitset<N>::reset(): sets all bits in the bitset to 0.
5. bitset<N>::set(): sets all bits in the bitset to 1.
6. bitset<N>::set(position, value): sets the bit at position to value.
7. bitset<N>::test(position): returns the value of the bit at position.

1. stack<T>: a container that stores data in a LIFO (Last In First Out) order.
2. queue<T>: a container that stores data in a FIFO (First In First Out) order.
3. priority_queue<T>: a container that stores data in a priority order.

1. priority_queue<T> (by default max heap): a container that stores data in a priority order. The largest element is placed at the top of the queue. Efficiency: O(logN) insertion, O(1) deletion.
2. priority_queue<T, vector<T>, greater<T>> (min heap): a container that stores data in a priority order. The smallest element is placed at the top of the queue. Efficiency: O(logN) insertion, O(1) deletion.
3. make_heap(first, last, comparison): transforms the range [first, last) into a heap using comparison. Efficiency: O(N).
4. pop_heap(first, last, comparison): transforms the range [first, last) into a heap using comparison, and removes the first element in the heap. Efficiency: O(logN).
5. push_heap(first, last, comparison): transforms the range [first, last) into a heap using comparison, and adds the element last - 1 to the heap. Efficiency: O(logN).
6. sort_heap(first, last, comparison): transforms the range [first, last) into a heap using comparison, and sorts the elements in the range in ascending order. Efficiency: O(N logN).
7. is_heap(first, last, comparison): returns true if the range [first, last) is a heap using comparison, false otherwise. Efficiency: O(N).

	1. priority_queue<T>: a container that stores data in a priority order. The largest element is placed at the top of the queue. Efficiency: O(logN) insertion, O(1) deletion.
	2. priority_queue<T, vector<T>, greater<T>>: a container that stores data in a priority order. The smallest element is placed at the top of the queue. Efficiency: O(logN) insertion, O(1) deletion.

1. sort(first, last, comparison): sorts the range [first, last) using comparison. Efficiency: O(N logN).
2. stable_sort(first, last, comparison): sorts the range [first, last) using comparison. The relative order of equivalent elements is maintained. Efficiency: O(N logN).
3. partial_sort(first, middle, last, comparison): sorts the range [first, last) using comparison so that elements in the range [first, middle) are less than or equal to the elements in the range [middle, last). Efficiency: O(N logN).
4. partial_sort_copy(first, last, resultFirst, resultLast, comparison): copies the range [first, last) to the range [resultFirst, resultLast) using comparison so that elements in the range [resultFirst, resultLast) are less than or equal to the elements in the range [first, last). Efficiency: O(N logN).
5. is_sorted(first, last, comparison): returns true if the range [first, last) is sorted using comparison, false otherwise. Efficiency: O(N).
6. is_sorted_until(first, last, comparison): returns an iterator pointing to the first element in the range [first, last) that is not sorted using comparison. Efficiency: O(N).

	1. binary_search(first, last, value, comparison): returns true if value exists in the range [first, last), false otherwise. Efficiency: O(logN). 
	2. lower_bound(first, last, value, comparison): returns an iterator pointing to the first element in the range [first, last) that has a value not less than value. Efficiency: O(logN).
	3. upper_bound(first, last, value, comparison): returns an iterator pointing to the first element in the range [first, last) that has a value greater than value. Efficiency: O(logN).
	4. equal_range(first, last, value, comparison): returns a pair of iterators pointing to the first and one element past the last element in the range [first, last) that is equal to value. Efficiency: O(logN).

1. string: a data type that is a sequence of characters in memory. 
2. string::iterator: the type of an iterator for a string.
3. string::length(): returns the number of characters in the string.
4. string::empty(): returns true if the string is empty, false otherwise.
5. string::append(): appends a string to the end of the current string.
6. string::swap(): swaps the contents of two strings.
7. string::find(): searches for a string inside the current string, and returns the starting position if found.
8. string::rfind(): searches for a string inside the current string, and returns the starting position of the last occurrence if found.
9. string::replace(): replaces a part of the current string with another string.
10. string::substr(): returns a part of the current string.
11. string::insert(): inserts a string into the current string.
12. string::erase(): removes a part of the current string.
13. string::resize(): changes the size of the current string.
14. string::capacity(): returns the maximum size of the string.
15. string::reserve(): reserves storage for the string.
16. string::c_str(): returns a C-style string.
17. string::copy(): copies a part of the current string to a C-style string.
18. string::compare(): compares two strings.

1. __builtin_popcount(x): returns the number of 1's in the binary representation of x.
2. __builtin_clz(x): returns the number of leading 0's in the binary representation of x.
3. __builtin_ctz(x): returns the number of trailing 0's in the binary representation of x.
4. gcd(a, b): returns the greatest common divisor of a and b using Euclid's algorithm.
5. lcm(a, b): returns the least common multiple of a and b.
6. pow(a, b): returns a raised to the power of b. 
7. isPrime(n): returns true if n is a prime number, false otherwise.
8. sieveOfEratosthenes(n): generates all prime numbers in the range [0, n) (inclusive).
9. eulerTotient(n): returns the number of positive integers less than n that are relatively prime to n.

1. abs(x): returns the absolute value of x.
2. max(x, y): returns the maximum of x and y.
3. min(x, y): returns the minimum of x and y.
4. sqrt(x): returns the square root of x.
5. pow(x, y): returns x raised to the power of y.
6. floor(x): returns the largest integer not greater than x.
7. ceil(x): returns the smallest integer not less than x.
8. round(x): returns the integer closest to x.
9. long long int my_round(double x): returns the integer closest to x.
10. double my_round_double(double x): returns the double closest to x.
11. double to_double(int x): converts an int to a double.
12. double to_double(long long int x): converts a long long int to a double.
13. long long int to_llint(int x): converts an int to a long long int.
14. long long int to_llint(double x): converts a double to a long long int.
15. ld my_sqrt(double x): returns the square root of x as a long double.
16. ld my_pow(double x, double y): returns x raised to the power of y as a long double.
17. double my_pow_double(double x, double y): returns x raised to the power of y as a double.
18. long double my_abs(double x): returns the absolute value of x as a long double.
19. double my_abs_double(double x): returns the absolute value of x as a double.
20. double my_acos(double x): returns the arc cosine of x as a double.
21. long double my_acos(double x): returns the arc cosine of x as a long double.

## Graph theory

```cpp

1. adjList: use an adjacency list to represent a graph as an array of linked lists.
2. adjList<T> graph: creates a graph with T as the node type.
3. graph.nodeCount: the number of nodes in the graph.
4. graph.edgeCount: the number of edges in the graph.
5. graph.nodes: a vector containing all the nodes in the graph.
6. graph.edges: a vector containing all the edges in the graph.
7. graph. neighbourList: an array of linked lists containing the neighbours of each node.
8. graph.index: an array containing the indices of the nodes in the graph.
9. graph. deg: an array containing the degree of each node.
10. graph. addNode(u): adds a node u to the graph.
11. graph. addEdge(u, v): adds an edge from node u to node v with weight 1.
12. graph. addEdge(u, v, weight): adds an edge from node u to node v with weight weight.
13. graph. removeNode(u): removes a node u from the graph.
14. graph. removeEdge(u, v): removes an edge from node u to node v.
15. graph. clear(): clears the graph.
16. graph. getNodeIndex(u): returns the index of node u.
17. graph. getNodeDegree(u): returns the degree of node u.
18. graph. getNodeCount(): returns the number of nodes in the graph.
19. graph. getEdgeCount(): returns the number of edges in the graph.
20. graph. isNode(u): returns true if node u exists in the graph, false otherwise.
21. graph. isEdge(u, v): returns true if there is an edge from node u to node v, false otherwise.

1. dp: use a two-dimensional array to represent a table in dynamic programming.
2. dp<T> table: creates a table with T as the data type.
3. table.rowCount: the number of rows in the table.
4. table.columnCount: the number of columns in the table.
5. table.table: a two-dimensional array containing the data in the table.
6. table. clear(): clears the table.
7. table. resize(rowCount, columnCount): resizes the table.

1. point: a data type for points in two-dimensional space.
2. point p(x, y): creates a point at coordinates (x, y).
3. point p = (x, y): creates a point at coordinates (x, y).
4. point p1 = p2: creates a point p1 with the same coordinates as p2.
5. p.x: the x-coordinate of point p.
6. p.y: the y-coordinate of point p.
7. p1 == p2: returns true if points p1 and p2 have the same coordinates, false otherwise.
8. p1 != p2: returns true if points p1 and p2 have different coordinates, false otherwise.
9. p1 < p2: returns true if the x-coordinate of p1 is less than the x-coordinate of p2, or if the x-coordinates are equal and the y-coordinate of p1 is less than the y-coordinate of p2, false otherwise.
10. p1 > p2: returns true if the x-coordinate of p1 is greater than the x-coordinate of p2, or if the x-coordinates are equal and the y-coordinate of p1 is greater than the y-coordinate of p2, false otherwise.
11. p1 <= p2: returns true if the x-coordinate of p1 is less than or equal to the x-coordinate of p2, or if the x-coordinates are equal and the y-coordinate of p1 is less than or equal to the y-coordinate of p2, false otherwise.
12. p1 >= p2: returns true if the x-coordinate of p1 is greater than or equal to the x-coordinate of p2, or if the x-coordinates are equal and the y-coordinate of p1 is greater than or equal to the y-coordinate of p2, false otherwise.
13. point::operator+(point p): returns the point obtained by adding point p to the current point.
14. point::operator-(point p): returns the point obtained by subtracting point p from the current point.
15. point::operator*(double k): returns the point obtained by multiplying the current point by a scalar k.
16. point::operator/(double k): returns the point obtained by dividing the current point by a scalar k.
17. point::operator+=(point p): adds point p to the current point and returns the result.
18. point::operator-=(point p): subtracts point p from the current point and returns the result.
19. point::operator*=(double k): multiplies the current point by a scalar k and returns the result.
20. point::operator/=(double k): divides the current point by a scalar k and returns the result.
21. point::operator-(): returns the opposite of the current point.
22. point::length(): returns the length of the current point.
23. point::distance(point p): returns the distance between the current point and point p.
24. point::squaredDistance(point p): returns the squared distance between the current point and point p.
25. point::dot(point p): returns the dot product of the current point and point p.
26. point::cross(point p): returns the cross product of the current point and point p.
27. point::perpendicular(): returns a point perpendicular to the current point.
28. point::rotate(double angle, point p): rotates the current point counterclockwise by the specified angle around point p.
29. point::normalized(): returns the normalized version of the current point.
30. point::angle(point p): returns the angle between the current point and point p.
31. point::direction(point p): returns a point with the same direction as the current point, but with length 1.

1. dijkstra(source, target, graph): runs Dijkstra's algorithm on graph, starting at vertex source and going to vertex target. Returns the shortest path to target and the shortest path length. Efficiency: O(E logV).
2. floydWarshall(graph): runs the Floyd-Warshall algorithm on graph. Returns a matrix of shortest paths and a matrix of shortest path lengths. Efficiency: O(V^3).
3. bellmanFord(source, target, graph): runs the Bellman-Ford algorithm on graph, starting at vertex source and going to vertex target. Returns the shortest path to target and the shortest path length. Efficiency: O(VE).
4. dijkstraAll(graph): runs Dijkstra's algorithm on graph, starting at all vertices. Returns a matrix of shortest paths and a matrix of shortest path lengths. Efficiency: O(E logV + V^2).
5. floydWarshallAll(graph): runs the Floyd-Warshall algorithm on graph. Returns a matrix of shortest paths and a matrix of shortest path lengths. Efficiency: O(V^3).
6. bellmanFordAll(graph): runs the Bellman-Ford algorithm on graph, starting at all vertices. Returns a matrix of shortest paths and a matrix of shortest path lengths. Efficiency: O(VE).
7. minCostFlow(graph, capacity, cost, source, target): runs the min-cost max-flow algorithm on graph, with the specified capacity and cost functions and a source and target. Returns the max flow and the cost of the flow. Efficiency: O(F E logV), where F is the max flow.
8. fordFulkerson(graph, capacity, source, target): runs the Ford-Fulkerson algorithm on graph, with the specified capacity function and a source and target. Returns the max flow. Efficiency: O(F E), where F is the max flow.
9. fordFulkersonBinarySearch(graph, capacity, source, target): runs the Ford-Fulkerson algorithm on graph, with the specified capacity function and a source and target. Returns the max flow. Efficiency: O(E^2 V log(CV)), where C is the sum of the capacities on the edges, and V is the number of vertices.
10. johnson(graph): runs the Johnson algorithm on graph. Returns a matrix of shortest paths and a matrix of shortest path lengths. Efficiency: O(VE + V^2 logV).
11. topologicalSort(graph): sorts the vertices of graph topologically. Returns an array of vertices. Efficiency: O(V + E).
12. kosarajuSSC(graph): runs the Kosaraju algorithm on graph. Returns an array of the vertices in each strongly-connected component, in topological order. Efficiency: O(V + E).
13. tarjanSSC(graph): runs the Tarjan algorithm on graph. Returns an array of the vertices in each strongly-connected component, in topological order. Efficiency: O(V + E).
14. biconnectedComponents(graph): runs Tarjan's algorithm on graph. Returns an array of pairs of vertices, each of which is a cut vertex and the other is an articulation point. Efficiency: O(V + E).
15. biconnectedComponentsBridges(graph): runs Tarjan's algorithm on graph. Returns an array of pairs of vertices, each of which is a bridge and the other is an articulation point. Efficiency: O(V + E).
16. cycle(graph): returns true if graph contains a cycle, false otherwise. Efficiency: O(V + E).
17. cycle(graph, source): returns true if graph contains a cycle, starting at source. Efficiency: O(V + E).
18. cycle(graph, source, target): returns true if graph contains a path from source to target that forms a cycle, false otherwise. Efficiency: O(V + E).
19. eulerCycle(graph): returns an Euler cycle in graph, if one exists. Efficiency: O(E).
20. eulerPath(graph): returns an Euler path in graph, if one exists. Efficiency: O(E).
21. bipartite(graph): returns true if graph is bipartite, false otherwise. Efficiency: O(V + E).
22. twoColor(graph): returns true if graph is bipartite, false otherwise. Efficiency: O(V + E).
23. minCut(graph, source, target): returns a minimum cut in graph, with a source and target. Efficiency: O(E V^2).
24. minCut(graph): returns a minimum cut in graph. Efficiency: O(V^3).
25. minCutBipartiteMatching(graph, source, target): returns a minimum cut in graph, with a source and target. Efficiency: O(V^2), assuming the graph is bipartite.
26. minCutBipartiteMatching(graph): returns a minimum cut in graph. Efficiency: O(V^2), assuming the graph is bipartite.
27. stronglyConnectedComponents(graph): runs the Tarjan algorithm on graph. Returns an array of the vertices in each strongly-connected component, in topological order. Efficiency: O(V + E).
28. articulationPoints(graph): runs Tarjan's algorithm on graph. Returns an array of the articulation points in graph. Efficiency: O(V + E).
29. bridges(graph): runs Tarjan's algorithm on graph. Returns an array of the bridges in graph. Efficiency: O(V + E).
30. biconnectedComponents(graph): runs Tarjan's algorithm on graph. Returns an array of pairs of vertices, each of which is a cut vertex and the other is an articulation point. Efficiency: O(V + E).
31. biconnectedComponentsBridges(graph): runs Tarjan's algorithm on graph. Returns an array of pairs of vertices, each of which is a bridge and the other is an articulation point. Efficiency: O(V + E).
32. cycle(graph): returns true if graph contains a cycle, false otherwise. Efficiency: O(V + E).

1. Binary search tree: a container that stores data in a binary tree. Each node stores an element and has two children, a left child and a right child. The left child is less than or equal to the node, and the right child is greater than the node. Efficiency: O(logN) insertion, deletion, and search.
Operations:
Instantiation: BinarySearchTree<int> tree;
Insert: tree.insert(5);
Delete: tree.delete(5);
Search: if (tree.search(5)) { // 5 is in the tree }

2. Fenwick tree: a container that stores data in an array and allows quick updates and range queries on the data. Efficiency: O(logN) updates and range queries.
Operations:
Instantiation: FenwickTree<int> ft(100);
Update: ft.update(5, 1);
Range query: ft.query(5, 10);

3. Union-find: a container that stores data in an array and keeps track of connected components. Efficiency: O(logN) for union and find.
Operations:
Instantiation: UnionFind uf(100);
Union: uf.union(5, 6);
Find: uf.find(5);

4. Segment tree: a container that stores data in an array and allows quick updates and range queries on the data. Efficiency: O(logN) for updates and range queries.
Operations:
Instantiation: SegmentTree<int> st(a, 0, a.size() - 1);
Update: st.update(5, 1);
Range query: st.query(5, 10);

5. Sparse table: a container that stores data in an array and allows quick updates and range queries on the data. Efficiency: O(logN) for updates and range queries.
Operations:
Instantiation: SparseTable<int> st(a);
Update: st.update(5, 1);
Range query: st.query(5, 10);