Intro to C++

Data Structure

C++ provides a rich set of data structures through both its core language and the Standard Template Library (STL). Here’s a list of commonly supported data structures with some example usage.

---

1. Array

• Fixed-size collection of elements of the same type.
• Access elements using an index.

Example:

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    for (int i = 0; i < 5; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

---

2. Vector (Dynamic Array)

• Provided by the STL; resizable array.
• Supports dynamic resizing, insertion, and deletion.

Example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4};
    vec.push_back(5);  // Add element
    vec.pop_back();    // Remove last element
    for (int v : vec) {
        cout << v << " ";
    }
    return 0;
}

---

3. List (Doubly Linked List)

• A doubly linked list with O(1) insertion & deletion.

Example:

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {10, 20, 30};
    lst.push_back(40);  // Add to the end
    lst.push_front(5);  // Add to the beginning

    for (int v : lst) {
        cout << v << " ";
    }
    return 0;
}

---

4. Deque (Double-Ended Queue)

• Allows insertion and deletion at both ends.
• can access via indexing with O(1).

Example:

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq = {10, 20, 30};
    dq.push_front(5);  // Add to front
    dq.push_back(40);  // Add to back

    for (int v : dq) {
        cout << v << " ";
    }
    return 0;
}

---

5. Stack

• Last-In-First-Out (LIFO) structure implemented using std::stack.

Example:

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> stk;
    stk.push(10);
    stk.push(20);
    stk.push(30);

    while (!stk.empty()) {
        cout << stk.top() << " ";  // Access top element
        stk.pop();                // Remove top element
    }
    return 0;
}

---

6. Queue

• First-In-First-Out (FIFO) structure implemented using std::queue.

Example:

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);

    while (!q.empty()) {
        cout << q.front() << " ";  // Access front element
        q.pop();                  // Remove front element
    }
    return 0;
}

---

7. Priority Queue (Heap)

• A specialized queue where the largest (or smallest) element is at the top.
• implemented via dynamic array (vector)

Time Complexity

• Push (insert): O(log n) due to heapify-up operation
• Pop (remove top element): O(log n) due to heapify-down operation
• Top (access the maximum/minimum): O(1)
• Size: O(1) is tracked internally

Example:

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;  // Max heap by default
    pq.push(30);
    pq.push(10);
    pq.push(50);

    while (!pq.empty()) {
        cout << pq.top() << " ";  // Access highest priority element
        pq.pop();                 // Remove it
    }
    return 0;
}

---

8. Set

• Set is implemented as a self-balancing binary search tree (usually a red-black tree).
• It maintains elements in sorted order.

Time Complexity

• Insert: O(log n) due to tree rebalancing
• Erase: O(log n) removing a node and rebalancing the tree.
• Size: O(1) is tracked internally.
• Lookup methods (e.g. find, count): O(log n)

Example:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {10, 20, 30, 10};  // Duplicate 10 is ignored
    s.insert(40);

    for (int v : s) {
        cout << v << " ";
    }
    return 0;
}

💡mySet.end() returns an iterator pointing to the position just past the last element of the set. It is not dereferenceable.

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Create a set of integers
    set<int> mySet = {10, 20, 30, 40, 50};

    // Example 1: Using find()
    auto it = mySet.find(30); // Search for the value 30
    if (it != mySet.end()) {
        cout << "Found: " << *it << endl; // Output: Found: 30
    } else {
        cout << "Not Found" << endl;
        // cout << *it; 
        // is UNSAFE option!!!: Dereferencing will cause undefined behavior
    }

    auto it2 = mySet.find(25); // Search for the value 25
    if (it2 == mySet.end()) {
        cout << "25 Not Found" << endl; // Output: 25 Not Found
    }

    // Example 2: Using count()
    int exists = mySet.count(40); // Check if 40 exists
    cout << "40 exists: " << exists << endl; // Output: 40 exists: 1

    int notExists = mySet.count(100); // Check if 100 exists
    cout << "100 exists: " << notExists << endl; // Output: 100 exists: 0

    return 0;
}

---

9. Map

• Key-value pairs, where each key is unique.
• A std::map is typically implemented as a balanced binary search tree, like a red-black tree.

Time Complexity

• Insert: O(log n) due to tree balancing.
• Get (find): O(log n) binary search through the tree.
• Remove (erase): O(log n) find the element and rebalance the tree.

Example:

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> mp;
    mp["apple"] = 3;
    mp["banana"] = 5;
    mp["cherry"] = 2;

    for (auto &pair : mp) {
        cout << pair.first << ": " << pair.second << endl;
    }
    return 0;
}

---

10. Unordered Set and Unordered Map/Hash Map

• Like set and map, but elements are not sorted and offer better average-case performance for lookups.

Example:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> ump;
    ump["one"] = 1;
    ump["two"] = 2;

    for (auto &pair : ump) {
        cout << pair.first << ": " << pair.second << endl;
    }
    return 0;
}

---

Memory Allocation, Pointers, and Freeing Memory in C++

In C++, memory is divided into:
1. Stack: Automatically managed memory for local variables.
2. Heap: Manually managed memory for dynamic allocation.

---

1. Memory Allocation

Memory allocation can be done statically, automatically, or dynamically.

Static/Automatic Allocation (Stack)

• Memory for variables is allocated at compile-time.
• Automatically deallocated when the scope ends.

Example:

void func() {
    int a = 10; // Allocated on the stack
    // Automatically deallocated when func() exits
}

Dynamic Allocation (Heap)

• Memory is allocated at runtime using new.
• Must be manually deallocated using delete to avoid memory leaks.

Example:

int* ptr = new int(10); // Dynamically allocate an integer on the heap
cout << *ptr << endl;   // Access the value
delete ptr;             // Free memory

---

2. Pointers

• A pointer stores the address of another variable.
• Syntax: type* pointer_name;

Example

#include <iostream>
using namespace std;

int main() {
    int a = 10;
    cout << "a: " << a << endl; // prints 10
    cout << "a: " << &a << endl; // prints address of a
    
    cout << "--------------------" << endl;
    
    int* b = &a; // b holds the address of a
    cout << "b: " << b << endl; // prints address of a
    cout << "b: " << *b << endl; // prints value of a
    
    cout << "--------------------" << endl;
    
    *b = 100; // change the value of a (what b is pointing to)
    cout << "a: " << a << endl; // prints 100
    cout << "b: " << *b << endl; // prints 100

    return 0;
}

Output

a: 10
a: 0x7ffff6d02274
--------------------
b: 0x7ffff6d02274
b: 10
--------------------
a: 100
b: 100

---

3. Freeing Memory

• Use delete for a single object.
• Use delete[] for dynamically allocated arrays.

Example (Freeing Memory):

int* arr = new int[5];  // Allocate an array
for (int i = 0; i < 5; ++i) arr[i] = i * 10; // Assign values
delete[] arr;          // Free the array memory

💡 In the case for 2+ dimenstional list, you need to delete each row in it 👇🏻

int** arr = new int*[rows];  // Allocate memory for 'rows' pointers

for (int i = 0; i < rows; ++i) {
    arr[i] = new int[cols];  // Allocate memory for each row
}

// FYI: the array will have garbage values assigned by default 

// Memory allocation still occurred, so it must be freed
for (int i = 0; i < rows; ++i) {
    delete[] arr[i];  // Free each row
}
delete[] arr;  // Free the array of row pointers

---

4. Common Issues

• Dangling Pointer: Accessing memory after it’s freed.

  int* p = new int(10);
  delete p;
  // cout << *p; // Undefined behavior (memory is freed)

• Memory Leak: Forgetting to delete allocated memory.

  int* p = new int(10);
  // Memory not freed, causes a memory leak

---

Summary

• Use stack for automatic memory management (local variables).
• Use heap for dynamic memory with new and free it with delete.
• Be careful with pointers to avoid memory leaks or dangling pointers.