欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn) vector 的四則運(yùn)算

 更新時(shí)間:2016年07月17日 09:06:35   投稿:hebedich  
本文給大家介紹的是在C++中實(shí)現(xiàn)高效的vector四則運(yùn)算的方法的相關(guān)資料,需要的朋友可以參考下

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

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;
}

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

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

因此求值就變成一次簡單的中序遍歷,那么我們的 vector 運(yùn)算是否也可以這樣做呢?

表達(dá)式模板

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

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";
    }
  }
};

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

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

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

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

#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] << " ";
  }
}

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

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

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

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

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

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

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

神奇的 boost::proto

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

相關(guān)文章

  • C++ OpenCV讀寫XML或YAML文件的方法詳解

    C++ OpenCV讀寫XML或YAML文件的方法詳解

    XML是一種元標(biāo)記語言。所謂元標(biāo)記,就是開發(fā)者可以根據(jù)自身需要定義自己的標(biāo)記。YAML是一個(gè)可讀性高,用來表達(dá)資料序列的格式。本文將通過C++和OpenCV實(shí)現(xiàn)這兩種文件的讀寫,需要的可以參考一下
    2022-05-05
  • C語言中冒泡排序算法詳解

    C語言中冒泡排序算法詳解

    大家好,本篇文章主要講的是C語言中冒泡排序算法詳解,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-01-01
  • C++深入講解初始化列表的用法

    C++深入講解初始化列表的用法

    這篇文章主要介紹了C++成員初始化列表,除了可以使用構(gòu)造函數(shù)對類成員進(jìn)行初始化之外,C++還提供了另外一種初始化的方法,叫做成員初始化列表。下面來看看文章的詳細(xì)吧,需要的朋友可以參考一下
    2022-04-04
  • 基于Matlab實(shí)現(xiàn)俄羅斯方塊游戲

    基于Matlab實(shí)現(xiàn)俄羅斯方塊游戲

    俄羅斯方塊是一個(gè)最初由阿列克謝帕吉特諾夫在蘇聯(lián)設(shè)計(jì)和編程的益智類視頻游戲。本文將利用Matlab實(shí)現(xiàn)這一經(jīng)典的小游戲,需要的可以參考一下
    2022-03-03
  • 淺談C語言之字符串處理函數(shù)

    淺談C語言之字符串處理函數(shù)

    下面小編就為大家?guī)硪黄獪\談C語言之字符串處理函數(shù)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2016-08-08
  • C++ CTreeview的checkbox使用方法

    C++ CTreeview的checkbox使用方法

    這篇文章主要介紹了C++ CTreeview的checkbox使用方法的相關(guān)資料,需要的朋友可以參考下
    2015-06-06
  • c++網(wǎng)絡(luò)編程下Linux的epoll技術(shù)和Windows下的IOCP模型

    c++網(wǎng)絡(luò)編程下Linux的epoll技術(shù)和Windows下的IOCP模型

    c++ 網(wǎng)絡(luò)編程LINUX-epoll/windows-IOCP下socket opoll函數(shù)用法 優(yōu)于select方法的epoll 以及windows下IOCP 解決多進(jìn)程服務(wù)端創(chuàng)建進(jìn)程資源浪費(fèi)問題,感興趣的小伙伴一起來學(xué)習(xí)吧
    2021-08-08
  • C語言員工信息管理系統(tǒng)源代碼

    C語言員工信息管理系統(tǒng)源代碼

    這篇文章主要為大家詳細(xì)介紹了C語言員工信息管理系統(tǒng)源代碼,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-12-12
  • C++實(shí)現(xiàn)秒表功能

    C++實(shí)現(xiàn)秒表功能

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)秒表功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • C語言實(shí)現(xiàn)信號(hào)槽的項(xiàng)目實(shí)踐

    C語言實(shí)現(xiàn)信號(hào)槽的項(xiàng)目實(shí)踐

    信號(hào)槽是觀察者模式的一種實(shí)現(xiàn),一個(gè)信號(hào)就是一個(gè)能夠被觀察的事件,本文主要介紹了C語言實(shí)現(xiàn)信號(hào)槽的項(xiàng)目實(shí)踐模具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-04-04

最新評論