Skip to content

C++ Note

目录

  1. The Compilation Process (Page 1)

  2. Object Files and Linking (Page 2)

  3. Introduction to Memory (Page 2)

  4. A Process in Memory (Page 3)

  5. The Stack (Page 4)

  6. The Heap (Pages 5–7)

  7. Pointers (Page 8)

  8. An Evolution of C: C++ Introduction (Page 9–10)

  9. C++: RAII, Destructors, Object Lifecycle (Page 11–13)

  10. C++: Inheritance and Polymorphism Example (Page 14–15, 17)

  11. C++: Copy Constructor and Assignment Operator (Page 17–20)

  12. C++: Strings (Page 18–19)

  13. Abstract Data Type (ADT) - General Concept

  14. Data Abstractions in C

  15. Data Abstractions in Object-Oriented Languages (OOP)

  16. C++ Templates (Generic Programming)

  17. Metaprogramming with Templates

  18. Syntax(Struct, enumer, pass, argument, array, type safety, new and delete)

1. Introduction

  • Simple: It is a simple language in the sense that programs can be broken down into logical units and parts, and has a rich library support and a variety of datatypes.
  • Machine Independent: C++ code can be run on any machine as long as a suitable compiler is provided.
  • Low-level Access: C++ provides low-level access to system resources, which makes it a suitable choice for system programming and writing efficient code.
  • Fast Execution Speed: C++ is one of the fastest high-level languages. There is no additional processing overhead in C++, it is blazing fast.

  • Object-Oriented: One of the strongest points of the language which sets it apart from C. Object-Oriented support helps C++ to make maintainable and extensible programs. i.e. large-scale applications can be built.

  • C++ remains one of the most used and popular programming languages used in making operating systems, embedded systems, graphical user interfaces and nowadays in High Frequency Trading (HFT) systems.

  • It supports both low-level and high-level features such as manual memory management and OOPs programming respectively.
  • Syntax similarity with C, Java, and C# makes it easier to switch languages.

  • C++ provides one of the fastest execution speeds among high level languages, which can be a deciding factor in Competitive Programming or high-performance applications.

  • Template Metaprogramming: C++ templates enable powerful generic programming and compile-time computations. You can write code that generates code, perform calculations at compile time, and create highly flexible, reusable components without runtime overhead.

  • Multiple Inheritance: Unlike many object-oriented languages, C++ allows a class to inherit from multiple parent classes simultaneously, providing greater flexibility in designing class hierarchies and code reuse patterns.
  • Operator Overloading: C++ lets you redefine the behavior of operators (like +, -, *, ==) for user-defined types, making custom classes feel natural and intuitive to use, similar to built-in types.
  • RAII (Resource Acquisition Is Initialization) : C++ follows the principle where resources are automatically managed through object lifetimes. When objects go out of scope, their destructors automatically clean up resources, preventing resource leaks.
  • Standard Template Library (STL) : C++ includes a comprehensive collection of template classes and algorithms for common data structures (vectors, maps, sets) and algorithms (sorting, searching), providing efficient, well-tested implementations.
  • Deterministic Destructors: Unlike garbage-collected languages, C++ objects are destroyed at predictable times when they go out of scope, giving developers precise control over resource cleanup and making behavior more predictable.
  • Zero-Cost Abstractions: C++ allows high-level programming constructs that compile down to efficient machine code with no runtime overhead. You can write expressive code without sacrificing performance.
  • Compile-Time Polymorphism: Through templates and function overloading, C++ can resolve many polymorphic calls at compile time rather than runtime, eliminating the overhead of virtual function calls when not needed.
  • Direct Memory and Hardware Access: C++ provides precise control over memory layout, pointer arithmetic, and hardware registers, making it ideal for system programming, embedded development, and performance-critical applications.

1. The Compilation Process (Page 1)

  • Definition: The sequence of steps a program goes through to transform human-readable source code into an executable machine code program.

image​ - Steps/Components:

  1. Source Program (text): e.g., hello.c​

    • Human-written code.

    • Preprocessor (cpp):

    • Modifies the source code based on directives.

    • Output: Modified source program (text), e.g., hello.i​

    • Compiler (cc1):

    • Translates the modified source code into assembly language.

    • Output: Assembly program (text), e.g., hello.s​

    • Assembler (as):

    • Translates the assembly program into machine code (object code).

    • Output: Relocatable object program (binary), e.g., hello.o​

    • Linker (ld):

    • Combines one or more object programs and libraries (e.g., stdlib.so - a shared object library) to create an executable program.

    • Resolves references between different object files.
    • Output: Executable object program (binary), e.g., hello​
    • Attention/Key Points:

  2. The diagram shows distinct stages and the tools typically used (cpp, cc1, as, ld).

  3. ​stdlib.so represents a shared library that can be linked at this stage.

  4. Example: The hello world example

  5. ​main.c:

    /* main.c */
#include <unistd.h>

extern char* hello(void);
extern int messageLength(void);

int main(void) {
    write(STDOUT_FILENO, hello(), messageLength());
    return 0;
}
    - ​hello.c:

    /* hello.c */
#define hi "Hello world\n"
#define hiLength 12

char *hello(void) {
    return hi;
}

int messageLength(void) {
    return hiLength;
}
    - After Preprocessing (main.i - partial view):

    /* main.i */
#include <unistd.h> // Contents of unistd.h would be expanded here

extern char* hello(void);
extern int messageLength(void);

int main(void) {
    write(1, hello(), messageLength()); // STDOUT_FILENO (often 1) substituted
    return 0;
}
    - After Preprocessing (hello.i - partial view):

    /* hello.i */
char *hello(void) {
    return "Hello world\n"; // 'hi' macro expanded
}

int messageLength(void) {
    return 12; // 'hiLength' macro expanded
}

2. Object Files and Linking (Page 2)

  • Definition (Relocatable Object File - ​.o​​ ): A file containing compiled machine code and data that is not yet linked into a full executable. It may contain unresolved symbols (references to code/data in other object files).

image​ - Key Points:

  • ​main.o:

    • Contains the compiled main function.
    • References to hello and messageLength are unresolved (shown as hello -> ???, messageLength -> ???).
    • ​main -> MAIN_ADDR (address of main within this object file).

    • ​hello.o:

    • Contains the compiled hello and messageLength functions.

    • ​ADDR_D0="Hello world\n" (address of the string literal).
    • ​hello -> HELLO_ADDR (address of hello function).
    • ​messageLength -> M_ADDR (address of messageLength function).
    • Linking: The linker resolves these ??? by matching them with definitions in other object files (like hello.o) or libraries. It combines these into a single executable and assigns final memory addresses.
    • The diagram shows hello (the linked executable) has both main, hello, and messageLength resolved, with ADDR_D0, MAIN_ADDR, HELLO_ADDR, M_ADDR all assigned final addresses within the executable's address space.

3. Introduction to Memory (Page 2)

  • Definition: Memory is a sequence of Bytes.

  • Key Points:

  • Byte-addressable: Each byte in memory has a unique address.

  • Data types: Different data types (like unsigned char, char, int) require different amounts of memory space.
  • Interpretation: The data type determines how a sequence of bytes at a given address is interpreted to represent a value.

  • Example:

  • A byte at an address containing 0x03 can be interpreted as the integer 3 if treated as an unsigned char.

  • A byte at an address containing 0x07 (ASCII for 'h' if this were 0x68) can be interpreted as the character 'h' if treated as a char. (Slide has (0x7) = 'h', which is not standard ASCII; 0x68 is 'h'. Assuming a typo or simplified representation).
  • Four bytes starting at an address containing 00 00 00 2A (hex for 42, assuming little-endian if 2A is the first byte or big-endian if 2A is the last byte in 0|0|0|42) can be interpreted as the integer 42 if treated as an int. (Slide shows (0xFC)=42 which is incorrect; 0xFC is 252. The diagram | | | |0|0|0|42 implies 0x0000002A for 42).

4. A Process in Memory (Page 3)

  • Definition: The memory layout of a running program (a process).

image​ - Segments:

  1. CODE (​ ​.text​​ ): Executable instructions. Read-only.

    • Includes code from statically linked libraries.

    • Initialized static data (​ ​.data​​ ): Global and static variables initialized with non-zero values.

    • Includes initialized data from statically linked libraries.

    • Uninitialized static data (​ ​.bss​ - Block Started by Symbol): Global and static variables initialized to zero or not explicitly initialized.

    • Includes uninitialized data from statically linked libraries.

    • HEAP: Dynamically allocated memory (e.g., using malloc, new). Grows, typically towards higher addresses (or in the diagram, downwards from the perspective of filling space).

    • Shared Memory:

    • Region for dynamically linked libraries (e.g., .so files).

    • Other shared memory segments (e.g., for inter-process communication).
    • STACK: Local variables, function arguments, return addresses. Grows, typically towards lower addresses.
    • Kernel Space: Memory reserved for the operating system kernel. Inaccessible to user programs directly.
    • Key Points/Attention:

  2. Address space boundaries: MIN_VALID_ADDR to MAX_VALID_ADDR.

  3. The program's structure on disk (ELF sections like .text, .data, .bss) influences the memory layout.
  4. Statically linked libraries have their code and data merged directly into the executable's segments.
  5. Dynamically linked libraries are mapped into the "Shared Memory" region.
  6. Heap and Stack are dynamic regions that grow (often in opposite directions) to maximize address space utilization.
  7. The kernel maintains its own protected memory space.

5. The Stack (Page 4)

  • Definition: A region of memory used for storing temporary data related to function calls, such as local variables, function arguments, and return addresses. It operates on a Last-In, First-Out (LIFO) principle. It's a stack of Activation Records (or stack frames).

image​ - Activation Record / Stack Frame:

  • Local variables: Variables declared inside the function.
  • Base (pointer): Typically a pointer to the beginning of the current frame or the previous frame.
  • Return address: The address in the calling function to return to after the current function completes.
  • Arguments: Parameters passed to the function.

  • Key Points/Attention:

  • The stack grows from "Higher Memory Address" towards "Lower Memory Address" (a common convention, e.g., on x86).

  • When FUNCTION A calls FUNCTION B, FUNCTION B's activation record is pushed on top of FUNCTION A's.

  • CRITICAL: Why you should NOT return pointers to a function's local variables.

    • When a function returns, its stack frame is deallocated (popped).
    • Memory previously occupied by local variables is now considered "garbage" or available for reuse.
    • A pointer to such memory becomes a dangling pointer. Dereferencing it leads to undefined behavior.
    • Example (Dangling Pointer):
#include <stdlib.h>
#include <stdio.h>

int * foo(int baseValue) {
    int myLocalVariable = baseValue;
    if (myLocalVariable % 2 != 0) {
        myLocalVariable++;
    } else {
        myLocalVariable = myLocalVariable * 2;
    }
    return &myLocalVariable; // DANGER: Returning address of local variable
}

int bar(int baseValue) {
    int myLocalVariable = baseValue;
    if (myLocalVariable % 2 != 0) {
        myLocalVariable--;
    } else {
        myLocalVariable = myLocalVariable / 2;
    }
    return myLocalVariable; // SAFE: Returning value
}

int main(void) {
    int * ptrToValue = foo(32); // ptrToValue gets address of foo's myLocalVariable (which was 64)
                                // foo's stack frame is now GONE. ptrToValue is dangling.
    printf("Printing foo's local variable: %d\n", *ptrToValue); // UNDEFINED BEHAVIOR
    printf("Printing bar's return value: %d\n", bar(32));      // bar(32) returns 16. Safe.
                                                                // The call to bar and printf likely overwrote
                                                                // the memory ptrToValue points to.
    printf("Re-printing foo's local variable: %d\n", *ptrToValue); // UNDEFINED BEHAVIOR, very likely garbage or crash
}

  • Explanation:

    1. ​ptrToValue = foo(32): foo's myLocalVariable becomes 64. foo returns its address. ptrToValue holds this address.
    2. After foo returns, its stack frame is popped. ptrToValue is now a dangling pointer.
    3. ​printf("...foo's local...", *ptrToValue): Might print 64 by luck, or garbage, or crash.
    4. ​bar(32) is called. Its myLocalVariable becomes 16. It returns 16. This is safe. The stack space used by bar (and printf) might overwrite the memory ptrToValue was pointing to.
    5. ​printf("...Re-printing foo's...", *ptrToValue): Highly likely to print garbage or crash, as the memory location has likely been overwritten.

6. The Heap (Pages 5-7)

  • Definition (Conceptual Introduction - Page 5 & 6): A region of memory used for dynamic memory allocation, where the program can request and release blocks of memory of arbitrary size at runtime.

  • Motivation (Problems with Stack-Only Allocation):

  • Option 1 (N local variables): Product p1, p2, ..., pN;​

    • Memory Used: Stack.
    • Limitations: Highly inflexible (N fixed at compile time), impractical for many items, stack size limit ("stack overflow").

    • Option 2 (Fixed array on stack): Product products[N];​

    • Memory Used: Stack.

    • Limitations: Inflexible (N fixed at compile time), stack size limit.

    • Option 3 (Dynamically initialized array): products = new Product[size]; (C++ syntax implied)

    • Memory Used: The Heap. products pointer itself might be on stack, but the array data is on the heap.

    • Advantages: Flexibility (size determined at runtime), handles large data (heap is generally larger than stack).
    • Responsibility: Programmer must free this memory (e.g., delete[] products). Failure leads to a "memory leak."

    • Option 4 (Dynamic structure): Using list, set, map, tree, etc.

    • Memory Used: The Heap. These structures request memory from the heap as they grow.

    • Advantages: Even more flexible (can grow and shrink easily).
    • Detailed Definition & Characteristics (Page 7):

  • A region of free memory available to the program at runtime.

  • Memory is allocated from here using functions/operators like new (in C++)
  • It typically "grows" upwards (towards higher memory addresses in many systems, though the diagram on page 7 shows it conceptually growing downwards towards the stack to illustrate they can collide). The key is it's a flexible pool.
  • The programmer must explicitly deallocate (release) memory from the heap using delete (in C++)

  • Key Points/Attention (Page 7):

  • Stack vs. Heap:

    • Stack: Used for local variables, function arguments, return addresses. Memory allocated/deallocated automatically (LIFO). Typically "grows" downwards.
    • Heap: For dynamic allocation. Manual allocation/deallocation.
    • Collision: The stack and heap grow towards each other. If they collide, the program runs out of memory.
    • Kernel Space: Memory used by the OS; user programs cannot access it directly.

    • Programmer Responsibility (Page 8):

    • Allocation: You must ask for memory (e.g., new Product[size]).

    • Deallocation: You must give it back when done (e.g., delete[] products).

    • Failure to deallocate causes memory leaks.

    • Using memory after it has been freed leads to dangling pointers and undefined behavior (often crashes).

    • Why Use Heap? (Page 8):

    • Amount of memory needed is unknown at compile time.

    • Data needs to persist longer than the function call that created it.
    • For large data structures that might overflow the stack.
    • Example

#include <iostream>
#include <vector> // For std::vector (Option 4)
#include <string>

// Simple Item struct
struct Item {
    int id;
    std::string name;

    // Constructor to see when objects are created
    Item(int i = 0, std::string n = "Default") : id(i), name(n) {
        std::cout << "  Item " << id << " ('" << name << "') CREATED." << std::endl;
    }

    // Destructor to see when objects are destroyed
    ~Item() {
        std::cout << "  Item " << id << " ('" << name << "') DESTROYED." << std::endl;
    }
};

int main() {
    std::cout << "--- Option 3: Dynamically Allocated Array ---" << std::endl;
    int arraySize = 3; // Let's use a fixed size for simplicity

    // 'itemsArray' pointer itself is on the stack.
    // Memory for 'arraySize' Item objects is allocated on THE HEAP.
    Item* itemsArray = new Item[arraySize];
    std::cout << "Dynamically allocated array of " << arraySize << " Items created on the HEAP." << std::endl;

    // Initialize items (optional, but good to show they exist)
    itemsArray[0] = Item(101, "Apple");  // Creates a temporary, then assigns
    itemsArray[1] = Item(102, "Banana");
    itemsArray[2] = Item(103, "Cherry");
    // Note: The original 3 items from `new Item[arraySize]` are created with default values,
    // then overwritten here. Destructors for those temporaries will be called.

    std::cout << "\nItems in the dynamic array (briefly):" << std::endl;
    for(int i=0; i < arraySize; ++i) {
        std::cout << "  - ID: " << itemsArray[i].id << std::endl;
    }


    // Responsibility: Programmer MUST free this memory.
    // This calls the destructor for each Item object in the array before deallocating memory.
    std::cout << "\nPreparing to delete[] the dynamic array..." << std::endl;
    delete[] itemsArray;
    itemsArray = nullptr; // Good practice: prevent dangling pointer usage
    std::cout << "Dynamic array memory DEALLOCATED." << std::endl;


    std::cout << "\n--- Option 4: Dynamic Structure (std::vector) ---" << std::endl;
    // 'itemList' (the std::vector object) is on the stack.
    // Its internal data (the actual Item objects) is managed on THE HEAP.
    std::vector<Item> itemList;
    std::cout << "std::vector 'itemList' created." << std::endl;

    // Add items. The vector grows dynamically on the HEAP.
    std::cout << "\nAdding items to the vector..." << std::endl;
    itemList.push_back(Item(201, "Dog"));    // Item created and moved/copied into vector
    itemList.push_back(Item(202, "Cat"));
    itemList.emplace_back(203, "Bird"); // More efficient: constructs Item in-place

    std::cout << "\nItems in the vector (briefly):" << std::endl;
    for(const auto& item : itemList) { // const auto& is good practice
        std::cout << "  - ID: " << item.id << std::endl;
    }

    // No explicit delete[] needed by the user for itemList's internal data.
    // The std::vector's destructor will be called when 'itemList' goes out of scope (at the end of main).
    // This destructor handles deallocating heap memory and calling destructors for all contained Items.
    std::cout << "\nEnd of main reached. 'itemList' (vector) will go out of scope and clean up automatically." << std::endl;

    return 0;
} // <- itemList's destructor is automatically called here, cleaning up its heap memory and Item objects.
- |Aspect|Stack|Heap| | --------| -----------------------------------------------------| -------------------------------------------------------------------------| |Purpose|Local variables, function arguments, return address|Dynamically allocated memory (e.g.,new,malloc)| |Allocation/Deallocation|Automatic (LIFO)|Programmer-controlled (new/deleteormalloc/free)| |Growth Direction|Downwards (toward lower addresses on x86)|Upwards (toward higher addresses on many systems)| |Size Limitations|Limited size (stack overflow if too large)|Typically much larger than stack, but still finite (heap exhaustion)| |Flexibility|Fixed at compile-time per function call|Dynamic; can request arbitrary-sized blocks at runtime| |Lifetime|Ends when function returns|Ends when explicitly freed or when program terminates| |Risks|Stack overflow if too many large local variables|Memory leaks if not freed; dangling pointers if freed too soon or twice|

7. Pointers (Page 8)

  • Definition: Variables that hold a memory address as their value.

  • Related Operations:

  • Dereference Operator (​ ​*​ ​ ):

    • Allows access to the value stored at the memory address the pointer holds.
    • Example: int val = *ptr;​

    • Address-of Operator (​ ​&​ ​ ):

    • Allows you to get the memory address of a variable.

    • Example: int x; int *ptr = &x;​

    • Pointer Arithmetic: Operations like increments (++), decrements (--), additions, and subtractions on pointers are "type-aware."

    • Type-Aware Operations:

    • Core Idea: Pointers know the type of data they point to (e.g., int*, char*, MyStruct*).

    • Size Matters: The compiler uses sizeof(pointed-to-type) for calculations.

    • Operations (scaled by ​sizeof​​ ):

      • ​pointer++ or ++pointer: Moves pointer to the next element.

      • Actual address change: current_address + 1 * sizeof(type).

      • ​pointer - N: Calculates address of the N-th element before pointer.

      • Actual address change: current_address - N * sizeof(type).

      • ​pointer2 - pointer1: Result is the number of elements between them (not bytes).

      • Requires pointer1 and pointer2 to be of the same type and typically point into the same array.

      • Calculation: (address_in_pointer2 - address_in_pointer1) / sizeof(type).
      • Array Indexing (​​array[i]​ ​ ): (Page 9)

    • Direct application of pointer arithmetic.

    • ​array[i] is equivalent to *(array + i).
    • ​array (in this context) decays to a pointer to its first element.
    • The + i part automatically scales by element size.
    • Why "Type-Aware" is Key (Page 9):

  • Abstraction: Programmer works with "elements," not raw byte offsets.

  • Portability: Code remains correct even if sizeof(type) varies across platforms.
  • Readability: ptr++ intuitively means "next item."

  • Addressable Entities (Page 9): Almost everything in a program has a memory address, including:

  • String literals

  • Functions
  • Variables
  • Arrays
  • Dynamically allocated memory
  • etc.

8. An Evolution of C: C++ Introduction (Page 9-10)

  • 1. "C++ is a multiparadigm language, as Python." (Page 9)

  • Definition (Multiparadigm): C++ supports multiple ways of thinking about and structuring programs.

  • Key Paradigms in C++:

    • Procedural Programming: (Inherited from C) Organizing code into procedures or functions.
    • Object-Oriented Programming (OOP): Organizing code around "objects," which bundle data (attributes) and functions that operate on that data (methods). Involves classes, inheritance, polymorphism.
    • Generic Programming: Writing code that can work with different data types without being rewritten (e.g., using templates).
    • Functional Programming (to some extent): Features like lambdas and algorithms operating on ranges.
    • 2. "Overloading... create a new symbol/name depending on the types of inputs the function takes." (Page 9-10)

  • Definition (Function Overloading): Allows multiple functions with the same name but different parameter lists (different types, number, or order of arguments).

  • Attention: The compiler performs "name mangling" to give each overloaded function a unique internal name.

  • Example (Page 10):

    // Different add functions based on parameters
int add() { return 0; }
int add(int a) { return a; }
int add(int a, int b) { return a + b; }
int add(int size, int values[]) { /* sum array */ ... }

int main() {
    int my_values[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Calls to different add versions are resolved at compile time
    int result = add(add(add(), add(10)), add(9, my_values));
    printf("Result is: %d\n", result); // Example specific to the slide, may need array size for last add
}
    - 3. "Operator overloading... symbols/names for operators are really hard to find once the program is compiled." (Page 10)

  • Definition (Operator Overloading): Allows defining or redefining how standard operators (like +, -, *, <<, ==, []) behave with objects of custom classes (structs).

  • Attention:

    • Operator overloading also undergoes name mangling, and the mangled names can be very obscure (e.g., operator+ becomes something cryptic).
    • Debuggers often help demangle these names.
    • Example (String multiplication for repetition):

    #include <iostream>
#include <string>

// Overload * for std::string to mean repetition
std::string operator*(const std::string& str, int n) {
    std::string result = "";
    for (int i = 0; i < n; ++i) {
        result += str;
    }
    return result;
}

int main() {
    std::string text = "Hello";
    std::string multiplied_text = text * 3; // Calls the overloaded operator*
    std::cout << multiplied_text << std::endl; // Output: HelloHelloHello
    return 0;
}
    - ​​std::​ ​ : A namespace prefix indicating that the following identifier (e.g., cout, string) is part of the C++ Standard Library. Helps avoid naming conflicts.

9. C++: RAII, Destructors, Object Lifecycle (Page 11-13)

  • 4. "Semi-Automatic memory management of objects created in the stack, i.e.:" (Page 11) - RAII

  • Definition (RAII - Resource Acquisition Is Initialization): A fundamental C++ programming technique where resource management (like memory allocation, file opening, mutex locking) is tied to the lifetime of objects. Acquisition happens in the constructor, release in the destructor.

  • Objects on the Stack:

    • When an object (instance of a class/struct) is a local variable, its memory is on the stack.
    • Its destructor is automatically called when the object goes out of scope (e.g., function ends, block ends).

    void myFunction() {
    MyClass myObject; // Created on the stack. Constructor called.
    // ... do stuff with myObject ...
} // myObject goes out of scope. Destructor for myObject is automatically called here.
    - "An object can be created as both: a value in the stack, a value in the heap..." (Page 11)

  • Value in the stack (Automatic Storage Duration):

    MyClass obj1; // obj1 lives on the stack. Constructor called.
              // Destructor automatically called when obj1 goes out of scope.
    - Value in the heap (Dynamic Storage Duration):

    MyClass* ptrObj = new MyClass(); // ptrObj (the pointer) lives on the stack.
                                // The MyClass object itself lives on the heap. Constructor called.
// ... use ptrObj ...
delete ptrObj; // YOU MUST MANUALLY call delete.
               // This calls the destructor for the MyClass object, then frees memory.
               // If you forget 'delete', it's a memory leak.
    - Attention: The slide's "call the free function" is C-style. In C++, new is paired with delete, and new[] with delete[]. These also handle constructor/destructor calls. - "You still need to implement a destructor for your class (It is the opposite of a constructor)." (Page 11)

  • Definition (Destructor): A special class member function (~ClassName) that is automatically called when an object of the class is about to be destroyed (either by going out of scope for stack objects, or by delete for heap objects).

  • Purpose: To release any resources the object acquired during its lifetime (e.g., free memory allocated on the heap, close files, release network connections).

  • Example (Complex class on Page 11-12):

    #include <iostream>

class Complex {
    private:
        float real;
        float imaginary;
        int id;

    //Complex(float real, float imaginary): real(real), imaginary(imaginary) {};
    public:
        Complex(float real, float imaginary) {
            this->real = real;
            this->imaginary = imaginary;
            id = 0;
        }

        Complex(const Complex& other) {
            this->real = other.real;
            this->imaginary = other.imaginary;
        }
        /*
        This special member function is automatically called 
        when a Complex object is about to be destroyed 
        (e.g., when it goes out of scope, or when delete is called on a pointer 
        to a dynamically allocated Complex object).
        */
        ~Complex() {
            std::cout << "I'm destroyed! (" << id << ")" << std::endl;
        }

        void set_id(int id) {
            this->id = id;
        }

        float get_real() {
            return real;
        }

        float get_imaginary() {
            return imaginary;
        }

        void set_real(float new_real) {
            real = new_real;
        }

        void set_imaginary(float new_imaginary) {
            imaginary = new_imaginary;
        }

        //We use friend so the + operator can access private fields
        friend Complex operator+(Complex const& c1, Complex const& c2);
        friend std::ostream& operator<< (std::ostream& out, const Complex& c);

};

Complex operator+(Complex const& c1, Complex const& c2) {
    return Complex(c1.real + c2.real, c1.imaginary + c2.imaginary);
}

std::ostream& operator<< (std::ostream& out, const Complex& c) {
    out << c.real << " + " << c.imaginary << "i (" << c.id << ")";
    return out;
}

int main() {
    Complex c1(1.0f, 2.0f);
    c1.set_id(1);
    Complex * c2 = new Complex(3.0f, 4.0f);//allocate memory on the heap using new
    c2->set_id(2);
    Complex c1PlusC2 = c1 + *(c2);
    c1PlusC2.set_id(3);
    std::cout << "(" << c1 << ") + (" << *(c2) << ") is (" << c1PlusC2 << ")" << std::endl;
    delete(c2);
    return 0;
}

//
(1 + 2i (1)) + (3 + 4i (2)) is (4 + 6i (3))
I'm destroyed! (2)
I'm destroyed! (3)
I'm destroyed! (1)
    - Attention: The order of destruction for stack objects is the reverse of their construction. c2 (heap) is destroyed when delete is called. c1PlusC2 then c1 (stack) are destroyed as main exits. - Declaration Before Mention (Page 13):

  • Functions (and variables, types) must generally be declared before they are used.

  • A declaration introduces a name and its type to the compiler (extern int add(int a, int b);).
  • A definition provides the actual implementation or allocates storage (int add(const int a, int b) { return a + b; }).
  • An executable needs definitions for all used symbols.

  • Namespaces (Page 13, 16):

  • Definition: A feature that provides a named scope to prevent name collisions in large projects. Code is organized into logical groups.

  • Example (Page 13): MyProject::List and StandardLibrary::List.

  • Example (Page 16):

    #include <iostream>

namespace my_namespace { int variable_a = 2; }
namespace my_other_namespace { int variable_a = 3; }

int main() {
    printf("variable_a from my_namespace: %d\n", my_namespace::variable_a);
    printf("variable_a from my_other_namespace: %d\n", my_other_namespace::variable_a);

    // Using 'using namespace std;' (from another example on page 16)
    // std::string s = "Hello"; becomes string s = "Hello";
    // std::cout becomes cout;
    return 0;
}
    - Attention: using namespace std; is common in small examples but can be risky in larger projects (especially in headers) as it brings all names from std into the current scope, potentially causing collisions. - Classes in C++ (Page 13-14):

  • Inheritance:

    • Mechanism for creating new classes (derived classes) from existing ones (base classes).

    • Multiple Inheritance: A class can inherit from more than one base class.

    • Diamond Problem: Ambiguity if a class inherits from two classes that share a common ancestor, potentially getting multiple copies of the ancestor's members. C++ provides virtual inheritance to solve this.

      Problem:

      class A { public: int value; };
class B : public A { };
class C : public A { };
class D : public B, public C { };  // D has TWO copies of A!

      Solution - Virtual Inheritance:

      class A { public: int value; };
class B : virtual public A { };  // virtual inheritance
class C : virtual public A { };  // virtual inheritance
class D : public B, public C { };  // D has only ONE copy of A

      Key points:

      • Use virtual keyword when inheriting from the common base class
      • Ensures only one instance of the base class exists in the final derived class
      • Eliminates ambiguity when accessing base class members
      • The most derived class (D) is responsible for initializing the virtual base class (A)

      Usage:

      D obj;
obj.value = 42;  // No ambiguity - only one 'value' exists

      Without virtual inheritance, you'd need obj.B::value or obj.C::value to resolve ambiguity. - Access Modifiers (by section): public, private, protected.

    • ​public: Members are accessible from anywhere.

    • ​private: Members are only accessible from within the class itself.
    • ​protected: Members are accessible from within the class and by its derived classes.
    • Attention: These are compile-time checks. Once compiled, it might be possible to circumvent them (e.g., via pointer manipulation), but this is bad practice.

    • Virtual Functions / Methods (Page 14):

    • Declared with the virtual keyword in the base class.

    • Allow derived classes to provide their own specific implementation (override).
    • Enables polymorphism (dynamic dispatch).

    • Pure Virtual Functions / Methods (Page 14):

    • ​virtual void functionName() = 0;​

    • A virtual function that the base class declares but does not define.
    • Makes the class an abstract class (cannot be instantiated directly).
    • Derived classes must implement all pure virtual functions to become concrete (instantiable). Equivalent to abstract methods in other languages.
    • Constructors and Destructors (Page 14): Essential parts of class lifecycle management.

    • Dividing Declarations and Definitions (Page 14):

    • General practice: Class declaration (name, member signatures) in a header file (.hpp or .h).

    • Member function definitions in a C++ source file (.cpp).
    • Exception: Template classes are usually fully defined in header files.

    • Inheritance Access Restriction (Page 14): When a class Derived inherits from Base, the type of inheritance can be specified:

    • ​class Derived : public Base { ... }; (Public inheritance): public members of Base are public in Derived, protected are protected. Most common.

    • ​class Derived : protected Base { ... }; (Protected inheritance): public and protected members of Base become protected in Derived.
    • ​class Derived : private Base { ... }; (Private inheritance): public and protected members of Base become private in Derived. (Is-implemented-in-terms-of relationship).

10. C++: Inheritance and Polymorphism Example (Page 14-15, 17)

  • Abstract Class ​Figure​ and Derived Classes ​Circle​​ , ​Rectangle​ (Page 14, 17):

  • ​figure.hpp (Conceptual, based on page 14 & 17 structure)

    // figure.hpp
#ifndef FIGURE_HPP
#define FIGURE_HPP

class Figure {
public:
    // Pure virtual functions make Figure an abstract class
    virtual void draw() = 0;
    virtual float area() = 0; // Added from page 17 example
    virtual ~Figure() {} // Good practice to have a virtual destructor in base class

protected: // Accessible by derived classes
    int center_x;
    int center_y;
    Figure(int x, int y) : center_x(x), center_y(y) {} // Constructor for derived classes
};

class Circle : public Figure {
public:
    Circle(int x, int y, float r);
    void draw() override; // 'override' is good practice
    float area() override;

private:
    float radius;
};

class Rectangle : public Figure {
public:
    Rectangle(int x, int y, int w, int h);
    void draw() override;
    float area() override; // Assuming Rectangle would also have area

private:
    int width;
    int height;
};
#endif // FIGURE_HPP
    - ​circle.cpp (from page 17, extended for area)

    // circle.cpp
#include "figure.hpp" // Contains Figure and Circle declarations
#include <iostream>
#define PI 3.14159265358979323846

Circle::Circle(int x, int y, float r) : Figure(x, y), radius(r) {
    // center_x = x; // Done by Figure constructor
    // center_y = y; // Done by Figure constructor
}

void Circle::draw() {
    std::cout << "Circle@(" << center_x << ", " << center_y
              << ") with radius " << radius << std::endl;
}

float Circle::area() {
    return PI * radius * radius;
}
    - Polymorphism Example (Page 15):

// On stack:
Circle c = Circle(0, 0, 1);
Rectangle r = Rectangle(0, 0, 1, 1);
// c.draw(); r.draw(); // Would call respective draw methods

// On heap, using base class pointers:
Figure* figures[2] = {new Circle(0,0,1), new Rectangle(0,0,1,1)};
// figures[0]->draw(); // Calls Circle::draw()
std::cout << figures[1]->draw() << std::endl; // Calls Rectangle::draw()
                                             // (std::cout wrapping draw() is unusual if draw is void,
                                             // assuming it's for illustrative purpose of calling draw)
delete figures[0];
delete figures[1];
- Answers to Questions on Page 15:

  1. Why an array of pointers to ​Figure​​ ?

    • Polymorphism: Allows treating different derived types (Circle, Rectangle) uniformly through the base class (Figure*) interface. The correct draw() is called at runtime (dynamic dispatch).
    • Heterogeneous Collection: Can store pointers to different objects that share a common base class in the same collection.
    • Dynamic Allocation: Objects are created on the heap (new), and pointers manage them. This avoids "object slicing" which would occur if you stored derived objects directly in an array of Figure (only the Figure part would be copied).

    • We cannot define a variable of class ​Figure​​ , why?

    • ​Figure is an abstract class because it has at least one pure virtual function (virtual void draw() = 0;). Abstract classes cannot be instantiated directly.

    • Which ​draw​ is being called in line 6 (​​figures[1]->draw()​ ​ )?

    • ​Rectangle::draw() is called. This is due to dynamic dispatch enabled by virtual functions. The program determines at runtime that figures[1] points to a Rectangle object.

    • What happens with ​c​ and ​r​ (stack-allocated objects)?

    • They are allocated on the stack. Their memory is automatically reclaimed when they go out of scope (e.g., at the end of the function where they are declared). Destructors are called automatically.

11. C++: Copy Constructor and Assignment Operator (Page 17-20)

  • Copy Constructor (Page 17, 19-20):

  • Definition: A special constructor used to create a new object as a copy of an existing object of the same class.

  • Syntax: Typically ClassName(const ClassName& other);​

  • Why by reference? (​​const ClassName& other​​ ): (Page 17)

    • If it took the argument by value (ClassName other), calling the copy constructor would require making a copy of other to pass it, which would require calling the copy constructor again, leading to infinite recursion. Pass-by-reference avoids this. const is used because the copy constructor usually shouldn't modify the source object.
    • Implicitly Defined: If not user-defined, the compiler provides a default one that performs member-wise copy.
    • When Invoked (Example from Page 20):

    Point p1(3, 4);
Point p2 = p1; // Copy constructor invoked to initialize p2 from p1
// Also invoked when:
// - Passing an object by value to a function
// - Returning an object by value from a function
    - Example (​​Point​ class, Page 19):

    #include <iostream>
class Point {
private:
    int x, y;
public:
    // (1) Constructor
    Point(int x_val, int y_val) : x(x_val), y(y_val) {}
    // (2) Copy Constructor
    Point(const Point& other) : x(other.x), y(other.y) {
        std::cout << "Copy constructor called\n";
    }
    int getX() const { return x; }
    int getY() const { return y; }
};

int main() {
    Point p1(3, 4);
    std::cout << "p1: (" << p1.getX() << ", " << p1.getY() << ")\n";
    Point p2 = p1; // Invokes copy constructor
    std::cout << "p2 (after copy): (" << p2.getX() << ", " << p2.getY() << ")\n";
    return 0;
}
    - Assignment Operator (​ ​=​ ​ ) for Objects (Page 18):

  • Definition: An operator used to copy the contents of an existing object to another existing object.

  • Syntax (if overloaded): ClassName& operator=(const ClassName& other);​
  • Default Behavior (Shallow Copy): If not user-defined, the compiler provides a default assignment operator that performs member-wise copy. This is a shallow copy.

  • Attention (Shallow Copy Issues): If a class contains pointers to dynamically allocated memory:

    • Dangling Pointer: If one object is destroyed and deallocates the memory, the other object's pointer now dangles.
    • Double Free: If both objects' destructors try to delete (free) the same shared memory, it leads to a crash or undefined behavior.
    • Solution: Implement a custom assignment operator (and copy constructor, and destructor - "Rule of Three/Five") to perform a deep copy if the class manages raw pointers to resources.
    • ​​delete[]​ for Arrays (Page 18):

  • Definition: Operator used to deallocate memory that was allocated for an array using new SomeType[].

  • Attention:

    • It ensures that the destructor is called for each element in the dynamically allocated array before the memory is freed.
    • Using delete (non-array version) on memory allocated with new[] is undefined behavior.
    • Using delete[] on memory allocated with new (single object) is undefined behavior.
    • Example (Page 18):
    #include <iostream>
using namespace std;
struct my_type {
    ~my_type() { cout << "destructor" << endl; } // Destructor
};

int main() {
    my_type v[5]; // 5 objects on stack. Destructors called automatically when v goes out of scope (5 times).

    my_type* array = new my_type[4]; // 4 objects on heap.
    delete[] array; // Calls destructor for each of the 4 objects, then frees memory. Output: 4 "destructor" lines.

    cout << "delete finished" << endl;
    return 0; // v goes out of scope here. Output: 5 "destructor" lines.
}
// Expected Output Order:
// destructor (from delete[] array)
// destructor (from delete[] array)
// destructor (from delete[] array)
// destructor (from delete[] array)
// delete finished
// destructor (from v[4] going out of scope)
// destructor (from v[3] going out of scope)
// ...
// destructor (from v[0] going out of scope)

12. C++: Strings (Page 18-19)

  • Two Kinds of "Strings":

  • C-style strings (Page 19):

    • ​char pointer (char*) or char array (char[]) ending with a null terminator (\0).
    • Mutability: Mutable if defined on the stack or heap.
    • String Literals: e.g., "Hello World". These are typically stored in a read-only section of the executable and are not mutable. Attempting to modify a string literal results in undefined behavior.

    • ​​std::string​ (C++ class - Page 19):

    • A class from the C++ Standard Library (<string>).

    • Represents string objects that are mutable (can be changed after creation).
    • Manages its own memory, generally safer and easier to use than C-style strings.
    • Key Points/Attention:

  • ​​operator<<​ (Output Stream): Overloaded to work with both std::string objects and C-style strings (char*).

  • ​​printf​​ : Expects C-style strings for the %s format specifier.

    • To print a std::string with printf, use its .c_str() method: printf("%s\n", my_std_string.c_str());​
    • Passing a std::string object directly to printf %s (without .c_str()) is undefined behavior (as shown by garbage output My first string is @T� on page 19).
    • Example (Page 19):
#include <iostream>
#include <string> // For std::string
#include <cstdio> // For printf

using namespace std;

int main() {
    string s1 = "Hello world!"; // std::string object
    cout << s1 << endl;         // Works: Hello world!

    const char * s2 = "Goodbye!"; // C-style string (pointer to literal)
    cout << s2 << endl;           // Works: Goodbye!

    // printf("My first string is %s\n", s1); // WRONG: s1 is std::string, not char*
                                             // Output on slide: My first string is @T�
    printf("My second string is %s\n", s2);  // CORRECT: s2 is char*
                                             // Output: My second string is Goodbye!
    printf("The correct way to print my first string is %s\n", s1.c_str()); // CORRECT
                                                                          // Output: The correct way to print my first string is Hello world!
    return 0;
}

13. Abstract Data Type (ADT) - General Concept

  • Definition:

  • An ADT is a description of:

    1. A collection of values.
    2. The operations that can be performed on those values.

    3. Crucially, an ADT does not define the technical details of:

    4. How the values are represented internally (data structure).

    5. How the operations work on these internal representations (algorithm implementation).
    6. It focuses on what an ADT is and what it can do, not how it does it.
    7. Examples of Common ADTs:

  • Lists:

    • Description: A linearly organized collection of values.

    • Main Operations:

    • Creation

    • Insertion/Deletion/Retrieval: e.g., get(position), elementAt(position)​
    • Properties: empty, size, contains.

    • Sets:

    • Description: An unordered collection of different (unique) elements.

    • Main Operations:

    • Creation

    • Insertion/Deletion
    • Union/Intersection
    • Properties: empty, size, contains, is a sub set.

    • Stacks:

    • Description: A linearly organized collection of values (similar to a list). It's a FILO (First In, Last Out) collection.

    • Main Operations:

    • Creation

    • Push/Pop
    • Properties: empty, size.

    • Queues:

    • Description: A linearly organized collection of values (similar to a list). It's a FIFO (First In, First Out) collection.

    • Main Operations:

    • Creation

    • Enqueue/Dequeue
    • Properties: empty, size.

14. Data Abstractions in C

  • Core Principle: The Abstract Data Type (interface) and its implementation should be separated.

  • Structure:

  • ADT Definition (Header file - ​.h​​ ):

    • Types: Declarations, NOT Definitions.

    • Purpose: To declare the existence of the type without revealing its internal structure. This is crucial for information hiding.

    • Example: struct List; typedef struct List * list; (using an incomplete type).

    • Operations: Declarations (Function Prototypes), NOT Definitions.

    • Purpose: To define the functions that allow users to create, modify, or inspect ADT values.

    • Example: extern list list_new(void);​

    • ADT Implementation (Source file - ​.c​​ ):

    • Contains the actual definitions of the types (e.g., struct List { /* members */ };) and the implementations of the functions.

    • Achieving Abstraction in C (Relies on Informal Conventions):

  • Key Distinction: C lacks built-in language constructs like public/private (as in C++/Java) to strictly enforce information hiding.

  • Mechanisms:

    1. Header (​ ​.h​​ ) vs. Source (​ ​.c​​ ) File Separation: Declarations in .h, definitions in .c.
    2. Incomplete Types: Using typedef struct MyADT MyADT_t; in the header. The compiler enforces non-access to members of incomplete types if only the header is included.
    3. ​​static​ Keyword: Used for functions and variables within a .c file to limit their scope and make them "private" to that implementation file.
    4. Characteristics:

  • Data is separated from operations (typical of procedural programming).

  • Difficult to define truly generic structures without void* and manual type casting, or complex macro usage.
  • Example (List ADT in C - from slide snippets):

// In list.h (Interface)
struct List; // Forward declaration of the struct
typedef struct List * list; // list is a pointer to an opaque struct List

extern list list_new(void);
extern unsigned int list_size(const list const lst);
extern boolean list_is_empty(const list const lst);
extern boolean list_add(list const lst, void * e); // void* for generic elements
extern void* list_at(const list const lst, const int at);
extern void* list_del_at(const list const lst, const int at);
extern void list_drop(list lst); // Frees memory
// ... and list_deep_equals
- Points to Consider (from slide):

  • Can we have multiple implementations of these types and functions? (Yes, by linking different .c files that implement the .h interface).
  • Can we use multiple implementations at the same time? (Yes, if they are carefully designed, e.g., by different naming or if the interface allows for context).
  • Why choose specific names like list_size, list_drop? (Convention, clarity).
  • Can we have a "List of T" where T is a specific type (strong typing)? (Not directly in C like in C++ templates. Achieved via void* and requires careful casting and type management by the user, or by using macros to generate type-specific versions). The slide answers "Yes, Yes, No" to these points in order, implying "No" for strongly-typed generic lists without extra work.

15. Data Abstractions in Object-Oriented Languages (OOP)

  • Core Idea: The ​Class​​

  • Defines a new type.

  • Operations (methods) are defined within the class (both declarations and definitions).

    • Create/Destroy Class values (Constructors/Destructors).
    • Modify Class values.
    • Check properties in Class values.
    • Objects: Instances of a class.
    • Conventions: Follow formal conventions, usually ClassName(arguments) for instantiation.
    • Key Difference from Procedural (like C ADTs):

  • Encapsulation: Data and operations are not separated. Each object encapsulates both its data (attributes) and the operations (methods) that can act on that data.

  • Declarations vs. Definitions (in OOP context):

  • Declarations: Specifying the name of the operation, its arguments (inputs), and its return type. (The "what").

  • Definitions: Providing the actual code or implementation for that operation. (The "how-to").

  • Fundamental Characteristics of Object-Oriented Programming (OOP):

  • Abstraction: Offers powerful mechanisms for defining data abstractions (classes).

  • Encapsulation:

    • An evolution from separating data structures and algorithms.
    • Operations (methods) are associated with the data structures they operate on.
    • Information Hiding: If modules (classes) are appropriately defined, data structures should only be manipulated through allowed operations (public methods).
    • Benefits: Modularity and reuse can be significantly improved compared to procedural programming if data abstractions are appropriate.
    • ADTs in OOP (Conceptual Diagram):

  • An ADT (e.g., an abstract class or interface) defines the conceptual type and its operations.

  • ​ImplementationA (a concrete class) is a type of ADT.
  • ​ImplementationB (another concrete class) is a type of ADT.
  • A value/object of ImplementationA is a value/object of the ADT.
  • Example: A LinkedList object is a List and contains or is composed of _Node objects.

16. C++ Templates (Generic Programming)

  • Purpose: Allow writing generic classes and functions that can operate on different data types without needing to rewrite the code for each type.
  • How Templates Work (​​print​ example):
template <typename T> // or template <class T>
void print(const T value) {
    std::cout << value << std::endl;
}
// Usage:
// print<int>(5);
// print<char>('h');
// print<std::string>("Hello?");
// int values[3] = {1, 2, 3}; print<int[]>(values); // This specific example for arrays is problematic; typically needs specialization or pointer.
  • Compilation-Time Instantiation: A different version of print (e.g., print_for_int, print_for_char) is created by the compiler for each specific type used with the template during compilation.

  • Advantage: Static Polymorphism:

    • The correct version of the function is determined at compile time.
    • No runtime overhead to decide which function to call.
    • Can lead to very efficient code, often as fast as manually writing separate functions.

    • Advantage: Type Safety:

    • If you try to use print with a type T that doesn't support the << operator with std::cout, you get a compile-time error, not a runtime crash.

    • Disadvantage: "Duck Typing" (Implicit Interface):

    • The template print doesn't explicitly state "T must be printable via <<". It just tries to use std::cout << value;.

    • If value (of type T) can be used with << (if it "quacks like a duck"), it compiles.
    • If not, the error message can be long and confusing because it happens deep inside the template code during instantiation.
    • The requirement (T must support operator<<) is an implicit interface.
    • Fixing "Duck Typing" with C++20 Concepts:

  • Concepts allow you to explicitly define the requirements for a template parameter.

// Hypothetical C++20 example
concept Printable = requires(T a) { std::cout << a; }; // Define a concept
template <Printable T> // Now T MUST satisfy the Printable concept
void print(const T value) {
    std::cout << value << std::endl;
}
- ​​typename​ vs. ​class​ in Template Parameters:

  • ​template <typename T>​
  • ​template <class T>​
  • Functionally Identical: The language makes no difference between them in this context.
  • Intention: class might be used by a developer to hint that T is expected to be a class type, while typename is more general (can be a primitive type, class type, etc.). typename is often preferred for its generality.

  • C++ Stack Class Template Example:

  • Declaration (e.g., in ​Stack.h​​ ):

    template <class T> // 1. Template Declaration
class Stack {      // 2. Class Name
public:            // 3. Public Interface
    Stack(int s = 10);    // 4. Constructor (default size 10)
    ~Stack() { delete[] stackPtr; } // 5. Destructor (cleans up memory) - simplified from slide for []
    bool push(const T& item);     // 6. Push operation
    bool pop(T& item);            // 7. Pop operation (item is an out-parameter)
                                  // (Slide image had a typo for pop comment, code is T&)
    int isEmpty() const { return top == -1; }      // 8. Check if empty
    int isFull() const { return top == size - 1; } // 9. Check if full (slide had size-1 logic)
private:           // 10. Private Members
    int size;          // 11. Maximum capacity
    int top;           // 12. Index of top element (-1 if empty)
    T* stackPtr;       // 13. Pointer to array storing elements
};
    - Implementation (e.g., in ​Stack.cpp​ or ​Stack.tpp​​ ):

    // Constructor
template <class T>
Stack<T>::Stack(int s = 10) {
    top = -1;             // 1. Initialize top
    this->size = s;       // 2. Store provided size
    stackPtr = new T[s];  // 3. Allocate memory
}

// Push
template <class T>
bool Stack<T>::push(const T& item) {
    if (!isFull()) {
        stackPtr[++top] = item; // 1. Check not full, 2. Increment top, store item
        return true;            // 3. Push successful
    }
    return false;               // 4. Push unsuccessful (stack full)
}

// Pop
template <class T>
bool Stack<T>::pop(T& popValue) { // popValue is an out-parameter
    if (!isEmpty()) {
        popValue = stackPtr[top--]; // 1. Check not empty, 2. Get item, then decrement top
        return true;                // 3. Pop successful
    }
    return false;                   // 4. Pop unsuccessful (stack empty)
}
    - Main function example usage:

    #include <iostream> // For std::cout, std::endl
// Assuming Stack class definition is available
typedef Stack<float> FloatStack; // Creates an alias

int main() {
    FloatStack fs(5); // Create a stack of floats with capacity 5
    float f = 1.1f;
    std::cout << "Pushing elements onto fs" << std::endl;
    while (fs.push(f)) {
        std::cout << f << ' ';
        f += 1.1f;
    }
    std::cout << "\nStack Full.\n";
    std::cout << "Popping elements from fs\n";
    while (fs.pop(f)) { // f is reused to store popped value
        std::cout << f << ' ';
    }
    std::cout << "\nStack Empty\n" << std::endl;
    return 0;
}
    - Generic Functions as Arguments (Pre-C++20 Concepts way to add restrictions):

  • Templates themselves don't directly provide restrictions (like Java's extends Comparable).

  • One option: Pass certain generic functions (operations) as extra arguments (e.g., a comparison function).

  • Example:

    #include <iostream>
#include <cassert> // For assert

// Function pointer type alias for a function that takes two T's and returns a T
template<typename T>
using t_max_func_ptr = T (*)(T, T);

int max_i(int a, int b) { return a > b ? a : b; }
float max_f(float a, float b) { return a > b ? a : b; }

template<typename T>
T maximum(const int size, T values[], t_max_func_ptr<T> max_op) {
    assert(size > 0);
    T current_max = values[0];
    for (int i = 1; i < size; i++) {
        current_max = max_op(current_max, values[i]);
    }
    return current_max;
}

int main() {
    int int_values[] = {1, 2, 3, 4};
    float float_values[] = {2.3f, 8.7f, -1.4f, 0.3f};

    std::cout << "maximum int is: " << maximum<int>(4, int_values, max_i) << std::endl;
    std::cout << "maximum float is: " << maximum<float>(4, float_values, max_f) << std::endl;
    return 0;
}
    • Here, t_max_func_ptr<T> max_op (or t_max<T> max on slide) is the key: it takes a function pointer argument.
    • C++20 Concepts (A better way for restrictions):

  • More akin to Java's generic restrictions.

  • Requires compiler flag like g++ -std=c++20.

  • Example:

    #include <iostream>
#include <concepts> // For std::same_as

// Concept: T is Comparable if it has a 'compares_to' method taking another T and returning int
template <typename T>
concept Comparable = requires(T a, T b) {
    { a.compares_to(b) } -> std::same_as<int>;
};

class Integer {
private:
    int value;
public:
    Integer(int val) : value(val) {}
    int compares_to(Integer other) const { // Added const for good practice
        // A typical comparison:
        if (value < other.value) return -1;
        if (value > other.value) return 1;
        return 0;
        // Slide had: return value - other.value; which also works if difference semantics are okay
    }
    int getValue() const { return value; } // Helper for printing
};

// Function constrained by the Comparable concept
template<Comparable T>
int comparing(T a, T b) {
    return a.compares_to(b);
}

int main() {
    Integer a = Integer(3);
    Integer b = Integer(2);
    int res = comparing(a, b); // This will compile
    std::cout << "Comparing a(3) and b(2): " << res << std::endl; // Expected: 1 (or positive)
    return 0;
}
    - This is similar to Java interfaces:

    /*
interface Comparable<T> {
    int compareTo(T o);
}

class MyInteger implements Comparable<MyInteger> {
    int value;
    public MyInteger(int v) { value = v; }
    @Override
    public int compareTo(MyInteger other) {
        return Integer.compare(this.value, other.value);
    }
}

// Generic function in Java
// <T extends Comparable<T>> int someGenericFunction(T obj1, T obj2) {
//     return obj1.compareTo(obj2);
// }
*/

17. Metaprogramming with Templates

  • Definition: Using templates to perform computations or generate code at compile time.

  • Key Points:

  • Templates are not the same as preprocessor directives (like #define).

  • Templates are resolved by the compiler, not the preprocessor.
  • Template instances are generated during compilation time depending on the template arguments.
  • Once the executable is compiled, these compile-time generated instances are already available without any extra runtime steps for their generation.
  • All instances generated (e.g., specific values computed) are also accessible.
  • Example 1: ​Counter​ (Compile-time recursion)

#include <iostream>

// 1. General Template Definition (the "recursive step")
template<unsigned int x>
struct Counter {
    // The 'counter' for 'x' is 1 PLUS the 'counter' for 'x-1'
    static const int counter = 1 + Counter<x - 1>::counter;
};

// 2. Template Specialization (the "base case" for the recursion)
template<> // This is a full specialization
struct Counter<0> { // Specifically for when x IS 0
    // The 'counter' for 0 is defined as 0
    static const int counter = 0;
};

int main() {
    // 3. Usage: Requesting Counter<42>::counter
    // This value (42) is computed at compile time.
    std::cout << Counter<42>::counter << std::endl; // Outputs 42
    return 0;
}
- Template Specialization (General Definition):

  • Allows defining different implementations of a template for specific data types or combinations of data types.

  • Example: ​print​ specialized for ​int​​

    #include <iostream>
// #include <bits/stdc++.h> // Generally discouraged for production code
using namespace std; // Also generally discouraged in headers or globally in .cpp

// Generic template
template <typename T>
void print(T value) {
    cout << value;
}

// Template specialization for int
template <>
void print(int value) { // Note: void print<int>(int value) is also valid syntax for specialization
    cout << "Value: " << value;
}

int main() {
    print(3);    // Uses specialized version: Output: Value: 3
    cout << endl;
    print("a");  // Uses generic version: Output: a
    cout << endl;
    // Output from slide:
    // Value: 3
    // a
    return 0;
}
    - Example 2: Fibonacci (Compile-time vs. Runtime)

  • Runtime Fibonacci (fibonacci_function.cpp):

    #include <iostream>
unsigned long long fibonacci_func(int v) { // Renamed to avoid clash
    if (v == 0) return 0;
    if (v == 1) return 1;
    return fibonacci_func(v - 2) + fibonacci_func(v - 1);
}
/* // main from slide
int main(const int argc, const char ** const argv) {
    int f = 35;
    std::cout << "My greatest fibonacci: " << fibonacci_func(f) << std::endl;
    // The loop with fibonacci(f-1) seems to be a busy-wait or a check, not directly related to calculation
    for (int i = 0; i < 200; i++) {
        if (fibonacci_func(f - 1) >= 0) { // This will always be true for f=35
            std::cout << '.';
        }
    }
    std::cout << std::endl;
    return 0;
}
*/
    - Compile-time Fibonacci (fibonacci.cpp - template metaprogramming):

    #include <iostream>

template <unsigned long long n>
struct Fibonacci {
    // enum trick for compile-time constants before C++11 static constexpr
    enum : unsigned long long { result = Fibonacci<n - 1>::result + Fibonacci<n - 2>::result };
    // With C++11 or later:
    // static constexpr unsigned long long result = Fibonacci<n - 1>::result + Fibonacci<n - 2>::result;
};

template<>
struct Fibonacci<0> {
    enum : unsigned long long { result = 0 };
    // static constexpr unsigned long long result = 0;
};

template<>
struct Fibonacci<1> {
    enum : unsigned long long { result = 1 };
    // static constexpr unsigned long long result = 1;
};

int main() {
    // Fibonacci<35>::result is computed AT COMPILE TIME.
    std::cout << "My greatest fibonacci: " << Fibonacci<35>::result << std::endl;

    // The loop for Fibonacci<34>::result is also a compile-time check
    // The compiler knows Fibonacci<34>::result, so the if is constant.
    for (int i = 0; i < 200; i++) {
        if (Fibonacci<34>::result >= 0) { // This is a compile-time constant check
            std::cout << '.';
        }
    }
    std::cout << std::endl;
    return 0;
}

18.Syntax(Struct, enumer, pass, argument, array, type safety, new and delete)

Type Safety in C++

C++ is a strongly typed language. It means that all variables' data type should be specified at the declaration, and it does not change throughout the program. Moreover, we can only assign the values that are of the same type as that of the variable.

Note that <<endl flushes the output buffer, but \n not

Function in C++

1. Pass by Value

In pass by value method, a variable's value is copied and then passed to the function. As the result, any changes to the parameter inside the function will not affect the variable's original value in the caller.

2. Pass by Reference

In pass-by-reference method, instead of passing the value of the argument, we pass the reference of an argument to the function. This allows the function to change the value of the original argument.

3. Pass by Pointer

The pass-by-pointer is very similar to the pass-by-reference method. The only difference is that we pass the raw address of the argument as the parameter to the function instead of reference.

#include <iostream>
#include <cassert>

static int foo(int a);
static int bar(int * a);
static int fubar(int& a);

int main() {
    int my_var = 9;
    printf("foo(my_var): %d\n", foo(my_var));
    printf("bar(&my_var): %d\n", bar(&my_var));
    printf("fubar(my_var): %d\n", fubar(my_var));
    printf("my_var: %d\n", my_var);
    return 0;
}

static int foo(int a) {
    return a * 10;
}

static int bar(int * a) {
    assert(a != nullptr);
    return *a * 100;
}

static int fubar(int& a) {
    a = 1;
    return a * 1000;
}

Default Argument

#include <iostream>
using namespace std;

// Function with default height 'h' argument
double calcArea(double l, double h = 10.0) {
//Note that default parameter must start from right
    return l * h;
}

int main() {
    cout << "Area 1:  "<< calcArea(5)
    << endl;

    cout << "Area 2: "<< calcArea(5, 9);
    return 0;
}

Array

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {2, 4, 8, 12, 16};

    // Traversing and printing arr
    for (int i = 0; i < 5; i++)
        cout << arr[i] << " ";

    return 0;
}

Pointer

#include <bits/stdc++.h>
using namespace std;

int main() {
    int var = 10;

    // Store the address of 
    // var variable
    int* ptr = &var;

    // Access value using (*)
    // operator
    cout << *ptr;
    return 0;
}

Structures

C++ Structures are used to create user defined data types which are used to store group of items of different data types

#include <iostream>
using namespace std;

// Class like structure
struct Point {
private:
    int x, y;
public:

    // Constructors
    Point(int a, int b) {
        x = a;
        y = b;
    }

    // Member function
    void show() {
        cout << x << " " << y << endl;
    }

    // Destructor
    ~Point() {
        cout << "Destroyed Point Variable" << endl;
    }
};

int main() {

    // Creating Point variables using constructors
    Point s1;
    Point s2(99, 1001);

    s1.show();
    s2.show();
    return 0;
}

typedef

In C++, typedef is used to create an alias for an existing variable. Similarly, with structures, typedef creates an alias for the original name of the structure.

#include <iostream>
using namespace std;

typedef struct GeeksforGeeks {
    int x, y;

// Alias is specified here
} GfG;

int main() {

    // Using alias
    GfG s = { 0, 1 };
    cout << s.x << " " << s.y << endl;
    return 0;
}

Enumeration

Easy example, By default, the first name in an enum is assigned the integer value 0, and the subsequent ones are incremented by 1.

#include <iostream>
using namespace std;

// Defining enum
enum direction {
    EAST, NORTH, WEST, SOUTH
};

int main() {

    // Creating enum variable
    direction dir = NORTH;
    cout << dir;
    return 0;
}

Another example

#include <iostream>
using namespace std;

// Define the enum class
enum class Day { Sunday = 1, Monday, Tuesday,
                Wednesday, Thursday, Friday, 
                Saturday };

int main() {

    // initializing
    Day today = Day::Thursday;

    // Print the enum
    cout << static_cast<int>(today);
    return 0;
}

New and delete operator

#include <iostream>
using namespace std;

int main() {
    int *ptr = NULL;

    // Request memory for integer variable
    // using new operator
    ptr = new int(10);
    if (!ptr) {
        cout << "allocation of memory failed";
        exit(0);
    }

    cout << "Value of *p: " << *ptr << endl;

    // Free the value once it is used
    delete ptr;

    // Allocate an array
    ptr = new int[3];
    ptr[2] = 11;
    ptr[1] = 22;
    ptr[0] = 33;
    cout << "Array: ";
    for (int i = 0; i < 3; i++)
        cout << ptr[i] << " ";

    // Deallocate when done
    delete[] ptr;

    return 0;
}

‍