0. C++ Fundamentals

This section covers the foundational concepts of C++ programming, essential for building any application.

Includes

Standard libraries provide pre-written code for common tasks. Use #include <library_name> to bring them into your program.

• <iostream>: For input/output operations (std::cout, std::cin).
• <vector>: For dynamic arrays (std::vector).
• <string>: For string manipulation (std::string).
• <cmath>: For common mathematical functions (sqrt, pow).
• <algorithm>: For a wide range of algorithms (std::sort, std::min, std::max).
• <map>: For associative arrays (key-value pairs, std::map).
• <set>: For unique, sorted collections (std::set).
• <memory>: For smart pointers (std::unique_ptr, std::shared_ptr).
• <fstream>: For file input/output (std::ifstream, std::ofstream).
• <sstream>: For string stream manipulation (std::stringstream).
• <stdexcept>: For standard exception classes (std::runtime_error).

Basic Data Types

Fundamental types for storing different kinds of data.

• int: Whole numbers (integers), e.g., 5, 10, 0.
• float: Real numbers with decimal points (single precision), e.g., 3.14f, -0.5f.
• double: Real numbers with decimal points (double precision), e.g., 3.14159, -0.01.
• char: Single characters, e.g., 'a', 'B', '7', '?'.
• bool: Boolean values: true or false.
• std::string: Sequences of characters (text), e.g., "hello", "World" (requires #include <string>).

Variables

Named memory locations to store data.

int age = 30; // Declare an integer variable 'age' and initialize it to 30.
double price = 19.99; // Declare a double variable 'price' and initialize it to 19.99.
std::string name = "Alice"; // Declare a string variable 'name' and initialize it to "Alice".
bool isActive = true; // Declare a boolean variable 'isActive' and initialize it to true.
const double PI = 3.14159; // Declare a constant double 'PI'. Its value cannot be changed.

Input/Output

Interacting with the user via the console.

• std::cout: Standard output stream (console).
• std::cin: Standard input stream (keyboard).
• std::endl: Inserts a newline character and flushes the output buffer.
• std::getline(std::cin, var): Reads an entire line of input, including spaces.

#include <iostream>
#include <string> // For std::string and std::getline

int age;
std::string fullName;

std::cout << "Hello, World!" << std::endl; // Print "Hello, World!"
std::cout << "Enter your age: ";
std::cin >> age; // Read an integer

std::cout << "Enter your full name: ";
// std::cin >> std::ws skips any leading whitespace (like the newline left by previous std::cin)
std::getline(std::cin >> std::ws, fullName); // Read the full line of input into the 'name' string.

Operators

Symbols that perform operations on variables and values.

• **Arithmetic**: +, -, *, /, % (modulo/remainder)
• **Comparison**: == (equal to), != (not equal to), < (less than), > (greater than), <= (less than or equal to), >= (greater than or equal to)
• **Logical**: && (AND), || (OR), ! (NOT)
• **Assignment**: = (assign value), += (add and assign), -= (subtract and assign), etc.
• **Bitwise**: & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift), >> (right shift)
• **Increment/Decrement**: ++ (increase by 1), -- (decrease by 1)

Control Flow

Statements that control the order in which instructions are executed.

If-Else

int age = 15;
if (age >= 18) {
    std::cout << "You are an adult." << std::endl;
} else if (age >= 13) {
    std::cout << "You are a teenager." << std::endl;
} else {
    std::cout << "You are a child." << std::endl;
}

Switch

int day = 3;
switch (day) {
    case 1:
        std::cout << "Monday" << std::endl;
        break;
    case 2:
        std::cout << "Tuesday" << std::endl;
        break;
    default:
        std::cout << "Other day" << std::endl;
}

For Loop

for (int i = 0; i < 5; ++i) {
    std::cout << "Iteration: " << i << std::endl;
}

Range-based For Loop

#include <vector>
std::vector<int> numbers = {10, 20, 30};
for (int num : numbers) {
    std::cout << num << " ";
}
std::cout << std::endl;

While Loop

int count = 0;
while (count < 3) {
    std::cout << "Count: " << count << std::endl;
    count++;
}

Do-While Loop

int j = 0;
do {
    std::cout << "J: " << j << std::endl;
    j++;
} while (j < 0); // Condition checked after first execution

Functions

Reusable blocks of code that perform a specific task.

Function Declaration (Prototype)

int add(int a, int b); // Takes two ints, returns an int
void greet(const std::string& name); // Takes a const reference to string, returns nothing

Function Definition

int add(int a, int b) {
    return a + b;
}

void greet(const std::string& name) {
    std::cout << "Hello, " << name << "!" << std::endl;
}

Main Function

The entry point of every C++ program.

int main_example() { // Renamed main to avoid conflict in a single HTML file
    int sum = add(5, 7); // Call 'add' function
    std::cout << "Sum: " << sum << std::endl;
    greet("Bob"); // Call 'greet' function
    return 0; // Indicate successful program execution
}

Arrays

Fixed-size collections of elements of the same type.

int my_array[5] = {1, 2, 3, 4, 5}; // Declare and initialize an array of 5 integers
std::cout << "First element: " << my_array[0] << std::endl; // Access using 0-based index
my_array[2] = 99; // Change element value

Pointers

Variables that store the memory address of another variable.

int x = 10;
int* ptr = &x; // Declare pointer 'ptr' and store address of 'x'

std::cout << "Value of x: " << x << std::endl;
std::cout << "Address of x: " << &x << std::endl;
std::cout << "Value stored in ptr (address of x): " << ptr << std::endl;
std::cout << "Value pointed to by ptr: " << *ptr << std::endl; // Dereference ptr to get value

*ptr = 20; // Change value at address pointed to by ptr (changes x)
std::cout << "New value of x: " << x << std::endl;

References

Aliases (alternative names) for existing variables.

int y = 50;
int& ref = y; // Declare reference 'ref' as an alias for 'y'

std::cout << "Value of y: " << y << std::endl;
std::cout << "Value of ref: " << ref << std::endl;

ref = 60; // Changing 'ref' also changes 'y'
std::cout << "New value of y: " << y << std::endl;

Structures

User-defined data types that group variables of different types together.

struct Point {
    int x;
    int y;
};

Point p1; // Declare a variable 'p1' of type Point
p1.x = 10; // Access the 'x' member of p1
p1.y = 20; // Access the 'y' member of p1

std::cout << "Point coordinates: " << p1.x << ", " << p1.y << std::endl;

Classes (Object-Oriented Programming)

Blueprints for creating objects, encapsulating data (members) and functions (methods).

#include <string> // Required for std::string
#include <iostream> // Required for std::cout

class Dog {
public: // Members accessible from outside the class
    std::string name;
    int age;

    // Constructor: A special function called when an object is created
    Dog(std::string n, int a) : name(n), age(a) {} // Initializer list

    // Member function: A function that belongs to the class
    void bark() {
        std::cout << name << " says Woof!" << std::endl;
    }

private: // Members only accessible within the class
    std::string breed;
};

// Example usage (typically in main or another function)
// Dog my_dog("Buddy", 3);
// my_dog.bark();
// std::cout << "Dog's name: " << my_dog.name << std::endl;
// my_dog.breed = "Golden Retriever"; // Error: 'breed' is private

Templates (Basic)

Allow writing functions or classes that work with different data types.

#include <iostream> // Required for std::cout

template <typename T> // Declare a template with type parameter 'T'
T maximum(T a, T b) { // Function takes two arguments of type T
    return (a > b) ? a : b; // Ternary operator: return a if a > b; else return b
}

// Example usage (typically in main or another function)
// int maxInt = maximum(5, 10);
// double maxDouble = maximum(3.14, 2.71);
// std::cout << "Max int: " << maxInt << std::endl;
// std::cout << "Max double: " << maxDouble << std::endl;

Standard Template Library (STL) Basics

Fundamental containers for storing and managing data.

Vectors

#include <vector>
#include <algorithm> // For std::sort
#include <iostream> // For std::cout

std::vector<int> vec = {5, 1, 4, 2, 8};
std::sort(vec.begin(), vec.end()); // Sort the elements

std::cout << "Sorted vector: ";
for (int val : vec) {
    std::cout << val << " ";
}
std::cout << std::endl;

Maps

#include <map>
#include <string> // For std::string
#include <iostream> // For std::cout

std::map<std::string, int> scores;
scores["Alice"] = 95; // Insert or update key-value pair
scores["Bob"] = 88;

std::cout << "Alice's score: " << scores["Alice"] << std::endl;
for (const auto& pair : scores) { // Iterate through the map
    std::cout << pair.first << ": " << pair.second << std::endl;
}

Sets

#include <set>
#include <iostream> // For std::cout

std::set<int> unique_nums;
unique_nums.insert(5);
unique_nums.insert(1);
unique_nums.insert(5); // Inserting a duplicate has no effect
unique_nums.insert(1);

std::cout << "Unique numbers: ";
for (int num : unique_nums) {
    std::cout << num << " ";
}
std::cout << std::endl;

File I/O

Reading from and writing to files.

#include <fstream>
#include <iostream>
#include <string>

// Writing to a file
void writeToFile() {
    std::ofstream outfile("example.txt"); // Create an output file stream
    if (outfile.is_open()) {
        outfile << "This is line 1.\n";
        outfile << "This is line 2.\n";
        outfile.close();
    } else {
        std::cerr << "Error opening file for writing." << std::endl;
    }
}

// Reading from a file
void readFromFile() {
    std::ifstream infile("example.txt"); // Create an input file stream
    std::string line;
    if (infile.is_open()) {
        while (std::getline(infile, line)) { // Read line by line
            std::cout << "Read line: " << line << std::endl;
        }
        infile.close();
    } else {
        std::cerr << "Error opening file for reading." << std::endl;
    }
}
// Example usage:
// writeToFile();
// readFromFile();

Exception Handling (Basic)

Dealing with errors that occur during program execution.

#include <stdexcept> // Required for std::runtime_error
#include <iostream>

double divide(double a, double b) {
    if (b == 0) {
        throw std::runtime_error("Division by zero!"); // Throw an exception
    }
    return a / b;
}

int main_exceptions() { // Renamed main to avoid conflict
    try {
        double result = divide(10, 2);
        std::cout << "Result: " << result << std::endl;

        result = divide(10, 0); // This will throw an exception
        std::cout << "This line won't be reached." << std::endl;
    } catch (const std::runtime_error& e) { // Catch a specific exception
        std::cerr << "Caught exception: " << e.what() << std::endl;
    } catch (...) { // Catch any other type of exception
        std::cerr << "Caught an unknown exception." << std::endl;
    }
    return 0;
}

Preprocessor Directives

Instructions processed by the compiler before compilation.

• #include <filename>: Includes the contents of another header file.
• #define MACRO_NAME value: Defines a macro.
• #ifdef MACRO_NAME / #endif: Checks if a macro is defined for conditional compilation.

#include <iostream>
#define MAX_SIZE 100

#ifdef DEBUG
    std::cout << "Debug mode enabled." << std::endl;
#endif

// Usage of MAX_SIZE
// int arr[MAX_SIZE];

1. Smart Pointers

Smart pointers are objects that act like pointers but also manage the memory of the object they point to, ensuring proper deallocation and preventing memory leaks.

std::unique_ptr

• Exclusive ownership. Cannot be copied, but can be moved.
• Automatically deallocates memory when it goes out of scope.
• Use std::make_unique for safe construction.

std::unique_ptr<int> ptr1 = std::make_unique<int>(10);
// std::unique_ptr<int> ptr2 = ptr1; // Error: cannot copy
std::unique_ptr<int> ptr3 = std::move(ptr1); // OK: moves ownership

std::shared_ptr

• Shared ownership. Multiple shared_ptrs can point to the same object.
• Uses a reference count; object is deallocated when the last shared_ptr goes out of scope.
• Use std::make_shared for safe and efficient construction.

std::shared_ptr<int> ptr1 = std::make_shared<int>(20);
std::shared_ptr<int> ptr2 = ptr1; // OK: copies ownership, increments ref count
// ptr1.use_count() and ptr2.use_count() will both be 2

std::weak_ptr

• Non-owning "weak" reference to an object managed by std::shared_ptr.
• Does not increment the reference count.
• Used to break circular references between shared_ptrs.
• Must be converted to std::shared_ptr via lock() before use.

std::shared_ptr<int> s_ptr = std::make_shared<int>(30);
std::weak_ptr<int> w_ptr = s_ptr;

if (std::shared_ptr<int> locked_s_ptr = w_ptr.lock()) {
    // Use locked_s_ptr
    std::cout << *locked_s_ptr << std::endl;
} else {
    std::cout << "Object no longer exists." << std::endl;
}

2. Move Semantics

Move semantics allow resources (like dynamically allocated memory) to be transferred from one object to another efficiently, avoiding costly deep copies.

Rvalue References (&&)

• References to temporary objects (rvalues).
• Enable move constructors and move assignment operators.

void func(int& lvalue_ref) { /* ... */ } // Lvalue reference
void func(int&& rvalue_ref) { /* ... */ } // Rvalue reference

int x = 10;
func(x);      // Calls lvalue_ref version
func(20);     // Calls rvalue_ref version (20 is a temporary)
func(std::move(x)); // Calls rvalue_ref version (std::move casts x to rvalue)

std::move

• A function that casts its argument to an rvalue reference.
• Does not move anything itself; it only enables subsequent move operations.

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = std::move(v1); // v1 is now in a valid but unspecified state (likely empty)

Perfect Forwarding (std::forward)

• Used with universal references (template parameter T&&) to preserve the value category (lvalue or rvalue) of an argument when forwarding it to another function.

template<typename T>
void wrapper(T&& arg) {
    // std::forward<T>(arg) preserves the original value category of arg
    some_other_func(std::forward<T>(arg));
}

3. Templates

Templates allow writing generic code that works with different data types.

Function Templates

template<typename T>
T add(T a, T b) {
    return a + b;
}
// Usage: add(5, 10); add(5.5, 10.1);

Class Templates

template<typename T>
class MyContainer {
public:
    T value;
    MyContainer(T val) : value(val) {}
};
// Usage: MyContainer<int> int_cont(10); MyContainer<double> double_cont(10.5);

Variadic Templates

• Templates that can take a variable number of arguments.
• Uses parameter pack (...) to represent a list of arguments.

template<typename T>
void print(T arg) {
    std::cout << arg << std::endl;
}

template<typename T, typename... Args>
void print(T first_arg, Args... rest_of_args) {
    std::cout << first_arg << ", ";
    print(rest_of_args...); // Recursive call to expand the pack
}
// Usage: print(1, "hello", 3.14);

Template Metaprogramming (TMP)

• Performing computations at compile time using templates.
• Often involves recursion and template specialization.
• Example: Factorial calculation at compile time.

template<int N>
struct Factorial {
    static const int value = N * Factorial<N - 1>::value;
};

template<>
struct Factorial<0> {
    static const int value = 1;
};
// Usage: std::cout << Factorial<5>::value << std::endl; // Computes 120 at compile time

4. Lambda Expressions

Anonymous functions that can be defined inline and capture variables from their surrounding scope.

Syntax: [capture_list](parameters) -> return_type { body }

• capture_list:
  • []: No variables captured.
  • [var]: Capture var by value.
  • [&var]: Capture var by reference.
  • [=]: Capture all used variables by value.
  • [&]: Capture all used variables by reference.
  • [this]: Capture this pointer by value.
  • [=, &var]: Capture all by value except var by reference.
  • [&, var]: Capture all by reference except var by value.
• return_type: Optional, can be deduced by the compiler.

Examples:

int x = 10;
auto add_x = [&](int a) { return a + x; }; // Captures x by reference
std::cout << add_x(5) << std::endl; // Output: 15

std::vector<int> nums = {1, 5, 2, 8, 3};
std::sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; }); // Custom sort

5. Concurrency (C++11 onwards)

C++ provides standard library support for multithreading.

std::thread

• Represents a single thread of execution.

void task() {
    std::cout << "Task running in a thread." << std::endl;
}
std::thread t(task);
t.join(); // Wait for the thread to finish
// t.detach(); // Let the thread run independently

Mutexes (std::mutex)

• Used to protect shared data from race conditions.
• lock() and unlock() for manual locking.
• std::lock_guard and std::unique_lock for RAII-style locking.

std::mutex mtx;
int shared_data = 0;

void increment() {
    std::lock_guard<std::mutex> lock(mtx); // Locks mutex on construction, unlocks on destruction
    shared_data++;
}

Condition Variables (std::condition_variable)

• Used for thread synchronization, allowing threads to wait until a certain condition is met.

std::mutex mtx;
std::condition_variable cv;
bool data_ready = false;

void consumer() {
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock, []{ return data_ready; }); // Waits until data_ready is true
    std::cout << "Data consumed." << std::endl;
}

void producer() {
    std::lock_guard<std::mutex> lock(mtx);
    data_ready = true;
    cv.notify_one(); // Notifies one waiting thread
    // cv.notify_all(); // Notifies all waiting threads
}

Futures (std::future, std::async)

• std::async launches an asynchronous task and returns a std::future.
• std::future can be used to retrieve the result of the asynchronous task.

int calculate_sum(int a, int b) {
    return a + b;
}

std::future<int> fut = std::async(std::launch::async, calculate_sum, 10, 20);
int result = fut.get(); // Blocks until result is available

6. STL Advanced

Custom Allocators

• Provide custom memory management strategies for STL containers.
• Useful for performance optimization or specific memory requirements (e.g., fixed-size blocks).

Advanced Algorithms

• std::for_each, std::transform, std::accumulate, std::partition, std::remove_if, std::unique, etc.
• Often used with iterators and lambda expressions.

7. Exception Handling

RAII (Resource Acquisition Is Initialization)

• A C++ programming idiom that ties the lifetime of a resource to the lifetime of an object.
• Resources (memory, file handles, mutexes) are acquired in the constructor and released in the destructor.
• Guarantees resource release even if exceptions occur. Smart pointers are a prime example of RAII.

class FileHandler {
    FILE* file;
public:
    FileHandler(const char* filename, const char* mode) {
        file = fopen(filename, mode);
        if (!file) throw std::runtime_error("Failed to open file.");
    }
    ~FileHandler() {
        if (file) fclose(file);
    }
    // ... other file operations
};

noexcept

• Specifies that a function does not throw exceptions.
• noexcept functions can be optimized more aggressively by the compiler.
• If a noexcept function does throw, std::terminate is called.

void func_no_throw() noexcept {
    // This function promises not to throw.
}

8. C++11/14/17/20 Key Features (Brief)

• C++11: auto, decltype, range-based for loops, nullptr, enum class, override, final, std::chrono, std::tuple, std::array, std::function.
• C++14: Generic lambdas (auto in lambda parameters), constexpr functions improved, variable templates.
• C++17: Structured bindings, if constexpr, std::optional, std::variant, std::any, std::string_view, parallel STL algorithms.
• C++20: Concepts, Modules, Coroutines, Ranges, std::jthread, std::span.

9. Polymorphism and Virtual Functions

Virtual Functions

• Enabled by the virtual keyword in a base class function.
• Allows dynamic dispatch (runtime polymorphism) where the actual function called depends on the type of the object pointed to, not the type of the pointer/reference.
• Requires a vtable (virtual table) lookup at runtime.

class Base {
public:
    virtual void greet() { std::cout << "Hello from Base!" << std::endl; }
};

class Derived : public Base {
public:
    void greet() override { std::cout << "Hello from Derived!" << std::endl; } // 'override' is good practice
};

Base* b = new Derived();
b->greet(); // Calls Derived::greet()
delete b;

Pure Virtual Functions

• A virtual function declared with = 0.
• Makes a class abstract; cannot be instantiated directly.
• Derived classes must implement pure virtual functions unless they are also abstract.

class Shape { // Abstract base class
public:
    virtual double area() = 0; // Pure virtual function
    virtual ~Shape() = default;
};

class Circle : public Shape {
public:
    double radius;
    Circle(double r) : radius(r) {}
    double area() override { return 3.14159 * radius * radius; }
};

CRTP (Curiously Recurring Template Pattern)

• A compile-time polymorphism technique.
• A class Base takes Derived as a template argument, and Derived inherits from Base<Derived>.
• Allows static dispatch (no vtable overhead) while achieving polymorphic-like behavior.

template<typename Derived>
class BaseCRTP {
public:
    void interface() {
        static_cast<Derived*>(this)->implementation();
    }
};

class MyDerived : public BaseCRTP<MyDerived> {
public:
    void implementation() {
        std::cout << "MyDerived implementation." << std::endl;
    }
};
// Usage: MyDerived obj; obj.interface();

10. Memory Management

Custom new and delete Operators

• Can be overloaded globally or for specific classes to customize memory allocation/deallocation.
• Global overload: void* operator new(std::size_t size)
• Class-specific overload: void* ClassName::operator new(std::size_t size)

Placement New

• Constructs an object at a pre-allocated memory location.
• Does not allocate memory, only calls the constructor.

char buffer[sizeof(MyClass)]; // Assuming MyClass is defined
MyClass* obj = new (buffer) MyClass(); // Constructs MyClass in 'buffer'
// Don't use 'delete obj'; explicitly call destructor: obj->~MyClass();

Understanding and Avoiding Memory Leaks

A memory leak occurs when a program allocates memory dynamically but fails to deallocate it when it's no longer needed. This leads to a gradual consumption of available memory, potentially causing the program or even the entire system to slow down or crash.

How Memory Leaks Happen

1. Forgetting to delete allocated memory: The most common cause. If new is used to allocate memory, a corresponding delete must be called to free it.

   // Example of a memory leak
   void leakyFunction() {
       int* data = new int[100]; // Memory allocated
       // ... use data ...
       // No 'delete[] data;' here, so memory is leaked when function exits
   }

2. Losing pointer to allocated memory: If the only pointer to dynamically allocated memory goes out of scope, is reassigned, or is otherwise lost before delete is called, the memory becomes unreachable and cannot be freed.

   void anotherLeakyFunction() {
       int* p = new int(5); // Memory allocated
       p = new int(10);     // 'p' now points to new memory; the old memory (where 5 was) is leaked
       delete p;            // Only the memory for 10 is freed
   }

3. Exceptions: If an exception occurs between a new and its corresponding delete, and there's no proper exception handling (like RAII), the delete might be skipped, leading to a leak.

   void leakyFunctionWithException() {
       int* resource = new int[100]; // Allocate resource
       // ... some operations ...
       if (true) { // Simulate an error/exception condition
           throw std::runtime_error("Something went wrong!");
       }
       delete[] resource; // This line is never reached if an exception is thrown
   }

How to Avoid Memory Leaks

The primary way to avoid memory leaks in modern C++ is to embrace RAII (Resource Acquisition Is Initialization) and use smart pointers.

1. Use Smart Pointers (std::unique_ptr, std::shared_ptr): This is the most effective and recommended approach. Smart pointers automatically manage memory deallocation.
   • std::unique_ptr for exclusive ownership: When a resource has a single, clear owner.

     // Avoiding leak with std::unique_ptr
     void safeFunctionUnique() {
         std::unique_ptr<int[]> data = std::make_unique<int[]>(100); // Memory allocated and managed
         // ... use data ...
         // No explicit delete needed; memory is freed automatically when 'data' goes out of scope
     }

   • std::shared_ptr for shared ownership: When multiple parts of your code need to share ownership of a resource.

     // Assuming MyObject is defined
     // Avoiding leak with std::shared_ptr
     void safeFunctionShared() {
         std::shared_ptr<MyObject> obj = std::make_shared<MyObject>(); // Memory allocated and managed
         // ... pass obj around ...
         // Memory is freed when the last shared_ptr goes out of scope
     }

2. RAII (Resource Acquisition Is Initialization): This principle ensures that resources are acquired in a constructor and released in a destructor. Smart pointers are the prime example, but you can also apply it to other resources like file handles, mutexes, etc. (as shown in the FileHandler example in the "Exception Handling" section).
3. Pair new with delete and new[] with delete[]: If you must use raw pointers and manual memory management (e.g., in low-level code or when interfacing with C libraries), always remember to pair new with delete and new[] with delete[]. This is error-prone and should be avoided in favor of smart pointers whenever possible.

   // Manual memory management (use with extreme caution)
   void manualMemoryManagement() {
       int* singleInt = new int(42);
       // ...
       delete singleInt; // Correctly frees single int
   
       int* intArray = new int[50];
       // ...
       delete[] intArray; // Correctly frees array
   }

By consistently using smart pointers and adhering to the RAII principle, you can significantly reduce the risk of memory leaks in your C++ applications.

11. Inbuilt Data Structures

The C++ Standard Library provides a rich set of container data structures. Understanding their characteristics is crucial for efficient programming.

std::vector

• Description: A dynamic array that can resize itself. Elements are stored contiguously in memory.

#include <vector>
#include <iostream>
std::vector<int> vec = {10, 20, 30};
vec.push_back(40); // Add element
std::cout << vec[0] << std::endl; // Access element

• Performance: Access (by index): $O(1)$, Insertion/Deletion (end): $O(1)$ amortized, Insertion/Deletion (middle/beginning): $O(N)$
• Thread Safety: Not thread-safe for concurrent modifications. Requires external synchronization.

std::list

• Description: A doubly-linked list. Elements are not stored contiguously, allowing efficient insertion and deletion anywhere.

#include <list>
#include <iostream>
std::list<int> lst = {10, 20, 30};
lst.push_back(40);
lst.push_front(5);
lst.remove(20); // Remove by value
for (int x : lst) {
    std::cout << x << " ";
}
std::cout << std::endl;

• Performance: Access (by index): $O(N)$, Insertion/Deletion (anywhere, with iterator): $O(1)$, Insertion/Deletion (without iterator, by value): $O(N)$
• Thread Safety: Not thread-safe for concurrent modifications. Requires external synchronization.

std::deque (Double-Ended Queue)

• Description: A double-ended queue. Similar to std::vector but optimized for insertions and deletions at both ends. Elements are not necessarily contiguous.

#include <deque>
#include <iostream>
std::deque<int> dq = {10, 20, 30};
dq.push_front(5);
dq.push_back(40);
std::cout << dq.front() << ", " << dq.back() << std::endl;

• Performance: Access (by index): $O(1)$, Insertion/Deletion (beginning/end): $O(1)$ amortized, Insertion/Deletion (middle): $O(N)$
• Thread Safety: Not thread-safe for concurrent modifications. Requires external synchronization.

std::set

• Description: An associative container that stores unique elements in a sorted order. Implemented as a self-balancing binary search tree (typically a Red-Black Tree).

#include <set>
#include <iostream>
std::set<int> s = {30, 10, 20};
s.insert(40);
s.insert(10); // Duplicate, ignored
for (int x : s) {
    std::cout << x << " "; // Output: 10 20 30 40
}
std::cout << std::endl;

• Performance: Insertion/Deletion/Search: $O(\log N)$
• Thread Safety: Not thread-safe for concurrent modifications. Requires external synchronization.

std::map

• Description: An associative container that stores key-value pairs in a sorted order based on keys. Keys must be unique. Implemented as a self-balancing binary search tree (typically a Red-Black Tree).

#include <map>
#include <iostream>
std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
std::cout << "Alice's age: " << ages["Alice"] << std::endl;
ages["Bob"] = 26; // Update value

• Performance: Insertion/Deletion/Search: $O(\log N)$
• Thread Safety: Not thread-safe for concurrent modifications. Requires external synchronization.

std::unordered_set

• Description: An associative container that stores unique elements in no particular order. Elements are organized into hash buckets. Provides average constant-time complexity.

#include <unordered_set>
#include <iostream>
std::unordered_set<int> us = {30, 10, 20};
us.insert(40);
us.insert(10); // Duplicate, ignored
if (us.count(20)) {
    std::cout << "20 is in the set." << std::endl;
}

• Performance: Insertion/Deletion/Search: $O(1)$ on average, $O(N)$ worst case (due to hash collisions)
• Thread Safety: Not thread-safe for concurrent modifications. Requires external synchronization.

std::unordered_map

• Description: An associative container that stores key-value pairs in no particular order. Keys must be unique. Elements are organized into hash buckets. Provides average constant-time complexity.

#include <unordered_map>
#include <iostream>
std::unordered_map<std::string, int> scores;
scores["John"] = 95;
scores["Jane"] = 88;
std::cout << "John's score: " << scores["John"] << std::endl;

• Performance: Insertion/Deletion/Search: $O(1)$ on average, $O(N)$ worst case (due to hash collisions)
• Thread Safety: Not thread-safe for concurrent modifications. Requires external synchronization.

std::queue

• Description: A container adaptor that provides a FIFO (First-In, First-Out) data structure. By default, it's implemented using std::deque.

#include <queue>
#include <iostream>
std::queue<int> q;
q.push(10);
q.push(20);
std::cout << q.front() << std::endl; // Output: 10
q.pop();
std::cout << q.front() << std::endl; // Output: 20

• Performance: Push/Pop/Front/Back: $O(1)$
• Thread Safety: Not inherently thread-safe. Requires external synchronization.

std::stack

• Description: A container adaptor that provides a LIFO (Last-In, First-Out) data structure. By default, it's implemented using std::deque.

#include <stack>
#include <iostream>
std::stack<int> s;
s.push(10);
s.push(20);
std::cout << s.top() << std::endl; // Output: 20
s.pop();
std::cout << s.top() << std::endl; // Output: 10

• Performance: Push/Pop/Top: $O(1)$
• Thread Safety: Not inherently thread-safe. Requires external synchronization.

std::priority_queue

• Description: A container adaptor that provides a max-heap (by default). Elements are retrieved in order of priority (largest element first). Implemented using std::vector and heap algorithms.

#include <queue> // For std::priority_queue
#include <iostream>
std::priority_queue<int> pq;
pq.push(30);
pq.push(10);
pq.push(50);
std::cout << pq.top() << std::endl; // Output: 50
pq.pop();
std::cout << pq.top() << std::endl; // Output: 30

• Performance: Push/Pop: $O(\log N)$, Top: $O(1)$
• Thread Safety: Not inherently thread-safe. Requires external synchronization.

Important Note on Thread Safety for STL Containers:

None of the standard C++ containers are inherently thread-safe for concurrent modifications. If multiple threads access and at least one modifies the container, you must use external synchronization mechanisms (like std::mutex) to protect the container and prevent race conditions. Concurrent read-only access by multiple threads is generally safe.

Comparison of Inbuilt Data Structures

12. Design Patterns

Advanced C++ often involves implementing various design patterns. Each pattern below is a collapsible section.

class Singleton {
private:
    Singleton() { /* Private constructor */ }
    // Prevent copy and assignment
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
public:
    static Singleton& getInstance() {
        static Singleton instance; // Guaranteed to be initialized once
        return instance;
    }
    void showMessage() {
        std::cout << "Hello from Singleton!" << std::endl;
    }
};
// Usage: Singleton::getInstance().showMessage();

// Product Interface
class Product {
public:
    virtual ~Product() = default;
    virtual std::string getName() const = 0;
};

// Concrete Products
class ConcreteProductA : public Product {
public:
    std::string getName() const override { return "Product A"; }
};

// Concrete Product
class ConcreteProductB : public Product {
public:
    std::string getName() const override { return "Product B"; }
};

// Creator Interface (Factory)
class Creator {
public:
    virtual ~Creator() = default;
    virtual Product* createProduct() const = 0;
    std::string someOperation() const {
        Product* product = this->createProduct();
        std::string result = "Creator: The product is " + product->getName();
        delete product;
        return result;
    }
};

// Concrete Creators
class ConcreteCreatorA : public Creator {
public:
    Product* createProduct() const override { return new ConcreteProductA(); }
};

class ConcreteCreatorB : public Creator {
public:
    Product* createProduct() const override { return new ConcreteProductB(); }
};
/*
// Usage:
Creator* creatorA = new ConcreteCreatorA();
std::cout << creatorA->someOperation() << std::endl; // Output: Creator: The product is Product A
delete creatorA;
*/

#include <vector>
#include <list>
#include <algorithm>
#include <string> // Required for std::string
#include <iostream> // Required for std::cout

// Observer Interface
class Observer {
public:
    virtual ~Observer() = default;
    virtual void update(const std::string& message) = 0;
};

// Subject (Observable)
class Subject {
private:
    std::list<Observer*> observers;
public:
    void attach(Observer* observer) {
        observers.push_back(observer);
    }
    void detach(Observer* observer) {
        observers.remove(observer);
    }
    void notify(const std::string& message) {
        for (Observer* observer : observers) {
            observer->update(message);
        }
    }
};

// Concrete Observer
class ConcreteObserver : public Observer {
private:
    std::string name;
public:
    ConcreteObserver(const std::string& n) : name(n) {}
    void update(const std::string& message) override {
        std::cout << name << " received update: " << message << std::endl;
    }
};
/*
// Usage:
Subject subject;
ConcreteObserver obs1("Observer 1");
ConcreteObserver obs2("Observer 2");

subject.attach(&obs1);
subject.attach(&obs2);

subject.notify("A new event occurred!"); // Both observers get notified
subject.detach(&obs1);
subject.notify("Another event!"); // Only Observer 2 gets notified
*/

// Strategy Interface
class PaymentStrategy {
public:
    virtual ~PaymentStrategy() = default;
    virtual void pay(int amount) const = 0;
};

// Concrete Strategies
class CreditCardPayment : public PaymentStrategy {
public:
    void pay(int amount) const override {
        std::cout << "Paying " << amount << " using Credit Card." << std::endl;
    }
};

// Concrete Strategy
class PayPalPayment : public PaymentStrategy {
public:
    void pay(int amount) const override {
        std::cout << "Paying " << amount << " using PayPal." << std::endl;
    }
};

// Context
class ShoppingCart {
private:
    PaymentStrategy* paymentStrategy;
public:
    ShoppingCart(PaymentStrategy* strategy) : paymentStrategy(strategy) {}
    ~ShoppingCart() { delete paymentStrategy; } // Ownership assumed
    void setPaymentStrategy(PaymentStrategy* strategy) {
        delete paymentStrategy; // Clean up old strategy
        paymentStrategy = strategy;
    }
    void checkout(int amount) const {
        if(paymentStrategy) paymentStrategy->pay(amount);
    }
};
/*
// Usage:
ShoppingCart cart(new CreditCardPayment());
cart.checkout(100); // Output: Paying 100 using Credit Card.

cart.setPaymentStrategy(new PayPalPayment());
cart.checkout(50); // Output: Paying 50 using PayPal.
*/

// Component Interface
class Coffee {
public:
    virtual ~Coffee() = default;
    virtual double getCost() const = 0;
    virtual std::string getIngredients() const = 0;
};

// Concrete Component
class SimpleCoffee : public Coffee {
public:
    double getCost() const override { return 5.0; }
    std::string getIngredients() const override { return "Coffee"; }
};

// Decorator Base Class
class CoffeeDecorator : public Coffee {
protected:
    Coffee* decoratedCoffee; // Changed from Coffee* to std::unique_ptr for RAII
public:
    CoffeeDecorator(Coffee* coffee) : decoratedCoffee(coffee) {}
    // Destructor now handles decoratedCoffee if it was owned, or unique_ptr handles it.
    // If decoratedCoffee is not owned (e.g. passed as raw ptr and managed elsewhere),
    // then the destructor might not need to delete it.
    // For simplicity here, assuming CoffeeDecorator takes ownership if a raw pointer is passed.
    // Better: pass std::unique_ptr to constructor.
    ~CoffeeDecorator() { delete decoratedCoffee; }


    double getCost() const override { return decoratedCoffee->getCost(); }
    std::string getIngredients() const override { return decoratedCoffee->getIngredients(); }
};

// Concrete Decorators
class MilkDecorator : public CoffeeDecorator {
public:
    MilkDecorator(Coffee* coffee) : CoffeeDecorator(coffee) {}
    double getCost() const override { return decoratedCoffee->getCost() + 1.5; }
    std::string getIngredients() const override {
        return decoratedCoffee->getIngredients() + ", Milk";
    }
};

class SugarDecorator : public CoffeeDecorator {
public:
    SugarDecorator(Coffee* coffee) : CoffeeDecorator(coffee) {}
    double getCost() const override { return decoratedCoffee->getCost() + 0.5; }
    std::string getIngredients() const override {
        return decoratedCoffee->getIngredients() + ", Sugar";
    }
};
/*
// Usage:
Coffee* myCoffee = new SimpleCoffee();
std::cout << "Cost: " << myCoffee->getCost() << ", Ingredients: " << myCoffee->getIngredients() << std::endl;

myCoffee = new MilkDecorator(myCoffee); // Add milk
std::cout << "Cost: " << myCoffee->getCost() << ", Ingredients: " << myCoffee->getIngredients() << std::endl;

myCoffee = new SugarDecorator(myCoffee); // Add sugar
std::cout << "Cost: " << myCoffee->getCost() << ", Ingredients: " << myCoffee->getIngredients() << std::endl;

delete myCoffee; // Clean up all decorators and the base coffee
*/

// Forward declarations
class ConcreteElementA;
class ConcreteElementB;

// Visitor Interface
class Visitor {
public:
    virtual ~Visitor() = default;
    virtual void visit(ConcreteElementA* element) = 0;
    virtual void visit(ConcreteElementB* element) = 0;
};

// Element Interface
class Element {
public:
    virtual ~Element() = default;
    virtual void accept(Visitor* visitor) = 0;
};

// Concrete Elements
class ConcreteElementA : public Element {
public:
    void accept(Visitor* visitor) override {
        visitor->visit(this);
    }
    std::string operationA() const { return "ConcreteElementA"; }
};

class ConcreteElementB : public Element {
public:
    void accept(Visitor* visitor) override {
        visitor->visit(this);
    }
    std::string operationB() const { return "ConcreteElementB"; }
};

// Concrete Visitor
class ConcreteVisitor1 : public Visitor {
public:
    void visit(ConcreteElementA* element) override {
        std::cout << "Visitor 1 processing " << element->operationA() << std::endl;
    }
    void visit(ConcreteElementB* element) override {
        std::cout << "Visitor 1 processing " << element->operationB() << std::endl;
    }
};

// Concrete Visitor
class ConcreteVisitor2 : public Visitor {
public:
    void visit(ConcreteElementA* element) override {
        std::cout << "Visitor 2 processing " << element->operationA() << " differently." << std::endl;
    }
    void visit(ConcreteElementB* element) override {
        std::cout << "Visitor 2 processing " << element->operationB() << " differently." << std::endl;
    }
};
/*
// Usage:
std::vector<Element*> elements = {new ConcreteElementA(), new ConcreteElementB()};

ConcreteVisitor1 visitor1;
for (Element* elem : elements) {
    elem->accept(&visitor1);
}

ConcreteVisitor2 visitor2;
for (Element* elem : elements) {
    elem->accept(&visitor2);
}

for (Element* elem : elements) {
    delete elem;
}
*/