這里假設(shè) vector 的運算定義為對操作數(shù) vector 中相同位置的元素進行運算，最后得到一個新的 vector。具體來說就是，假如 vector<int> d1{1, 2, 3}, d2{4, 5, 6};則， v1 + v2 等于 {5, 7, 9}。實現(xiàn)這樣的運算看起來并不是很難，一個非常直觀的做法如下所示：

vector<int> operator+(const vector<int>& v1, const vector<int>& v2) {
  // 假設(shè) v1.size() == v2.size()
  vector<int> r;

  r.reserve(v1.size());
  for (auto i = 0; i < v1.size(); ++i) {
    r.push_back(v1[i] + v2[i]);
  }
  return r;
}

// 同理，需要重載其它運算符
我們針對 vector 重載了每種運算符，這樣一來，vector 的運算就與一般簡單類型無異，實現(xiàn)也很直白明了，但顯然這個直白的做法有一個嚴(yán)重的問題：效率不高。效率不高的原因在于整個運算過程中，每一步的運算都產(chǎn)生了中間結(jié)果，而中間結(jié)果是個 vector，因此每次都要分配內(nèi)存，如果參與運算的 vector 比較大，然后運算又比較長的話，效率會比較低，有沒有更好的做法呢？

既然每次運算產(chǎn)生中間結(jié)果會導(dǎo)致效率問題，那能不能優(yōu)化掉中間結(jié)果？回過頭來看，這種 vector 的加減乘除與普通四則運算并無太大差異，在編譯原理中，對這類表達(dá)式進行求值通?？梢酝ㄟ^先把表達(dá)式轉(zhuǎn)為一棵樹，然后通過遍歷這棵樹來得到最后的結(jié)果，結(jié)果的計算是一次性完成的，并不需要保存中間狀態(tài)，比如對于表達(dá)式：v1 + v2 * v3，我們通常可以先將其轉(zhuǎn)化為如下樣子的樹：

因此求值就變成一次簡單的中序遍歷，那么我們的 vector 運算是否也可以這樣做呢？

表達(dá)式模板

要把中間結(jié)果去掉，關(guān)鍵是要推遲對表達(dá)式的求值，但 c++ 不支持 lazy evaluation，因此需要想辦法把表達(dá)式的這些中間步驟以及狀態(tài)，用一個輕量的對象保存起來，具體來說，就是需要能夠?qū)⒈磉_(dá)式的中間步驟的操作數(shù)以及操作類型封裝起來，以便在需要時能動態(tài)的執(zhí)行這些運算得到結(jié)果，為此需要定義類似如下這樣一個類：

enum OpType {
  OT_ADD,
  OT_SUB,
  OT_MUL,
  OT_DIV,
};

class VecTmp {
  int type_;
  const vector<int>& op1_;
  const vector<int>& op2_;

public:
  VecTmp(int type, const vector<int>& op1, const vector<int>& op2)
    : type_(type), op1_(op1), op2_(op2) {}

  int operator[](const int i) const {
    switch(type_) {
      case OT_ADD: return op1_[i] + op2_[i];
      case OT_SUB: return op1_[i] - op2_[i];
      case OT_MUL: return op1_[i] * op2_[i];
      case OT_DIV: return op1_[i] / op2_[i];
      default: throw "bad type";
    }
  }
};

有了這個類，我們就可以把一個簡單的運算表達(dá)式的結(jié)果封裝到一個對象里面去了，當(dāng)然，我們得先將加法操作符(以及其它操作符)重載一下：

VecTmp operator+(const vector<int>& op1, const vector<int>& op2) {
  return VecTmp(OT_ADD, op1, op2);
}

這樣一來，對于 v1 + v2，我們就得到了一個非常輕量的 VecTmp 對象，而該對象可以很輕松地轉(zhuǎn)化 v1 + v2 的結(jié)果(遍歷一遍 VecTmp 中的操作數(shù))。但上面的做法還不能處理 v1 + v2 * v3 這樣的套嵌的復(fù)雜表達(dá)式：v2 * v3 得到一個 VecTmp，那 v1 + VecTmp 怎么搞呢？

同理，我們還是得把 v1 + VecTmp 放到一個輕量的對象里，因此最好我們的 VecTmp 中保存的操作數(shù)也能是 VecTmp 類型的，有點遞歸的味道。。。用模板就可以了，于是得到如下代碼：

#include <vector>
#include <iostream>

using namespace std;

enum OpType {
  OT_ADD,
  OT_SUB,
  OT_MUL,
  OT_DIV,
};

template<class T1, class T2>
class VecSum {
    OpType type_;
  const T1& op1_;
  const T2& op2_;
 public:
  VecSum(int type, const T1& op1, const T2& op2): type_(type), op1_(op1), op2_(op2) {}
 
    int operator[](const int i) const {
      switch(type_) {
        case OT_ADD: return op1_[i] + op2_[i];
        case OT_SUB: return op1_[i] - op2_[i];
        case OT_MUL: return op1_[i] * op2_[i];
        case OT_DIV: return op1_[i] / op2_[i];
        default: throw "bad type";
      }
    }
};

template<class T1, class T2>
VecSum<T1, T2> operator+(const T1& t1, const T2& t2) {
  return VecSum<T1, T2>(OT_ADD, t1, t2);
}

template<class T1, class T2>
VecSum<T1, T2> operator*(const T1& t1, const T2& t2) {
  return VecSum<T1, T2>(OT_MUL, t1, t2);
}

int main() {
  std::vector<int> v1{1, 2, 3}, v2{4, 5, 6}, v3{7, 8, 9};
  auto r = v1 + v2 * v3;
  for (auto i = 0; i < r.size(); ++i) {
    std::cout << r[i] << " ";
  }
}

上面的代碼漂亮地解決了前面提到的效率問題，擴展性也很好而且對 vector 來說還是非侵入性的，雖然實現(xiàn)上乍看起來可能不是很直觀，除此也還有些小問題可以更完善些：

操作符重載那里很可能會影響別的類型，因此最好限制一下，只針對 vector 和 VecTmp 進行重載，這里可以用 SFINAE 來處理。

VecTmp 的 operator[] 函數(shù)中的 switch 可以優(yōu)化掉，VecTmp 模板只需增加一個參數(shù)，然后對各種運算類型進行偏特化就可以了。

VecTmp 對保存的操作數(shù)是有要求的，只能是 vector 或者是 VecTmp<>，這里也應(yīng)該用 SFINAE 強化一下限制，使得用錯時出錯信息好看些。

現(xiàn)在我們來重頭再看看這一小段奇怪的代碼，顯然關(guān)鍵在于 VecTmp 這個類，我們可以發(fā)現(xiàn)，它的接口其實很簡單直白，但它的類型卻可以是那么地復(fù)雜，比如說對于 v1 + v2 * v3 這個表達(dá)式，它的結(jié)果的類型是這樣的： VecTmp<vector<int>, VecTmp<vector<int>, vector<int>>>，如果表達(dá)式再復(fù)雜些，它的類型也就更復(fù)雜了，如果你看仔細(xì)點，是不是還發(fā)現(xiàn)這東西和哪里很像？像一棵樹，一棵類型的樹。

這棵樹看起來是不是還很眼熟，每個葉子結(jié)點都是 vector，而每個內(nèi)部結(jié)點則是由 VecTmp 實例化的：這是一棵類型的樹，在編譯時就確定了。這種通過表達(dá)式在編譯時得到的復(fù)雜類型有一個學(xué)名叫： Expression template。在 c++ 中每一個表達(dá)式必產(chǎn)生一個結(jié)果，而結(jié)果必然有類型，類型是編譯時的東西，結(jié)果卻是運行時的。像這種運算表達(dá)式，它的最終類型是由其中每一步運算所產(chǎn)生的結(jié)果所對應(yīng)的類型組合起來所決定的，類型確定的過程其實和表達(dá)式的識別是一致的。

VecTmp 對象在邏輯上其實也是一棵樹，它的成員變量 op1_, op2_ 則分別是左右兒子結(jié)點，樹的內(nèi)部結(jié)點代表一個運算，葉子結(jié)點則為操作數(shù)，一遍中序遍歷下來，得到的就是整個表達(dá)式的值。

神奇的 boost::proto

expression template 是個好東西(就正如 expression SFINAE 一樣)，它能幫助你在編譯時建立非常復(fù)雜好玩的類型系統(tǒng)（從而實現(xiàn)很多高級玩意，主要是函數(shù)式)。但顯然如果什么東西都需要自己從頭開始寫，這個技術(shù)用起來還是很麻煩痛苦的，好在模板元編程實在是個太好玩的東西，已經(jīng)有很多人做了很多先驅(qū)性的工作，看看 boost proto 吧，在 c++ 的世界里再打開一扇通往奇怪世界的大門

最新評論