# Implement a Simple Vector Class

**Interview Question: Expression Templates and Compile-Time Polymorphism**

**Background:**
Expression templates are a C++ template metaprogramming technique used for optimizing high-performance computations, particularly in numerical computing and scientific applications. They enable the efficient evaluation of complex expressions by eliminating unnecessary temporaries and combining multiple operations into a single loop at compile time.

**Task:**
1. **Implement a Simple Vector Class:**
- Create a template class `Vector` that encapsulates a dynamic array of elements (use `std::vector` for storage).
- Implement basic operations like element access and size retrieval.

2. **Expression Templates for Vector Operations:**
- Extend the `Vector` class to support addition and subtraction operations with other vectors.
- Use expression templates to create and return intermediate expression objects instead of computing the result immediately.
- Ensure that the actual computation of the addition or subtraction happens only when the result is assigned to a vector.

3. **Compile-Time Polymorphism:**
- Utilize compile-time polymorphism to handle different types of expressions (e.g., addition, subtraction) in a generic way.
- Demonstrate the use of template specialization or SFINAE (Substitution Failure Is Not An Error) to distinguish between different expression types.

4. **C++20 Concepts:**
- Define a concept that ensures the template parameters for your vector and expression templates are only instantiated with compatible types.
- Use `requires` clauses to enforce these constraints.

5. **Custom Type Traits and Reflection (Bonus):**
- Implement a custom type trait to check if a given type is an instance of your `Vector` class.
- Demonstrate how you can use this trait in SFINAE or `requires` clauses to create more flexible and type-safe code.

**Evaluation Criteria:**
- Correct implementation of expression templates, ensuring efficient computation.
- Proper use of C++20 concepts and `requires` clauses for type safety.
- Effective use of compile-time polymorphism and SFINAE.
- Bonus points for implementing and using custom type traits.
- Code readability, documentation, and adherence to C++ best practices.

## Step 1

1. **Implement a Simple Vector Class:**
- Create a template class `Vector` that encapsulates a dynamic array of elements (use `std::vector` for storage).
- Implement basic operations like element access and size retrieval.

Let's include headers first!

#include <vector>
#include <cstdint>

template<typename T>
class Vector {
    std::vector<T> storage_;
public:
    // Actually, we can let the compiler generate those special member functions
    // by itself, because according to the [dcl.fct.def.default] p5 says...
    Vector() = default; // C++11
    Vector(const Vector&) = default;
    Vector(Vector&&) = default;
    Vector& operator=(const Vector&) = default;
    Vector& operator=(Vector&&) = default;
    ~Vector() = default;
    
    const T& operator[](size_t pos) const { return storage_[pos]; }
    T& operator[](size_t pos) { return storage_[pos]; }
    
    size_t size() const noexcept { return storage_; }
};

## Step 2

2. **Expression Templates for Vector Operations:**
- Extend the `Vector` class to support addition and subtraction operations with other vectors.
- Use expression templates to create and return intermediate expression objects instead of computing the result immediately.
- Ensure that the actual computation of the addition or subtraction happens only when the result is assigned to a vector.

Expression Template:

template<typename T>
class Vector;

template<typename E, typename T>
class VecExpression {
public:
    size_t size() const { return static_cast<const E&>(*this).size(); }
    T operator[](size_t i) const { return static_cast<const E&>(*this)[i]; }

    operator Vector<T>() const {
        Vector<T> result(size());
        for (size_t i = 0; i < size(); ++i) {
            result[i] = (*this)[i];
        }
        return result;
    }
};

The modified Vector class:

template<typename T>
class Vector : public VecExpression<Vector<T>, T> {
    std::vector<T> storage_;

public:
    Vector() = default;
    Vector(size_t n) : storage_(n) {}
    Vector(const Vector<T>&) = default;
    Vector(Vector<T>&&) = default;
    Vector& operator=(const Vector<T>&) = default;
    Vector& operator=(Vector<T>&&) = default;
    ~Vector() = default;

    template<typename E>
    Vector(const VecExpression<E, T>& expr) {
        storage_.resize(expr.size());
        for (size_t i = 0; i < expr.size(); ++i) {
            storage_[i] = expr[i];
        }
    }

    template<typename E>
    Vector& operator=(const VecExpression<E, T>& expr) {
        storage_.resize(expr.size());
        for (size_t i = 0; i < expr.size(); ++i) {
            storage_[i] = expr[i];
        }
        return *this;
    }

    size_t size() const noexcept { return storage_.size(); }
    T& operator[](size_t i) { return storage_[i]; }
    const T& operator[](size_t i) const { return storage_[i]; }
};

Addition Expression:

template<typename T>
class VecAdd : public VecExpression<VecAdd<T>, T> {
    const Vector<T>& lhs_;
    const Vector<T>& rhs_;

public:
    VecAdd(const Vector<T>& lhs, const Vector<T>& rhs) : lhs_(lhs), rhs_(rhs) {
        assert(lhs.size() == rhs.size());    // We couldn't handle the size mismatching issue
    }

    size_t size() const noexcept { return lhs_.size(); }
    T operator[](size_t i) const { return lhs_[i] + rhs_[i]; }
};

template<typename T>
VecAdd<T> operator+(const Vector<T>& lhs, const Vector<T>& rhs) {
    return VecAdd<T>(lhs, rhs);
}

Subtraction Expression:

template<typename T>
class VecSub : public VecExpression<VecSub<T>, T> {
    const Vector<T>& lhs_;
    const Vector<T>& rhs_;

public:
    VecSub(const Vector<T>& lhs, const Vector<T>& rhs) : lhs_(lhs), rhs_(rhs) {
        assert(lhs.size() == rhs.size());
    }

    size_t size() const noexcept { return lhs_.size(); }
    T operator[](size_t i) const { return lhs_[i] - rhs_[i]; }
};

template<typename T>
VecSub<T> operator-(const Vector<T>& lhs, const Vector<T>& rhs) {
    return VecSub<T>(lhs, rhs);
}

See: https://godbolt.org/z/646nWK8e1

## Step 3

3. **Compile-Time Polymorphism:**
- Utilize compile-time polymorphism to handle different types of expressions (e.g., addition, subtraction) in a generic way.
- Demonstrate the use of template specialization or SFINAE (Substitution Failure Is Not An Error) to distinguish between different expression types.

We use the print-function for example, please also feel free replacing to your requrement:

template<typename Expr, typename = void>
struct printVecExpressionType {
    static void print([[maybe_unused]] const Expr& e) noexcept {
        std::cout << "Unknown Expression Type" << std::endl;
    }
};

template<typename T>
struct printVecExpressionType<VecAdd<T>, std::void_t<decltype(std::declval<VecAdd<T>>().size())>> {
    static void print(const VecAdd<T>& e) noexcept {
        using size_type = decltype(e.size());
        for (size_type i = 0; i < e.size(); i++)
            std::cout << e[i] << " ";
        std::cout << std::endl;
    }
};

template<typename T>
struct printVecExpressionType<VecSub<T>, std::void_t<decltype(std::declval<VecSub<T>>().size())>> {
    static void print(const VecSub<T>& e) noexcept {
        using size_type = decltype(e.size());
        for (size_type i = 0; i < e.size(); i++)
            std::cout << e[i] << " ";
        std::cout << std::endl;
    }
};

See: https://godbolt.org/z/MhY4bTnoq

## Step 4

4. **C++20 Concepts:**
- Define a concept that ensures the template parameters for your vector and expression templates are only instantiated with compatible types.
- Use `requires` clauses to enforce these constraints.

We need C++20's concept header:

#include <concepts>    // C++20
#include <type_traits> // C++11

The concept:

template<typename T>
concept ArithmeticType = requires(T a, T b) {
    { a + b } -> std::convertible_to<T>;
    { a - b } -> std::convertible_to<T>;
    { a == b } -> std::convertible_to<bool>;
    { a != b } -> std::convertible_to<bool>;
};

And we replace the Vector, VecAdd, VecSub `typename` to our concepts.
See: https://godbolt.org/z/z483b8aqs

## Step 5

5. **Custom Type Traits and Reflection (Bonus):**
- Implement a custom type trait to check if a given type is an instance of your `Vector` class.
- Demonstrate how you can use this trait in SFINAE or `requires` clauses to create more flexible and type-safe code.

Implement our type traits:

template<typename T>
struct IsVector : std::false_type {};

template<typename T>
struct IsVector<Vector<T>> : std::true_type {};

template<typename T>
inline constexpr bool is_vector_v = IsVector<T>::value;

### SFINAE version:

template<typename T>
typename std::enable_if<is_vector_v<T>, void>::type
printVector(const T& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
}

template<typename T>
typename std::enable_if<!is_vector_v<T>, void>::type
printVector(const T& vec) {
    std::cout << "Not a Vector type" << std::endl;
}

### concept version:

template<typename T>
concept VectorType = is_vector_v<T>;

template<typename T>
concept VecExpressionType = std::is_base_of_v<VecExpression<T, decltype(std::declval<T>().operator[](0))>, T>;

template<typename T>
concept VectorGeneralType = VecExpressionType<T> || VectorType<T>;

template<VectorGeneralType T>
void printVector(const T& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
}

// Other types
template<typename T>
void printVector([[maybe_unused]] const T& vec) requires (!VectorGeneralType<T>) {
    std::cout << "Not a Vector type" << std::endl;
}

See: https://godbolt.org/z/cMhcTnM4T

Thanks!