c++ - 表达式模板 - bad_alloc

Question

我目前正在做一个 C++ 项目，现在我已经卡住了一段时间了。这是关于使用表达式模板和(至少对我来说)一个奇怪的 bad_alloc 的延迟评估。

如果您尝试下面的代码，您会注意到由于最后一次添加 b+c 而导致的运行时错误 bad_alloc。这就是延迟评估完成的地方。此外，如果您删除“表达式”(左、右)成员的引用，下面的代码可以正常编译和运行。但由于性能等原因，我需要那里的引用资料。但是我也不明白，为什么我不能在那里使用引用。

我已经花了很多时间在上面。如果有人可以帮助我，请告诉我。

最好的问候。

#include <iostream>
#include <vector>

template<typename value_t, typename left_t, typename right_t, typename op_t>
class Expression
{
public:
    typedef value_t value_type;
    explicit Expression(const left_t &left,
                        const right_t &right,
                        const op_t &op) :
        left(left),
        right(right),
        op(op)
    {

    }
    value_t operator [](const size_t &i) const
    {
        return op(left[i],right[i]);
    }
    size_t size() const { return left.size();}
private:
    const left_t &left;
    const right_t &right;
    //const left_t left;
    //const right_t right;
    const op_t &op;
};

template<class left_t,
         class right_t,
         class value_t = typename left_t::value_type,
         class op_t = std::plus<value_t>>
const Expression<value_t, left_t, right_t, op_t> operator +(const left_t &left,
                                                            const right_t &right)
{
    return Expression<value_t,left_t,right_t,op_t>(left, right, op_t());
}

template<typename value_t, typename data_t = std::vector<value_t>>
class Vector : public data_t
{
public:
    typedef value_t value_type;
    using data_t::size;
    Vector(const std::initializer_list<value_t> &list) :
        data_t(list)
    {

    }
    Vector(const size_t &n) :
        data_t(n)
    {

    }
    Vector(const Vector &v) :
        data_t(v)
    {

    }
    template<typename left_t, typename right_t, typename op_t>
    Vector(const Expression<value_t,left_t,right_t,op_t> &v) :
        data_t(v.size())
    {
        operator =(v);
    }
    template<typename vec_t>
    Vector(const vec_t &v) :
        data_t(v.size())
    {
        operator =(v);
    }

    template<typename vec_t>
    Vector &operator =(const vec_t &v)
    {
        for(size_t i = 0; i < data_t::size(); ++i)
            data_t::operator [](i) = v[i];
        return (*this);
    }
    friend std::ostream &operator <<(std::ostream &os, const Vector &v)
    {
        if(v.size())
            os << v[0];
        for(size_t i = 1; i < v.size(); ++i)
            os << " " << v[i];
        return os;
    }
};

int main()
{
    Vector<double> a{0,1,2};
    auto b = a+a+a;
    auto c = a;
    std::cout << a+a+a+a << std::endl;
    std::cout << b+c << std::endl; // gives bad_alloc
    return 0;
}

Answer 1

"But i need references there, due to performance, etc."

证明它。

在表达式模板中，所有¹ 信息都应该是编译时的。

你可以在这里看到我的简单表达式模板示例:

// we have lazy placeholder types:
template <int N> struct placeholder {};
placeholder<1> _1;
placeholder<2> _2;
placeholder<3> _3;

// note that every type here is stateless, and acts just like a more
// complicated placeholder.
// We can have expressions, like binary addition:
template <typename L, typename R> struct addition { };
template <typename L, typename R> struct multiplication { };

// here is the "factory" for our expression template:
template <typename L, typename R> addition<L,R> operator+(L const&, R const&) { return {}; }
template <typename L, typename R> multiplication<L,R> operator*(L const&, R const&) { return {}; }

///////////////////////////////////////////////
// To evaluate/interpret the expressions, we have to define "evaluation" for each type of placeholder:
template <typename Ctx, int N> 
    auto eval(Ctx& ctx, placeholder<N>) { return ctx.arg(N); }
template <typename Ctx, typename L, typename R>
    auto eval(Ctx& ctx, addition<L, R>) { return eval(ctx, L{}) + eval(ctx, R{}); }
template <typename Ctx, typename L, typename R>
    auto eval(Ctx& ctx, multiplication<L, R>) { return eval(ctx, L{}) * eval(ctx, R{}); }

///////////////////////////////////////////////
// A simple real-life context would contain the arguments:
#include <vector>
struct Context {
    std::vector<double> _args;

    // define the operation to get an argument from this context:
    double arg(int i) const { return _args.at(i-1); }
};

#include <iostream>
int main() {
    auto foo = _1 + _2 + _3;

    Context ctx { { 3, 10, -4 } };
    std::cout << "foo: " << eval(ctx, foo) << "\n";
    std::cout << "_1 + _2 * _3: " << eval(ctx, _1 + _2 * _3) << "\n";
}

因此，您需要的是一种文字类型，它包含对关联值的引用，并将所有其他评估推迟到评估时间。

我可能更愿意将 size() 操作添加为一个自由函数，这样您就不必用它来阻碍所有表达式类型(关注点分离)。

---

¹ 几乎，nl。编码文字时除外

概念验证

使用概述的策略:

Live On Coliru

#include <iostream>
#include <tuple>

namespace ETL {
    template <typename T>
    struct Literal {
        T value;
        T get() const { return value; }
    };

    /*
     *template <typename T>
     *    static inline std::ostream& operator<<(std::ostream& os, ETL::Literal<T> const& lit) {
     *        return os << __PRETTY_FUNCTION__ << "\n actual: lit.value = " << lit.value;
     *    }
     */

    template <class L, class R, class Op> 
        struct BinaryExpr : std::tuple<L, R, Op> { // tuple optimizes for empty element types
            BinaryExpr(L l, R r, Op op) 
                : std::tuple<L, R, Op> { l, r, op }
            {}

            L const& get_lhs() const { return std::get<0>(*this); }
            R const& get_rhs() const { return std::get<1>(*this); }
            Op const& get_op() const { return std::get<2>(*this); }
        };

    template <class L, class R, class Op> auto cured(BinaryExpr<L,R,Op> _) { return _;   } 
    template <class T> auto cured(Literal<T> l)                            { return std::move(l);   } 
    template <class T> Literal<T> cured(T&& v)                             { return {std::forward<T>(v)}; }

    template <class Op, class L, class R> 
    BinaryExpr<L, R, Op> make_binexpr(L&& l, R&& r) { return { std::forward<L>(l), std::forward<R>(r), Op{} }; }

    template <class L, class R> auto operator +(L&& l, R&& r)
    { return make_binexpr<std::plus<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
    template <class L, class R> auto operator -(L&& l, R&& r)
    { return make_binexpr<std::minus<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
    template <class L, class R> auto operator *(L&& l, R&& r)
    { return make_binexpr<std::multiplies<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
    template <class L, class R> auto operator /(L&& l, R&& r)
    { return make_binexpr<std::divides<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
    template <class L, class R> auto operator %(L&& l, R&& r)
    { return make_binexpr<std::modulus<>>(cured(std::forward<L>(l)), std::forward<R>(r)); }

    template <typename T> auto val(T const& v)
    { return cured(v); }

    namespace impl {
        template <class T>
        static constexpr auto is_indexable(T const&) -> decltype(std::declval<T const&>()[0], std::true_type{}) { return {}; }
        static constexpr auto is_indexable(...) -> decltype(std::false_type{}) { return {}; }

        struct {
            template <class T> size_t operator()(T const& v) const { return (*this)(v, is_indexable(v)); }
            template <class T> size_t operator()(T const& v, std::true_type) const { return v.size(); }
            template <class T> size_t operator()(T const&, std::false_type) const { return 0; }

            template <class T> size_t operator()(Literal<T> const& l) const { return (*this)(l.value); } 
            template <class L, class R, class Op> 
                size_t operator()(BinaryExpr<L,R,Op> const& be) const { return (*this)(be.get_lhs()); } 
        } size;

        struct {

            template <class T>
                auto operator()(size_t i, T const& v) const { return (*this)(i, v, is_indexable(v)); }
            template <class T>
                auto operator()(size_t i, T const& v, std::true_type) const { return v[i]; }
            template <class T>
                auto operator()(size_t, T const& v, std::false_type) const { return v; }

            template <class T> auto operator()(size_t i, Literal<T> const& l) const { return (*this)(i, l.value); } 
            template <class L, class R, class Op> 
                auto operator()(size_t i, BinaryExpr<L,R,Op> const& be) const {
                    return be.get_op()((*this)(i, be.get_lhs()), (*this)(i, be.get_rhs()));
                } 
        } eval_at;
    }

    template <typename T> size_t size(T const& v)              { return impl::size(v); }
    template <typename T> auto   eval_at(size_t i, T const& v) { return impl::eval_at(i, v); }
}

#include <vector>

template <class value_t>
struct Vector : std::vector<value_t> {
    using data_t = std::vector<value_t>;
    typedef value_t value_type;
    using data_t::data_t;

    template <typename Expr>
        Vector(Expr const& expr) { *this = expr; }

    template <typename Expr>
        Vector& operator=(Expr const& expr) {
            this->resize(size(expr));
            for (size_t i = 0; i < this->size(); ++i)
                this->at(i) = eval_at(i, expr);
            return *this;
        }

    friend std::ostream &operator<<(std::ostream &os, const Vector &v) {
        for (auto& el : v) os << " " << el;
        return os;
    }
};

int main() {
    Vector<double> a { 1, 2, 3 };

    using ETL::operator+;
    using ETL::operator*;

    //std::cout << typeid(a + a * 4 / 2).name() << "\n";
#define DD(x) std::cout << typeid(x).name() << " size: " << ETL::size(x) << " result:" << (x) << "\n"
    DD(a * -100.0);
    auto b = a + a + a;
    auto c = a;

    std::cout << size(b)                 << "\n";
    std::cout << (a + a + a + a)         << "\n";
    std::cout << a * 4.0                 << "\n";
    std::cout << b + c                   << "\n";
    std::cout << (a + a + a + a) - 4 * a << "\n";
}

打印

ETL::BinaryExpr<ETL::Literal<Vector<double>&>, ETL::Literal<double>, std::multiplies<void> > size: 3 result: -100 -200 -300
3
 4 8 12
 4 8 12
 4 8 12
 0 0 0