3

Please consider the following (partial) implementation of a mathematical vector class (which is basically the code you can find in the Wikipedia article about expression templates):

namespace math
{
    template<class E>
    class vector_expression
    {
    public:
        std::size_t size() const {
            return static_cast<E const&>(*this).size();
        }

        double operator[](size_t i) const
        {
            if (i >= size())
                throw std::length_error("");
            return static_cast<E const&>(*this)[i];
        }

        operator E&() { return static_cast<E&>(*this); }
        operator E const&() const { return static_cast<E const&>(*this); }
    }; // class vector_expression

    template<class E1, class E2>
    class vector_sum
        : public vector_expression<vector_sum<E1, E2>>
    {
    public:
        vector_sum(vector_expression<E1> const& e1, vector_expression<E2> const& e2)
            : m_e1(e1), m_e2(e2)
        {
            if (e1.size() != e2.size())
                throw std::logic_error("");
        }

        std::size_t size() const {
            return m_e1.size(); // == m_e2.size()
        }

        double operator[](std::size_t i) const {
            return m_e1[i] + m_e2[i];
        }

    private:
        E1 const& m_e1;
        E2 const& m_e2;
    }; // class vector_sum

    template<typename E1, typename E2>
    vector_sum<E1, E2> operator+(vector_expression<E1> const& e1, vector_expression<E2> const& e2) {
        return { e1, e2 };
    }

    template<typename T>
    class vector
        : public vector_expression<vector<T>>
    {
    public:
        vector(std::size_t d)
            : m_data(d)
        { }
        vector(std::initializer_list<T> init)
            : m_data(init)
        { }
        template<class E>
        vector(vector_expression<E> const& expression)
            : m_data(expression.size())
        {
            for (std::size_t i = 0; i < expression.size(); ++i)
                m_data[i] = expression[i];
        }

        std::size_t size() const {
            return m_data.size();
        }

        double  operator[](size_t i) const { return m_data[i]; }
        double& operator[](size_t i) { return m_data[i]; }

    private:
        std::vector<T> m_data;
    }; // class vector    
} // namespace math

How should I extend this implementation to allow the following operations:

vector<double> x = { ... };
auto y = 4711 * x; // or y = x * 4711
auto z = 1 + x; // or x + 1, which should yield z[i] = x[i] + 1

I suppose that I need something like

namespace math
{
    template<class E, typename T>
    class vector_product
        : public vector_expression<vector_product<E, T>>
    {
    public:
        vector_product(vector_expression<E> const& e, T const& t)
            : m_e(e), m_t(t)
        { }

        std::size_t size() const {
            return m_e.size();
        }

        double operator[](std::size_t i) const {
            return m_e[i] * m_t;
        }

    private:
        E const& m_e;
        T const& m_t;
    }; // class vector_product

    template<class E, typename T>
    vector_product<E, T> operator*(vector_expression<E> const& e, T const& t) {
        return { e, t };
    }
    template<class E, typename T>
    vector_product<E, T> operator*(T const& t, vector_expression<E> const& e) {
        return e * t;
    }   
} // namespace math

but I don't know whether or not this is a good approach. So, how should I do it? And should I add any copy or move constructor/assignment operator? I guess not, since the implicit ones should do a perfect job, cause the only member variable of vector is a STL type.

0xbadf00d
  • 17,405
  • 15
  • 67
  • 107
  • 1
    Please note that `vector_product` is a badly chosen name, cause it might be confused with the cross product between three dimensional vectors. – 0xbadf00d Feb 24 '16 at 21:42
  • You could call it `scalar_mutliplication`? Or `scalar_closure`. – erip Feb 24 '16 at 22:14
  • Why don't you just overload `operator*` for your vector class? – erip Feb 24 '16 at 22:18
  • @erip That would be a name inconsistent to `vector_sum`. – 0xbadf00d Feb 24 '16 at 22:19
  • @erip Suppose I just overload `operator*`. Which code would be produced for `z = 3 * x + 2 * y`? `3 * x` and `2 * y` would be of type `vector` (which is a `vector_expression`) and then `operator+` would be called. It seems like that no temporaries would be constructed. Should be fine, shouldn't it? I thought we would the same technique used for `operator+` in order to prevent the implementation from producing inefficient code. [I assume you know why I don't overload `operator+`] – 0xbadf00d Feb 24 '16 at 22:25

3 Answers3

2

I would simply extend vector_sum to allow for E2 to be double, and to handle that gracefully if it is. This would involve taking arguments of E1 const& and E2 const& in your constructor, potentially not throwing on size differences (since scalars have no size), and rewriting operator[] to not do indexing. For the last part, something like:

    double operator[](std::size_t i) const {
        return m_e1[i] + get(m_e2, i);
    }

private:
    template <class E>
    double get(E const& rhs, std::size_t i) const {
        return rhs[i];
    }

    double get(double scalar, std::size_t ) const {
        return scalar;
    }

This way, if you're adding two vector_expressions, you'll do the indexing, but if you're adding a vector_expression and a double - you won't even try to index into the double. This switch happens at compile-time, so there's no run-time overhead.

Then, all you just need to add a couple more operator+s:

template <typename E1>
vector_sum<E1, double> operator+(vector_expression<E1> const& e1, double d) {
        return {e1, d};
}

template <typename E1>
vector_sum<E1, double> operator+(double d, vector_expression<E1> const& e1) {
        return {e1, d};
}

Which lets you write:

math::vector<int> x = {1, 2, 3, 4};
math::vector<int> y = {2, 3, 4, 5};    
auto sum = 3 + x + 1;

Keeping references to const probably isn't the right thing to do - if you did a+b+c, you'll end up keeping a reference to the temporary a+b. You probably only want to keep a reference to the actual vector, and keep copies of all the intermediate objects.


To support vector_product, you'll probably want vector_sum<E1,E2> to really be vector_binary_op<E1,E2,std::plus<>> and then vector_product<E1,E2> should be vector_binary_op<E1,E2,std::multiplies<>>. That way, you won't have all the duplication.

Barry
  • 286,269
  • 29
  • 621
  • 977
2

Inspired by Yakk and Barry, I've finally come up with the following:

namespace math
{
    template<class E>
    class expression
    {
    public:
        auto size() const {
            return static_cast<E const&>(*this).size();
        }

        auto operator[](std::size_t i) const
        {
            if (i >= size())
                throw std::length_error("");
            return static_cast<E const&>(*this)[i];
        }

        operator E&() { return static_cast<E&>(*this); }
        operator E const&() const { return static_cast<E const&>(*this); }
    }; // class expression

    template<typename T, class Allocator = std::allocator<T>>
    class vector
        : public expression<vector<T>>
    {
    private:
        using data_type = std::vector<T, Allocator>;
        data_type m_data;

    public:
        using value_type = T;
        using allocator_type = Allocator;
        using size_type = typename data_type::size_type;
        using difference_type = typename data_type::difference_type;
        using reference = typename data_type::reference;
        using const_reference = typename data_type::const_reference;
        using pointer = typename data_type::pointer ;
        using const_pointer = typename data_type::const_pointer;

        vector(size_type d)
            : m_data(d)
        { }
        vector(std::initializer_list<value_type> init)
            : m_data(init)
        { }
        template<class E>
        vector(expression<E> const& expression)
            : m_data(expression.size())
        {
            for (size_type i = 0; i < expression.size(); ++i)
                m_data[i] = expression[i];
        }

        size_type size() const {
            return m_data.size();
        }

        value_type  operator[](size_type i) const { return m_data[i]; }
        value_type& operator[](size_type i)       { return m_data[i]; };
    }; // class vector

    namespace detail
    {
        template<typename T>
        class scalar
            : public expression<scalar<T>>
        {
        public:
            using value_type = T;
            using allocator_type = std::allocator<void>;
            using size_type = typename std::allocator<T>::size_type;
            using difference_type = typename std::allocator<T>::difference_type;
            using reference = typename std::allocator<T>::reference;
            using const_reference = typename std::allocator<T>::const_reference;
            using pointer = typename std::allocator<T>::pointer;
            using const_pointer = typename std::allocator<T>::const_pointer;

            scalar(value_type value)
                : m_value(value)
            { }

            size_type size() const {
                return 0;
            }

            operator value_type&() { return static_cast<value_type&>(*this); }
            operator value_type const&() const { return static_cast<value_type const&>(*this); }

            value_type  operator[](size_type i) const { return m_value; }
            value_type& operator[](size_type i) { return m_value; }

        private:
            value_type m_value;
        }; // class scalar

        template<class>
        struct is_scalar : std::false_type { };

        template<class T>
        struct is_scalar<scalar<T>> : std::true_type { };
    } // namespace detail

    template<class E1, class E2, class BinaryOperation>
    class vector_binary_operation
        : public expression<vector_binary_operation<E1, E2, BinaryOperation>>
    {
    public:
        using value_type = decltype(BinaryOperation()(typename E1::value_type(), typename E2::value_type()));
        using allocator_type = std::conditional_t<
            detail::is_scalar<E1>::value,
            typename E2::allocator_type::template rebind<value_type>::other,
            typename E1::allocator_type::template rebind<value_type>::other>;

    private:
        using vector_type = vector<value_type, allocator_type>;

    public:
        using size_type = typename vector_type::size_type;
        using difference_type = typename vector_type::difference_type;
        using reference = typename vector_type::reference;
        using const_reference = typename vector_type::const_reference;
        using pointer = typename vector_type::pointer;
        using const_pointer = typename vector_type::const_pointer;

        vector_binary_operation(expression<E1> const& e1, expression<E2> const& e2, BinaryOperation op)
            : m_e1(e1), m_e2(e2),
              m_op(op)
        {
            if (e1.size() > 0 && e2.size() > 0 && !(e1.size() == e2.size()))
                throw std::logic_error("");
        }

        size_type size() const {
            return m_e1.size(); // == m_e2.size()
        }

        value_type operator[](size_type i) const {
            return m_op(m_e1[i], m_e2[i]);
        }

    private:
        E1 m_e1;
        E2 m_e2;
        //E1 const& m_e1;
        //E2 const& m_e2;
        BinaryOperation m_op;
    }; // class vector_binary_operation

    template<class E1, class E2>
    vector_binary_operation<E1, E2, std::plus<>>
    operator+(expression<E1> const& e1, expression<E2> const& e2) {
        return{ e1, e2, std::plus<>() };
    }
    template<class E1, class E2>
    vector_binary_operation<E1, E2, std::minus<>>
    operator-(expression<E1> const& e1, expression<E2> const& e2) {
        return{ e1, e2, std::minus<>() };
    }
    template<class E1, class E2>
    vector_binary_operation<E1, E2, std::multiplies<>>
    operator*(expression<E1> const& e1, expression<E2> const& e2) {
        return{ e1, e2, std::multiplies<>() };
    }
    template<class E1, class E2>
    vector_binary_operation<E1, E2, std::divides<>>
    operator/(expression<E1> const& e1, expression<E2> const& e2) {
        return{ e1, e2, std::divides<>() };
    }

    template<class E, typename T>
    vector_binary_operation<E, detail::scalar<T>, std::divides<>>
    operator/(expression<E> const& expr, T val) {
        return{ expr, detail::scalar<T>(val), std::divides<>() };
    }
    template<class E, typename T>
    vector_binary_operation<E, detail::scalar<T>, std::multiplies<>>
    operator*(T val, expression<E> const& expr) {
        return{ expr, detail::scalar<T>(val), std::multiplies<>() };
    }
    template<class E, typename T>
    vector_binary_operation<E, detail::scalar<T>, std::multiplies<>>
    operator*(expression<E> const& expr, T val) {
        return{ expr, detail::scalar<T>(val), std::multiplies<>() };
    }
} // namespace math

This allows the operations +, -, /, * for two vectors of the same size as well as the multiplication a * x and x * a of a vector x and a value a. Moreover, we can divide x / a, but not a / x (since that makes no sense). I think that this is the most plausible solution.

However, there are still some issues: I've added an Allocator template parameter to the vector class. In vector_binary_operation I need to know the resulting vector type. It would be possible that both expressions have a different allocator_type. I've decided to choose the allocator_type of the first expression in vector_binary_operation. I don't think that this is a real problem, since I don't think that it would make much sense to use different Allocators in this scenario.

The bigger issue is that I don't know how I need to deal with the expression member variables in vector_binary_operation. It would make sense to declare them as const references, cause the whole point of the code is to avoid unnecessary copies. However, as Barry pointed out, if we write sum = a + b + c, we will end up keeping a reference to the temporary a + b. Doing sum[0] will call operator()[0] on that temporary. But that object was deleted after the previous line.

I don't know what I need to do here and asked another question.

Community
  • 1
  • 1
0xbadf00d
  • 17,405
  • 15
  • 67
  • 107
1

Make a specializattion of template<class E> class vector_expression for E=double.

Add in concept of min/max size (as doubles are 0 to infinite dimension), and maybe is_scalar (might not be needed, except cast-to-scalar?).

Kill vector_sum and take its toys. Make binop_vector that takes a elementop on the elements.

Add

friend binop_vector<vector_expression,R,ElemAdd>
operator+( vector_expression const& l. R const& r ){
  return {l,r};
}
friend binop_vector<vector_expression<double>,vector_expression,ElemAdd>
operator+( double const& l. vector_expression const const& r ){
  return {l,r};
}

And similar for * with ElemMult to vector_expression. Ths binop uses the element wise operation to implement [].

Change asserts to ensure you have overlapping min/max sizes. Report intersection in binop_vector.

The vector_expression<double> overload has a min 0 max -1 (size_t) and always returns its value. If you need more than one scalar type, write scalar_expression<T> and inherit vector_expression<double> (etc) from it.

The above is not tested, just written on phone as I sit in garage.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524