C++ vector that uses expression templates technique to increase performance of mathematical expressions

Question

I've been reading Item 6 from Scott Meyers' Effective Modern C++ and noticed that he mentioned a technique called expression templates. I've decided to give it a try and implemented a vector that supports addition and subtraction:

#include <iostream>
#include <vector>
template<typename T>
class Vec
{
public:
 std::vector<T> data;
 typedef typename std::vector<T>::size_type size_type;
 Vec(size_type size): data(size)
 {
 }
 Vec(const std::initializer_list<T>& elements): data(elements.size())
 {
 size_type i = 0;
 for (const auto& el: elements)
 {
 data[i++] = el;
 }
 }
 template<typename VecOperation>
 Vec(const VecOperation& vo): data(vo.t2.data.size())
 {
 for (size_type i = 0; i < data.size(); ++i)
 {
 data[i] = vo[i];
 }
 }
 T operator[](size_type i) const
 {
 return data[i];
 }
};
template<typename T1, typename T2>
struct VecSum
{
 const T1& t1;
 const T2& t2;
 auto operator[](typename T2::size_type i) const
 {
 return t1[i] + t2[i];
 }
};
template<typename T1, typename T2>
struct VecDiff
{
 const T1& t1;
 const T2& t2;
 auto operator[](typename T2::size_type i) const
 {
 return t1[i] - t2[i];
 }
};
template<typename T1, typename T2>
auto operator+(const T1& t1, const T2& t2)
{
 return VecSum<T1, T2>{t1, t2};
}
template<typename T1, typename T2>
auto operator-(const T1& t1, const T2& t2)
{
 return VecDiff<T1, T2>{t1, t2};
}
int main()
{
 Vec<int> v1{1, 2, 3, 4, 5};
 Vec<int> v2{6, 7, 8, 9, 11};
 Vec<int> v3{3, 5, 2, 0, 17};
 Vec<int> v4 = v1+v2-v3;
 for (const auto& x: v4.data)
 {
 std::cout << x << ", ";
 }
 std::cout << std::endl;
 return 0;
}

The main advantage of this solution is that in the line Vec<int> v4 = v1+v2-v3; no additional temporaries of type Vec are created, which increases performance.

I'd be grateful if someone could point potential drawbacks and possible improvements of this code.

• Loki Astari: Very elegant solution.

Answer 1

Generally speaking, it's pretty good. However, there are still a few things that I would have done differently:

• typedef becomes kind of ugly now that we have type aliases. Always using type aliases generally tends to produce more readable and more consistent code:

  using size_type = typename std::vector<T>::size_type;
  

• Loop only when you have to. In your std::initializer_list constructor, you don't need to loop; you can use std::vector's constructor taking a pair of iterators instead:

  Vec(const std::initializer_list<T>& elements):
   data(std::begin(elements), std::end(elements))
  {
  }
  

• By the way std::initializer_list tends to be no more than a pair of pointers. You can take it directly by value instead of taking it by const reference.

• In operator+ and operator-, I would have placed the return type into the function signature and then used the list initialization syntax in the return statement:

  template<typename T1, typename T2>
  auto operator+(const T1& t1, const T2& t2)
   -> VecSum<T1, T2>
  {
   return { t1, t2 };
  }
  

  Whether it is better or not is debatable but when the return type is fixed, rather meaningful and arguably simple, I prefer to expose it in the signature.

• jiggunjer: Rather than using iterator pair, why not do data{elements} in the initializer list?
• Morwenn: @jiggunjer I don't remember the guarantees about copying std::initializer_list and lifetime problems -- the class really is a strange beast. Honestly, I hope it works but I'm not even sure. That's why I chose the iterators constructor, which I know works.
• jiggunjer: I don't understand. Brace initialization just works. Are you saying it is not in the c++ standard?

Answer 2

The problem with this library now is that the operators are capture-anything. (This also applies to the constructor). Thus they can accidentally apply to the things they are not supposed to. You have to restrict the types of arguments somehow.

For example, the code

Vec<int> v5(5);

does not compile, because the compiler selects the constructor

template<typename VecOperation>
Vec(const VecOperation& vo)

because it is a better match (the other constructor would require conversion from int to size_t).

You can either use metaprogramming (SFINAE) to restrict your template functions, or inherit Vec and all your operations from some CRTP base class, like VecBase<Derived>. (this is what Eigen does, and this library is a good example of expression template usage, although may be too complex for easily understand).

By the way, some implementations of std::valarray use expression templates as well.

• Morwenn: Good catch. CRTP might indeed be the best solution here :)