Skip to content

5.26 Lecture 12

Abstract Data Type

An Abstract Data Type is a description of values and operations on those values, without defining the technical details on how those values are represented and how the operations work on those representations

Lists

A List is a linearly organized collection of values, its main operations are:

  • Creation
  • Insertion/Deletion/Retrieval: get(position)​, elementAt(position)​
  • Properties about a list: empty, size, contains.

Sets

A Set is an unordered collection of different elements, its main operations are:

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

Stacks

A Stack is a linearly organized collection of values (similar to a list), it's a FILO collection (First In, Last Out), its main operations are:

  • Creation
  • Push/Pop
  • Properties about a list: empty, size

Queues

A Queue is a linearly organized collection of values (similar to a list), it's a FIFO collection (First In, First Out), its main operations are:

  • Creation
  • Enqueue/Dequeue
  • Properties about a list: empty, size

image​

The Abstract data type and its implement should be separated

In C, abstract data type is defined in 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.

Operations: Declarations (Function Prototypes), NOT Definitions.

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

Relies on Informal Conventions

  • Key Distinction: C does not have built-in language constructs (like public​/private​ keywords in C++ or Java) to strictly enforce information hiding.

  • How Abstraction is Achieved in C:

  • Header (​ ​.h​​ ) vs. Source (​ ​.c​​ ) File Separation: Declarations in .h​, definitions in .c​.

  • Incomplete Types:​typedef struct MyADT MyADT\_t;​ Compiler enforces non-access to members of incomplete types.
  • ​​static​​ Keyword: Used for functions and variables within a .c​ file to limit their scope and make them "private" to the implementation.

For a given ADT interface, the blue box represents one specific, chosen concrete implementation.

Data is separated from operations

Difficult to define generic structures

image​

Yes, Yes, No

image​

  • Declarations: This means specifying the name of the operation, what inputs it takes (arguments), and what it returns.
  • Definitions: This means providing the actual code or implementation for that operation. It's the "how-to" part.

image​

Fundamental Characteristics of Object Oriented Programming

  • Abstraction: It offers powerful mechanisms for the definition of data abstractions.

  • Encapsulation

  • An evolution of the traditional methodology of separating data structures from algorithms

  • Operations (methods) are associated with the data structures these operate on

If modules are appropriately defined, data structures should only be manipulated through the use of allowed operations (information hiding) If the data abstractions are appropriate, modularity and reuse can be significantly improved compared to procedural programming

image​

image​

a LinkedList object contains or is composed of _Node

How templates work in C++

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

print<int>(5);
print<char>('h');
print<std::string>("Hello?");
int values[3] = {1, 2, 3};
print<int[]>(values);

"In Compilation-Time (during compilation) a different version of print will be created for each case."

  • This is exactly what we discussed: template instantiation. The compiler doesn't just have one print​ function. It creates print_for_int​, print_for_char​, print_for_string​, etc., as needed during the compilation process.

"Advantage: choosing which version of print to run is already done during compilation."

  • Static Polymorphism: Because the correct version of the function is figured out at compile time, there's no runtime overhead to decide "which print do I call?". This can lead to very efficient code, often as fast as if you had written separate functions yourself.
  • Type Safety: If you try to use print​ with a type that doesn't support the <<​ operator with std::cout​, you'll get a compile-time error, not a runtime crash. This is good!

"Disadvantage: It uses "Duck-Typing" to compile, the used type needs to have ​<<​ ​ . We can "fix" this with concepts."

  • "Duck-Typing" (Implicit Interface): The template print​ doesn't explicitly say "T must be printable." 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, you get an error, often a long and confusing one because the error happens deep inside the template code when the compiler tries to generate the specific version.
  • The requirement (T​ must support operator<<​) is an implicit interface.
  • "We can "fix" this with concepts.": C++20 introduced Concepts. Concepts allow you to explicitly define the requirements for a template parameter. For example, you could define a Printable​ concept that requires a type to have a valid operator<<​ for std::cout​. Then you could write:
// C++20 example with a hypothetical Printable concept
template <Printable T> // Now T MUST satisfy the Printable concept
void print(const T value) {
    std::cout << value << std::endl;
}

typename vs class

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

template <class T>
void print(const T value) {
    std::cout << value << std::endl;
}

We will use class when we want to specify that the type should be a class, otherwise we will use typename.

But the language makes no difference between the two, the difference is in portraying the intention of the developer.

Example

// An example -- This is just a title for the slide

template <class T> // 1. Template Declaration
class Stack {      // 2. Class Name
public:            // 3. Public Interface (what users of the class can access)
    Stack(int s = 10);        // 4. Constructor (with a default size of 10)
    ~Stack() { delete [] stackPtr; } // 5. Destructor (cleans up memory)
    bool push(const T&);      // 6. Push operation declaration
    bool pop(T&);             // 7. Pop operation declaration (note: image has a typo here, says "push(T&)" but comment implies pop)
    int isEmpty() const { return top == -1; } // 8. Check if stack is empty
    int isFull() const { return top == size - 1; }  // 9. Check if stack is full

private:           // 10. Private Members (internal details hidden from users)
    int size;        // 11. Maximum capacity of the stack
    int top;         // 12. Index of the top element (-1 if empty)
    T* stackPtr;     // 13. Pointer to the array storing stack elements
};

Then the implement should be

//constructor with the default size 10
template <class T>
Stack<T>::Stack(int s = 10) {
  top = -1;              // 1. Initialize top to -1 (empty stack)
  this->size = s;         // 2. Store the provided size
  stackPtr = new T[s]; // 3. Allocate memory for the array
}

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

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

Main function

typedef Stack<float> FloatStack;

FloatStack fs(5);
float f = 1.1;
std::cout << "Pushing elements onto fs" << std::endl;
while (fs.push(f)) {
    std::cout << f << ' ';
    f += 1.1;
}
std::cout << "\n" << "Stack Full.\n";
std::cout << "Popping elements from fs\n";
while (fs.pop(f)) {
    std::cout << f << ' ';
}
std::cout << "\nStack Empty\n" << std::endl;

Generic functions as arguments

Templates by themselves do not provide a way to add restrictions (like in Java when we asked for a generic argument to be Comparable).

One option would be to ask for certain generic functions as extra arguments.

template<typename T>
using t_max = 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<T> max) {
    assert(size > 0);
    T current_max = values[0];
    for (int i = 1; i < size; i++) {
        current_max = max(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;
}

  • "Templates by themselves do not provide a way to add restrictions (like in Java when we asked for a generic argument to be Comparable​)."

  • In C++ templates, when you write template <typename T>​, \(T\) can be any type. If your template function internally tries to do something like \(a > b\) where \(a\) and \(b\) are of type \(T\), it will only compile if the operator>​ is actually defined for that specific \(T\).

  • Unlike Java's T extends Comparable​, C++ (before C++20 Concepts) didn't have a direct way to say "this template \(T\) must support comparison" at the template definition level.

  • "One option would be to ask for certain generic functions as extra arguments."

  • This is the solution presented: if your generic function needs a specific operation (like finding the maximum of two elements), you can make the user pass in a function that performs that operation for type \(T\).

  • ​t_max<T> max_func​: This is the key! It takes an argument named max_func​. The type of max_func​ is t_max<T>​, which means it's a pointer to a function that can compare two T's and return the larger one

Concepts

Another way to ask for restrictions, more akin to generic restrictions in Java when we asked for a generic argument to be Comparable is to use Concepts to add these requirements.

You need to compile with g++ -std=c++20​

template <typename T>
concept Comparable = requires(T a, T b) {
    { a.compares_to(b) } -> std::same_as<int>;
};
/*A type T is Comparable if, given two instances a and b of T, 
the expression a.compares_to(b) is valid and returns an int."*/
class Integer {
private:
    int value;
public:
    Integer(int value): value(value) {}
    int compares_to(Integer other) {
        return value - other.value;
    }
};

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);
    std::cout << res << std::endl;
    return 0;
}

Like java

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 this.value - other.value;
    }
}

<T extends Comparable<T>> int someGenericFunction(T obj1, T obj2) {
    return obj1.compareTo(obj2);
}

Metaprogramming

Templates not only allow us for generic classes, functions, and structures.

We can program using templates:

  • Templates are not the same as preprocessor directives.
  • Templates are resolved by the compiler, not the preprocessor.
  • Templates are instances during compilation time depending on the arguments.
  • Once the executable is compiled, instances are already available without any extra steps.
  • All instances generated are also accessible.

An example

#include <iostream>

// 1. General Template Definition (the "recursive step")
template<unsigned int x> // For any non-negative integer x
struct Counter {
    // This line says: 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
    std::cout << Counter<42>::counter << std::endl;
    return 0;
}

Template Specialization

In C++, template specialization allows us to define different implementations of a template for specific data types or combinations of data types.

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

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

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

int main()
{
    print(3);
    print("a");
    return 0;
}
---
output
Value: 3
a

Example of fibonacci

fibonacci_function.cpp

#include <iostream>

unsigned long long fibonacci(int v) {
    if (v == 0) {
        return 0;
    } else if (v == 1) {
        return 1;
    } else {
        return fibonacci(v - 2) + fibonacci(v - 1);
    }
}

int main(const int argc, const char ** const argv) {
    int f = 35;
    std::cout << "My greatest fibonacci: " << fibonacci(f) << std::endl;
    for (int i = 0; i < 200; i++) {
        if (fibonacci(f - 1) >= 0) {
            std::cout << '.';
        }
    }
    std::cout << std::endl;
}

fibonacci.cpp

#include <iostream>

template <unsigned long long n>
struct Fibonacci {
    enum : unsigned long long { result = Fibonacci<n - 1>::result + Fibonacci<n - 2>::result };
};
template<> struct Fibonacci<0> { enum { result = 0 }; };
template<> struct Fibonacci<1> { enum { result = 1 }; };


int main() {
    std::cout << "My greatest fibonacci: " << Fibonacci<35>::result << std::endl;
    for (int i = 0; i < 200; i++) {
        if (Fibonacci<34>::result >= 0) {
            std::cout << '.';
        }
    }
    std::cout << std::endl;
}