Vectors / Operator Overloading

Outline

  • Operator Overloading

  • Friend Function

  • Vector Class

Operator Overloading

  • Definition: The ability of the programmer to redefine the way operators function for user-defined types (classes). This allows operators like +, -, *, ==, <<, >>, etc., to behave meaningfully when applied to class objects, just as they do with built-in data types.

  • Purpose: Provides convenient, intuitive notation for object behavior, making code more readable and allowing objects to be treated similarly to built-in types. It hides the complexity of underlying function calls.

Explanation of Operator Overloading

  • Operator overloading allows the use of standard operator symbols to define special member functions or global functions that operate on objects of a class. This mechanism enables syntactic sugar for complex operations.

  • Example of Usage with Built-in Types: - Declaration:

    int i, j, k; // integers
float m, n, p; // floats
k = i + j; // integer addition and assignment
p = m + n; // floating addition and assignment

  • In C++, the compiler provides default overloads for operators such as +, -, *, / for built-in types. For instance: - k = i + j performs integer addition, whereas p = m + n performs floating-point addition. The compiler chooses the correct version based on operand types.

  • Custom Object Example: - For user-defined types (like Complex), we can use operator functions:

    Complex a, b, c;
c = a + b; // Without overloading, this would be an error or require a method like c = a.add(b);
Operator Overloading Syntax

  • Syntax Format: - return_type operator@(argument-list)

    • operator is a function keyword indicating an operator overload and @ can be any overloadable operator such as +, -, =, [], (), <<, >>, etc. (Not all operators can be overloaded; e.g., . .* :: ?: cannot be overloaded).

    • The argument-list depends on whether the operator is a member function (unary operators take no explicit arguments, binary operators take one) or a non-member/friend function (unary operators take one argument, binary operators take two).

Examples

  • operator+: Overloads the addition operator.

  • operator-: Overloads the subtraction operator.

  • operator*: Overloads the multiplication operator.

  • operator/: Overloads the division operator.

  • operator[]: Overloads the subscript operator, often used for array-like access.

  • operator(): Overloads the function call operator, allowing objects to be treated like functions.

Implementing Operator Overloading

  • Two main ways: - As member functions

    • As non-member (Friend) functions

Member Functions

  • Implementation as a Member Function: An operator overload implemented as a member function acts on the object for which it is called (the this object) and takes the right-hand operand(s) as explicit arguments. The left-hand operand is implicitly *this.

class Complex {
private:
    double _real;
    double _imag;
public:
    // Constructor and other members
    Complex(double r = 0.0, double i = 0.0) : _real(r), _imag(i) {}

    Complex operator+(const Complex &op) const { // 'const' correctly applied here
        double realResult = _real + op._real;
        double imagResult = _imag + op._imag;
        return Complex(realResult, imagResult);
    }
    // ...
};

  • Resulting call: c = a + b; translates to c = a.operator+(b);. This is suitable for operations where the left operand is an object of the class, like complex_obj + other_complex_obj.

Non-member Functions

  • Implementation as Non-member Function: An operator overload implemented as a non-member function (also called a "free function") takes all its operands as explicit arguments. It does not have a this pointer inherently.

class Complex {
private:
    double _real;
    double _imag;
public:
    Complex(double r = 0.0, double i = 0.0) : _real(r), _imag(i) {}
    double real() const { return _real; } // Accessors needed for private data
    double imag() const { return _imag; } //
    // ...
};

Complex operator+(const Complex &op1, const Complex &op2) { // Takes both operands explicitly
    double realResult = op1.real() + op2.real();
    double imagResult = op1.imag() + op2.imag();
    return Complex(realResult, imagResult);
}

  • This allows c = a + b; to translate to c = operator+(a, b);. This approach is necessary when the left-hand operand is not an object of the class (e.g., std::cout << myComplexObject). If the function needs access to private members, it must be declared as a friend.

Friend Functions

  • Implementation as a Friend Function: A friend function is a non-member function that is granted special access rights to the private and protected members of a class. It combines the explicit operand handling of a non-member function with the direct data access of a member function.

class Complex {
private:
    double _real;
    double _imag;
public:
    Complex(double r = 0.0, double i = 0.0) : _real(r), _imag(i) {}
    // Declare the operator+ as a friend function
    friend Complex operator+(const Complex &op1, const Complex &op2);
    // ...
};

// Definition of the friend operator outside the class, without 'Complex::'
Complex operator+(const Complex &op1, const Complex &op2) {
    // Can directly access private members _real and _imag
    double realResult = op1._real + op2._real;
    double imagResult = op1._imag + op2._imag;
    return Complex(realResult, imagResult);
}

  • Equivalent operation as above: c = a + b; translates to c = operator+(a, b);. Friend functions are often chosen for binary operators where implicit type conversion on the left-hand side is desired or for stream insertion/extraction operators (<<, >>) where the left operand is typically an ostream or istream object, not an object of Complex.

Ordinary Member Functions, Free Functions and Friend Functions

  • Characteristics:

    1. Member Functions:

    • Access to the private members of the class definition.

    • Scope of the function resides within the class.

    • Must be invoked on an object of the class (e.g., obj.memberFunction()).

    • Have an implicit this pointer.

    1. Free Functions (Non-member):

    • No direct access to private members (require public accessors).

    • Global scope or namespace scope.

    • Invoked like regular functions (e.g., freeFunction(obj)).

    • No this pointer.

    1. Friend Functions:

    • Access to the private members of the class definition (granted by the friend declaration).

    • Global scope or namespace scope, but declared within the class for access rights.

    • Invoked like regular functions (e.g., friendFunction(obj)).

    • No this pointer.

What is a ‘Friend’?

  • Definition: Friend declarations introduce enhanced access rights for functions or other classes.

    • Allows a function or another class to access non-public (private or protected) members of the class that declares it as a friend.

    • Access is unidirectional: If class B is a friend of class A, class B can access A’s non-public members, but A cannot automatically access B’s non-public members unless A is also declared as a friend in B. This breaks strict encapsulation for specific, declared entities.

Implications of Using 'Friend'

  • Use of friends can enhance access efficiency to data members compared to using public accessor (getter) or mutator (setter) function calls, as it bypasses the function call overhead for direct member access.

  • Can help operator functions directly access private data members, which is particularly useful for binary operators where either operand might not be the class object itself (like ostream in operator<<).

  • However, overuse can lead to issues such as defeating encapsulation (making private data less private) and data hiding, making code harder to maintain, debug, and understand as dependencies become less clear. It represents a controlled breach of encapsulation and should be used judiciously.

In-class Practice

  • Define a complex class and implement the addition as a member function and subtraction as a friend function.

class Complex {
private:
    double real;
    double imag;
public:
    // Constructor
    Complex(double r = 0.0, double i = 0.0) : real(r), imag(i) {}

    // Member function for Overloading +
    // 'const' is important here, indicates the function does not modify the object it's called on.
    Complex operator+(const Complex& other) const {
        return Complex(real + other.real, imag + other.imag);
    }

    // Friend function for Overloading - (declaration inside the class)
    friend Complex operator-(const Complex& c1, const Complex& c2);

    // Display function
    void display() const { std::cout << real << " + " << imag << "i" << std::endl; }
};

// Definition of the friend function outside the class
Complex operator-(const Complex& c1, const Complex& c2) {
    return Complex(c1.real - c2.real, c1.imag - c2.imag); // Direct access to private members
}

Copy Assignment Operator

  • Definition: The copy assignment operator (operator=) is a special member function used to assign the contents of one object to another existing object of the same class. It facilitates assignment between objects of the same type and is usually provided by the compiler's default shallow copy unless overridden by the programmer to perform a deep copy.

  • Syntax:

class& class::operator=(const class &arg) {
    // ... deep copy logic ...
    return *this; // Essential for chaining assignments (a = b = c;)
}
Example of Copy Assignment for Complex
Complex& Complex::operator=(const Complex& other) {
    if (this != &other) { // Self-assignment check: essential to prevent self-destruction of resources
        real = other.real;
        imag = other.imag;
    }
    return *this; // Return reference to self for chaining
}

  • Assignment operator for Complex follows the same principles:

    • Return type is a reference to a Complex object (Complex&).

    • Argument type is a const reference to another Complex object (const Complex&).

    • The if (this != &other) check is crucial to handle self-assignment (e.g., a = a;) correctly, especially in classes managing dynamically allocated memory, preventing potential issues like freeing memory before it's copied.

The “This” Pointer

  • Definition: Within a non-static member function, this is a prvalue expression whose value is the address of the object for which the member function is called. It is a pointer to the current object, or the object behind the function being called.

  • C++ passes a hidden this pointer as an implicit first argument to every non-static member function.

  • Implicitly utilized within a member function for referring to data members (e.g., real is equivalent to this->real). It becomes explicit when needed to disambiguate local variables from member variables or when returning the current object (*this). For example, return *this; returns the object itself.

Overloading Stream-insertion and Stream-extraction Operators

  • Example of Overloading:

    • cout << (stream-insertion) and cin >> (stream-extraction) are fundamental instances of operator overloads found in C++'s standard library for built-in types.

  • Built-in use of the operators:

    • ostream for output (e.g., std::cout) and istream for input (e.g., std::cin).

  • These operators are typically overloaded as friend functions because the left-hand operand (ostream or istream object) is usually not an object of the user-defined class. If they were member functions, the syntax would be myObject << std::cout, which is unnatural. The friend keyword allows them to directly access private members for I/O operations.

Example Implementation

Overloaded Output Operator (operator<<):

// Typically a friend function to allow 'std::cout << myObject;' syntax
friend std::ostream& operator<<(std::ostream &os, const Date &d) {
    os << d.month << "/" << d.day << "/" << d.year;
    return os; // Return 'os' by reference to allow chaining (e.g., cout << d1 << d2;)
}

  • Used as cout << d1; to output the date object in a user-friendly format. The return type ostream& is crucial for chaining output operations. const Date &d ensures the date object is not modified and avoids copying.

Overloaded Input Operator (operator>>):

// Typically a friend function to allow 'std::cin >> myObject;' syntax
friend std::istream& operator>>(std::istream &in, Date &d) { // 'Date &d' is not const because it will be modified
    char dummy_slash; // To consume the '/' characters
    int month_val, day_val, year_val;
    if (in >> month_val >> dummy_slash >> day_val >> dummy_slash >> year_val) {
        // Basic validation and setting the Date object
        if (d.set(month_val, day_val, year_val)) { // Assuming a set method is available
            // If setting successful, return the stream
            return in;
        } else {
            // Handle invalid date format, maybe set failbit for the stream
            in.setstate(std::ios_base::failbit);
        }
    } else {
        // Handle input stream errors (e.g., non-integer input)
        in.setstate(std::ios_base::failbit);
    }
    return in; // Return 'in' by reference for chaining
}

  • Used as cin >> d1; to input a date object. The return type istream& is for chaining input operations. The Date &d argument must be a non-const reference because the function modifies the object. Error handling (like in.setstate(std::ios_base::failbit)) is important for robust input.

In-class Practice with Complex Class

  • Implement stream overloading for the Complex class:

class Complex {
private:
    double real;
    double imag;
public:
    // Constructor, operators as above...

    // Friend function: Output stream declaration
    friend std::ostream& operator<<(std::ostream& os, const Complex& c);
    // Friend function: Input stream declaration
    friend std::istream& operator>>(std::istream& is, Complex& c);
};

// Definition of output stream operator
std::ostream& operator<<(std::ostream& os, const Complex& c) {
    os << c.real;
    if (c.imag >= 0) {
        os << " + " << c.imag << "i";
    } else {
        os << " - " << -c.imag << "i";
    }
    return os;
}

// Definition of input stream operator
std::istream& operator>>(std::istream& is, Complex& c) {
    double r, i;
    char op, img_char; // To capture '+', '-', 'i'
    is >> r; // Read real part
    if (is.peek() == '+') { // Check for '+' or '-'
        is >> op >> i >> img_char; // Read ' ', '+', ' ', imag, 'i'
    } else if (is.peek() == '-') {
        is >> op >> i >> img_char; // Read ' ', '-', ' ', imag, 'i'
        i = -i; // Adjust sign for negative imaginary part
    } else {
        // Assume purely real if no '+' or '-' followed by 'i'
        i = 0.0;
    }
    if (is.good() && img_char == 'i') { // Basic check if 'i' was read
        c.real = r;
        c.imag = i;
    } else if (is.good() && i == 0.0) { // If it was just 'r'
        c.real = r;
        c.imag = 0.0;
    } else {
        is.setstate(std::ios_base::failbit); // Set failbit if input format is not recognized
    }
    return is;
}

Take Home Message

  • Operator overloading offers convenient, readable, and intuitive notation for diverse object behaviors, making user-defined types behave more like built-in types.

  • There are three avenues for implementing operator overloading, each with its own use cases and implications:

    1. Member functions: Ideal when the left-hand operand is an object of the class itself.

    2. Non-member functions (Free functions): Used when symmetry is needed (e.g., int + Complex), or the left-hand operand is not the class object (e.g., stream operators).

    3. Friend functions: A specific type of non-member function that is granted direct access to private and protected members of a class, useful for stream operators where istream/ostream is the first operand and the class needs to access its own private data for I/O.

Vectors and Arrays

Outline for Vectors and Arrays

  • Arrays

  • Pointers

  • Copy Semantics (shallow vs. deep copy)

  • Elements Access (e.g., [], at())

  • References

Reasons for Studying Vector Implementation

  • To understand how the standard library std::vector works internally, including its memory management and performance characteristics O(1) amortized push_back.

  • Introduce core concepts and language features essential for robust class design, such as constructors, destructors, copy control (copy constructor, copy assignment), and the this pointer.

  • Discuss free store (heap) management using new and delete, including the importance of pairing them correctly to prevent memory leaks and corruption.

  • Address copy and move semantics in detail, distinguishing between shallow and deep copies and introducing move semantics to avoid expensive copies when ownership can be transferred.

  • Discuss dynamically growing data structures, the strategy for resizing (often doubling capacity), and its performance implications.

  • Understanding memory management techniques, including resource acquisition is initialization (RAII) and proper deallocation.

  • Expose students to class design methodologies and examples of efficient, exception-safe code, demonstrating best practices for resource management.

Example of Vector Class Implementation

class vector {
    int sz;         // the size of the vector
    double* elem;   // pointer to the dynamically allocated array of elements on the free store (heap)

public:
    // Constructor: Allocates memory for 's' doubles and initializes 'sz'.
    // Uses a constructor initializer list for efficient initialization.
    vector(int s) : sz{s}, elem{new double[s]} {
        // Initialize elements to 0.0 to prevent undefined behavior.
        for (int i = 0; i < sz; ++i) elem[i] = 0.0;
    }

    // Destructor: Deallocates the dynamically allocated memory to prevent memory leaks.
    // Follows the RAII principle.
    ~vector() { delete[] elem; }

    // Read access to an element (bounds checking might be added for safety).
    double get(int n) const { return elem[n]; } // 'const' for read-only access

    // Write access to an element.
    void set(int n, double v) { elem[n] = v; }

    // Returns the current size of the vector.
    int size() const { return sz; }
};

  • Constructor: Allocates memory dynamically on the heap for s elements of type double using new double[s]. It is good practice to initialize these elements to a default value (e.g., 0.0) to ensure predictable state and prevent garbage values.

  • Destructor: Deallocates the dynamically allocated memory using delete[] elem. This is crucial for preventing memory leaks and follows the Resource Acquisition Is Initialization (RAII) principle, where resources are acquired in the constructor and released in the destructor.

Initialization of Vectors

  • When initializing a vector with an integer, the interpretation can vary depending on the syntax, which can be a source of confusion:

    • vector v1(17); creates a vector of 17 elements, typically initialized to their default value (0.0 for doubles). This calls the constructor vector(int s).

    • vector v2 {17}; creates a vector with a single element of value 17. This uses an initializer list constructor (if available) or might implicitly convert if no such constructor exists and a single-argument constructor is suitable. To prevent accidental implicit conversions from int to vector, the single-argument constructor vector(int s) should often be declared explicit.

    • If vector(int s) were explicit, then vector v2 = 17; would be an error, but vector v2(17); or vector v2 = vector(17); would still work.

Issues with Copying Vectors

  • Problem understanding with naive copying methods (e.g., compiler-generated default copy constructor/assignment operator for classes with raw pointers), leading to disasters such as multiple deletions of the same memory space, dangling pointers, and corrupted data. This is known as a shallow copy.

    • Example Scenario with Naïve Copying:

void f(int n) {
    vector v(n);      // define a vector, 'v.elem' points to memory A
    // Default copy constructor (if not defined) would just copy 'sz' and 'elem' pointer.
    vector v2 = v;    // problematic shallow copy: 'v2.elem' now also points to memory A
    // When 'f' exits:
    // 1. v2's destructor is called: 'delete[] v2.elem;' (frees memory A)
    // 2. v's destructor is called: 'delete[] v.elem;' (attempts to free memory A AGAIN -> **double free error**!)
}

  • Expected Behaviors in Ideal Conditions (with proper deep copy):

    • Both v2 and v3 become independent copies of v, meaning they each own their separate block of dynamically allocated memory containing the same values.

    • Memory is correctly returned to the free store upon function exit through each object's destructor being called exactly once on its owned memory.

Naïve Copy Initialization

  • Default Behavior: C++ provides a default copy constructor and copy assignment operator if you don't define your own. For classes containing raw pointers to dynamically allocated memory, this default behavior performs a shallow copy. It copies the pointer value itself, not the data it points to. This results in multiple objects sharing ownership of the same underlying resource, leading to the problems described above (double free, dangling pointers).

Copy Constructor

class vector {
    int sz;
    double* elem;
public:
    // ... other constructors, destructor ...

    // Copy Constructor: Performs a deep copy.
    // It allocates new memory for the new vector and copies the elements from the source vector.
    vector(const vector& a) : sz{a.sz}, elem{new double[a.sz]} {
        // Copy elements from source 'a' to 'this' new memory
        for (int i = 0; i < sz; ++i) elem[i] = a.elem[i];
    }
    // ...
};

  • Functionality: Correctly allocates new space on the heap for the new vector object (elem{new double[a.sz]}) and then initializes the values by copying each element from the source vector (a.elem[i]) into the newly allocated space. This ensures deep copy behavior, where the new vector now owns its independent copy of the data, preventing shared memory issues.

Copy Assignment Operator
vector& vector::operator=(const vector& a) {
    if (this != &a) { // Self-assignment check: crucial to prevent object resources from being corrupted
        // 1. Allocate new memory for the data of the source object. This should be done before
        //    deleting existing memory, to ensure strong exception safety.
        double* p = new double[a.sz]; // A temporary buffer for the new data

        // 2. Copy the elements from the source 'a' to the newly allocated temporary memory.
        for (int i = 0; i < a.sz; ++i) p[i] = a.elem[i];

        // 3. Deallocate the old memory owned by 'this' object.
        delete[] elem;

        // 4. Update 'this' object's members to point to the new memory and reflect the new size.
        sz = a.sz;
        elem = p;
    }
    return *this; // Return reference to the current object to allow chaining of assignments.
}

  • Procedure: Ensures existing memory is managed correctly.

    1. Self-assignment check (if (this != &a)): Prevents issues if an object is assigned to itself (e.g., vec = vec;). Without this, delete[] elem would free memory that a.elem still points to, leading to a double-free later when a is destroyed.

    2. Resource Allocation: New memory is allocated (new double[a.sz]) to hold the copied data. This allocation happens before deleting the old memory, which is important for exception safety (if new throws an exception, the original object's state remains valid).

    3. Data Copy: Elements are copied from the source (a).

    4. Resource Deallocation: The old memory pointed to by elem is deallocated (delete[] elem).

    5. State Update: The pointer elem is updated to point to the newly allocated memory, and sz is updated to the new size.

    6. Return *this: Essential for supporting chained assignments like v1 = v2 = v3;.

Understanding Copy Semantics

  • Shallow Copy vs. Deep Copy: This distinction is critical for classes managing dynamic resources.

    • Shallow Copy: The default behavior provided by the compiler. It copies the values of the object's member variables. If these members are pointers to dynamically allocated memory, only the pointer itself is copied, not the data it points to. Result: multiple objects reference (share ownership of) the same underlying memory resource. This can lead to bugs like double-free errors when destructors are called or data corruption if one object modifies the shared resource.

    • Deep Copy: The behavior implemented by manually defining a copy constructor and copy assignment operator. It allocates new memory for the target object and then copies the contents of the dynamically allocated data from the source object into this new memory. Result: each object owns a separate, independent copy of the data, ensuring isolated resource management and preventing the issues associated with shallow copies.

Essential Operations for Vector Class

For classes that manage dynamic resources (like vector with double* elem), adhering to the Rule of Five is critical to ensure correct resource management and avoid common pitfalls:

  1. Constructors:

    • Default Constructor: vector() - Creates an empty vector or one with a default size.

    • Size Constructor: explicit vector(int s) - Creates a vector of s elements (as implemented). explicit prevents implicit conversions.

    • Copy Constructor: vector(const vector& a) - Performs a deep copy upon initialization.

    • Move Constructor (C++11 onwards): vector(vector&& a) - "Steals" resources from a temporary (rvalue) object instead of copying, improving efficiency.

  2. Destructor: ~vector() - Releases dynamically allocated resources.

  3. Copy Assignment Operator: vector& operator=(const vector& a) - Performs a deep copy upon assignment between existing objects.

  4. Move Assignment Operator (C++11 onwards): vector& operator=(vector&& a) - "Steals" resources from a temporary (rvalue) object upon assignment.

  5. Access Functions:

    • double get(int n) const; / double operator[](int n) const; (for const objects) - Read access.

    • void set(int n, double v); / double& operator[](int n); (for non-const objects) - Write access.

    • int size() const; - Returns the number of elements.

    • int capacity() const; - (For a more complete vector) Returns the total storage currently allocated.

Types of Memory Management

  • Global vector: Declared at global scope or as a static member. It persists for the entire program lifetime (from program start to end). Memory is typically allocated at program startup and deallocated at program termination.

  • Local vector: Declared within a function or block scope (on the stack). Its lifetime is temporary and limited to the function's or block's execution. Memory is automatically allocated on the stack when the function is called and deallocated when the function returns.

  • Free-store vector (Heap-allocated): Dynamically allocated using new (e.g., vector* vec_ptr = new vector(10);). Its lifetime is until explicitly deallocated using delete (e.g., delete vec_ptr;). If not explicitly deleted, it leads to a memory leak. This provides flexible memory management, allowing objects to outlive the scope in which they were created.

Resizing and Capacity Management for Vectors

  • Dynamic resizing strategies: Vectors are designed to be dynamically resizable. When a vector runs out of capacity (i.e., size() == capacity()) and push_back or resize is called to add more elements, it must reallocate its internal array to a larger size.

v.resize(10); // Resizes the vector to contain exactly 10 elements.
              // If the new size is larger, new elements are default-initialized.
              // If smaller, elements are destroyed. May involve reallocation.
v.push_back(7); // Adds a new element (7) to the end of the vector.
                // If capacity is insufficient, the vector will reallocate its internal buffer,
                // usually doubling its capacity, copy existing elements, add the new one,
                // and then deallocate the old buffer. This operation has amortized O(1) complexity.
v = v2;         // Copies v2’s elements and size to v, using the copy assignment operator.
                // This is a deep copy operation.
Optimizing Memory Management for Vectors

  • Maintaining free space for future expansions: To avoid frequent, expensive reallocations which involve new[], copying, and delete[], std::vector typically allocates more memory than immediately needed. This means its internal capacity() is often greater than its size().

  • Example shape of internal data representation illustrating free space issues: If a vector always reallocates to precisely size + 1, push_back would be O(N) for every operation. By allocating extra capacity (e.g., doubling it), push_back becomes amortized O(1). This means that while some push_back operations are expensive (when reallocation occurs), the vast majority are very fast, leading to an overall efficient average performance.

  • Functions like reserve(N) can be used to pre-allocate memory, especially when the final size is known or estimated, to minimize reallocations.

Conclusion / Reflection

  • Understand critical operator overloading techniques, including choosing between member, non-member, and friend functions based on the desired syntax and access needs.

  • Grasp memory management concepts (new/delete, RAII, stack/heap/global memory) and their importance for resource-owning classes.

  • Recognize the fundamental distinction between shallow and deep copy semantics, and the absolute necessity of implementing the Rule of Three/Five (destructor, copy constructor, copy assignment operator, and optionally move constructor/assignment) for classes managing dynamic resources to avoid memory leaks, double-frees, and data corruption.

  • Recognize the importance of thorough implementation to avoid common pitfalls such as memory leaks, incorrect memory sharing, and undefined behavior.

  • Appreciate how std::vector handles dynamic resizing and capacity management efficiently, providing a robust and flexible dynamic array.