Compiler Explorer

Source code

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>
#include <version>

// Expression templates

namespace expr {

namespace impl {

template<std::size_t Size>
struct fixed_vector_expr {
  static constexpr std::size_t size() { return Size; }
};

template<std::size_t Size0, std::size_t Size1>
using binary_fixed_vector_expr_t = fixed_vector_expr<
  Size0 < Size1 ? Size1 : Size0
>;

} // namespace impl

template<class T>
constexpr bool is_fixed_vector_v = false;

template<class X>
  requires(is_fixed_vector_v<X>)
struct unary_plus_expr : public impl::fixed_vector_expr<X::size()> {
  constexpr auto operator[] (std::size_t k) const {
    return +x[k];
  }

const X& x;
};

template<class X>
constexpr bool is_fixed_vector_v<unary_plus_expr<X>> = true;

template<class Left, class Right>
  requires(is_fixed_vector_v<Left> && is_fixed_vector_v<Right>)
class binary_plus_expr :
  public impl::binary_fixed_vector_expr_t<Left::size(), Right::size()>
{
public:
  // Constructor needed due to inheritance;
  // otherwise this class could be an aggregate.
  binary_plus_expr(const Left& lt, const Right& rt) : left(lt), right(rt) {}

constexpr auto operator[] (std::size_t k) const {
    return left[k] + right[k];
  }

private:
  const Left& left;
  const Right& right;
};

template<class L, class R>
constexpr bool is_fixed_vector_v<binary_plus_expr<L, R>> = true;

template<class X>
  requires(is_fixed_vector_v<X>)
struct unary_minus_expr :
  public impl::fixed_vector_expr<X::size()>
{
  constexpr auto operator[] (std::size_t k) const {
    return -x[k];
  }

const X& x;
};

template<class X>
constexpr bool is_fixed_vector_v<unary_minus_expr<X>> = true;

template<class Left, class Right>
  requires(is_fixed_vector_v<Left> && is_fixed_vector_v<Right>)
class binary_minus_expr :
  public impl::binary_fixed_vector_expr_t<Left::size(), Right::size()>
{
public:
  // Constructor needed due to inheritance;
  // otherwise this class could be an aggregate.
  binary_minus_expr(const Left& lt, const Right& rt) : left(lt), right(rt) {}

constexpr auto operator[] (std::size_t k) const {
    return left[k] - right[k];
  }

private:
  const Left& left;
  const Right& right;
};

template<class L, class R>
constexpr bool is_fixed_vector_v<binary_minus_expr<L, R>> = true;

template<class ScalingFactor, class Vector>
  requires(
    ! is_fixed_vector_v<ScalingFactor> &&
    is_fixed_vector_v<Vector>)
struct scale_expr :
  public impl::fixed_vector_expr<Vector::size()>
{
public:
  // Constructor needed due to inheritance;
  // otherwise this class could be an aggregate.
  scale_expr(const ScalingFactor& sf, const Vector& v) :
    alpha(sf), vec(v)
  {}

constexpr auto operator[] (std::size_t k) const {
    return alpha * vec[k];
  }

private:
  const ScalingFactor& alpha;
  const Vector& vec;
};

template<class S, class V>
constexpr bool is_fixed_vector_v<scale_expr<S, V>> = true;

template<class ValueType, std::size_t Size> 
class fixed_vector;

template<class ValueType, std::size_t Size> 
constexpr bool
is_fixed_vector_v<fixed_vector<ValueType, Size>> = true;

template<class ValueType, std::size_t Size> 
class fixed_vector : public impl::fixed_vector_expr<Size> {
public:
  constexpr fixed_vector() = default;

constexpr fixed_vector(const std::array<ValueType, Size>& data)
    : data_(data)
  {}

template<class Expr>
  constexpr fixed_vector(const Expr& expr) {
    for (std::size_t k = 0; k < Size; ++k) {
      data_[k] = expr[k];
    }
  }

template<class Expr>
  constexpr fixed_vector& operator=(const Expr& expr) {
    for (std::size_t k = 0; k < Size; ++k) {
      data_[k] = expr[k];
    }
    return *this;
  }

template<class Expr>
  constexpr fixed_vector& operator+=(const Expr& expr) {
    for (std::size_t k = 0; k < Size; ++k) {
      data_[k] += expr[k];
    }
    return *this;
  }

static constexpr std::size_t size() { return Size; }

constexpr ValueType operator[] (std::size_t k) const {
    return data_[k];
  }

constexpr ValueType& operator[] (std::size_t k) {
    return data_[k];
  }

private:
  std::array<ValueType, Size> data_{};
};

template<class X>
  requires(is_fixed_vector_v<X>)
constexpr unary_plus_expr<X>
operator+(const X& x) {
  return {x};
}

template<class X>
  requires(is_fixed_vector_v<X>)
constexpr unary_minus_expr<X>
operator-(const X& x) {
  return {x};
}

template<class L, class R>
  requires(
    is_fixed_vector_v<L> &&
    is_fixed_vector_v<R>)
constexpr binary_plus_expr<L, R>
operator+(const L& left, const R& right) {
  return {left, right};
}

template<class L, class R>
  requires(
    is_fixed_vector_v<L> &&
    is_fixed_vector_v<R>)
constexpr binary_minus_expr<L, R>
operator-(const L& left, const R& right) {
  return {left, right};
}

template<class ScalingFactor, class Vector>
  requires(
    ! is_fixed_vector_v<ScalingFactor> &&
    is_fixed_vector_v<Vector>)
constexpr scale_expr<ScalingFactor, Vector>
operator*(const ScalingFactor& alpha, const Vector& v) {
  return {alpha, v};
}

} // namespace expr

int main() {
  {
    using expr::fixed_vector;

// Test our expression templates system.
    {
      fixed_vector x{std::array{1.0f, 2.0f, 3.0f, 4.0f}};
      fixed_vector y{std::array{-1.0f, -2.0f, -3.0f, -4.0f}};

fixed_vector<float, 4> x_plus_y = x + y;
      fixed_vector x_plus_y_expected{std::array{0.0f, 0.0f, 0.0f, 0.0f}};
      for (std::size_t k = 0; k < 4; ++k) {
        assert(x_plus_y[k] == x_plus_y_expected[k]);
      }

fixed_vector<float, 4> three_times_x = 3.0f * x;
      fixed_vector three_times_x_expected{std::array{3.0f, 6.0f, 9.0f, 12.0f}};
      for (std::size_t k = 0; k < 4; ++k) {
        assert(three_times_x[k] == three_times_x_expected[k]);
      }

fixed_vector<float, 4> z = 3.0f * x + y;
      fixed_vector z_expected{std::array{2.0f, 4.0f, 6.0f, 8.0f}};
      for (std::size_t k = 0; k < 4; ++k) {
        assert(z[k] == z_expected[k]);
      }
    }

std::vector<fixed_vector<float, 4>> vec{
      fixed_vector{std::array{1.0f, 2.0f, 3.0f, 4.0f}},
      fixed_vector{std::array{0.5f, 1.0f, 1.5f, 2.0f}},
      fixed_vector{std::array{0.25f, 0.5f, 0.75f, 1.0f}}
    };
    const fixed_vector zero{std::array{0.0f, 0.0f, 0.0f, 0.0f}};
    const fixed_vector expected_result{std::array{
      1.75f, 3.5f, 5.25f, 7.0f  
    }};

// Show that a manual for loop with std::plus<> produces
    // the expected result.  std::plus<>::operator() returns
    // an expression template (binary_plus_expr) here.
    {
      fixed_vector<float, 4> plus_result;
      std::plus<> plus{};
      static_assert(
        std::is_same_v<
          decltype(plus(plus_result, vec[0])),
          expr::binary_plus_expr<
            fixed_vector<float, 4>,
            fixed_vector<float, 4>>
        >
      );

for (std::size_t k = 0; k < vec.size(); ++k) {
        plus_result = plus(plus_result, vec[k]);
      }
      for (std::size_t k = 0; k < 4; ++k) {
        assert(plus_result[k] == expected_result[k]);  
      }
    }

// Show that a manual for loop produces the expected result.
    // This invokes fixed_vector's generic operator+=
    // that works for any "fixed-vector-like" type, including
    // fixed_vector itself and any of its expression templates.
    {
      fixed_vector<float, 4> manual_result;
      for (std::size_t outer_index = 0; outer_index < vec.size(); ++outer_index) {
        manual_result += vec[outer_index];
      }
      for (std::size_t k = 0; k < 4; ++k) {
        assert(manual_result[k] == expected_result[k]);  
      }
    }

#if defined(__cpp_lib_ranges_fold)
    // fold_left with std::plus<> does NOT compile,
    // because the return type of std::plus<>::operator()
    // is an expression template type (binary_plus_expr).
    // This is a feature, not a bug, because returning an
    // expression template here would necessarily dangle.
    // This manifests as failure to satisfy
    // _`indirectly-binary-left-foldable-impl`_,
    // because binary_plus_expr is not movable
    // (because its copy assignment operator is implicitly deleted,
    // because it has reference members).
    auto fold_result = std::ranges::fold_left(
      vec.begin(), vec.end(),
      zero,
      //std::plus<>{}
      std::plus<fixed_vector<float, 4>>{}
    );
    for (std::size_t k = 0; k < 4; ++k) {
      assert(fold_result[k] == expected_result[k]);
    }

// fold_left with a lambda must return fixed_vector
    // so that the algorithm can deduce the result type.
    auto fold_lambda_result = std::ranges::fold_left(
      vec.begin(), vec.end(),
      zero,
      [] (const auto& x, const auto& y) {
        return fixed_vector<float, 4>(x + y);
      }
    );
    for (std::size_t k = 0; k < 4; ++k) {
      assert(fold_lambda_result[k] == expected_result[k]);
    }
#endif

// std::reduce with std::plus<> compiles and runs correctly,
    // because the initial value type is fixed_vector
    // and std::reduce casts the expression template type
    // (binary_plus_expr) returned from std::plus<>::operator()
    // to the initial value type. 
    auto reduce_result = std::reduce(
      vec.begin(), vec.end(), zero, std::plus<>{}
    );
    for (std::size_t k = 0; k < 4; ++k) {
      assert(reduce_result[k] == expected_result[k]);  
    }
  }

return 0;
}