如何用c++ template 解決這個需求?

有一個一維數組,對其中每個元素做平均數(mean value),即對周圍N個相鄰元素求和再除以元素個數,偽代碼表示為:

Array make_mean(Array input, int N) {
Array res;
for(int i = 0; i &< Array.len(); i++) { if (i - N &< 0) { // 相鄰元素在數組左邊界外,求平均數 res[i] = ...; } else if (i + N &>= Array.len()) { // 超過右邊界,求平均數
res[i] = ...;
} else { // 相鄰元素都在邊界內,求平均數
res[i] = ...;
}
}
return res;
}

現在我想用c++ template實現這個功能 (更加generalized),模板參數為相鄰元素操作函數(或類)代替上面的...,即 make_mean& (input, N)。只要這個模板參數只要滿足input是數組的一個元素,輸出的是一個操作後的結果。

我的問題是如果這個my_operator只訪問一個元素本身,我可以理解。但如果它依賴於該元素周圍的元素,應該如何實現呢?

=========================================

為了使問題明確進行下補充。

如果目標是對數組的每個元素進行單一操作(例如加1),樓主明白如何實現這個模板函數和模板參數。現在的問題是對每個元素進行一個依賴於鄰居元素的操作,那麼應如何實現這個模板參數my_operator?


template&
T[N] make_mean(T (input)[N], size_t n, OP op)
{
T res[N];
if(n&>=N)
throw std::out_of_range("range over array size.");
for(size_t i = 0; i &< N; i++) { if (i - n &< 0) { // 相鄰元素在數組左邊界外,求平均數 res[i] = op(input, input+n+i); } else if (i + n &>= N) { // 超過右邊界,求平均數
res[i] = op(input+i-n, input+N);
} else { // 相鄰元素都在邊界內,求平均數
res[i] = op(input+i-n, input+n+i);
}
return res;
}


先說清楚一點:用template去解決數組並不是一個好的方案。因為數組由兩個因素共同決定:類型和長度(這就是為什麼說數組是複合類型)。因此,即使類型不改變,只要長度變了,類型就變了。

比如,int a[3]和int b[4],a和b是兩個不同的類型。

而模板會根據不同的類型去實例化不同的函數。因此用模板函數去處理數組的結果就是:每當你傳遞一個不同長度的數組時,就會有一個相應的函數被實例化出來。因此這樣做並不是一個很好的方案除非你可以保證你的數組長度很少變化。如果你不能保證,那麼最好用vector來處理。

==============================================================

沒仔細看你的題目,這裡給你舉個例子:寫一個函數,接收一個int數組為參數,將數組中每個元素加1,然後返回數組。

傳統c++:

template&
int (func(int (arr)[N]))[N]
{
for(int i = 0; i &< N; i++) { arr[i] += 1; } return arr; }

上面這個函數的參數是引用,返回值也是引用,這是必須的:

參數必須是引用,因為不能用一個數組名去初始化另一個數組。(下面也有解釋)

返回值必須是引用,因為在函數返回(return)後,所有在該函數內定義的數據(除new以外)會全部釋放,因此函數不能返回函數作用範圍內定義的數組,只能返回同樣是引用傳遞進來的數組

由於參數是引用,因此傳遞進去的是外面已經存在的數組,該函數拿到數組後直接對數組進行處理,最後返回的還是同一個數組。這就意味著,經過這個函數處理的數組本身會發生變化。

也就是說:

int arr[3] = {1, 2, 3};
func(arr); // 此後arr變成了2, 3, 4
int res[3] = func(arr); // ERROR!!! 不能用一個數組像這樣去初始化另一個數組
int * p = func(arr); // 正確,可以用數組名去初始化一個指針。此時p指向arr。

c++11:

在c++11里,我們提倡程序員使用std::array,而避免使用int[]形式的數組。std::array就類似java中的數組了,比如可以獲取它的長度(std::array::size())。

template&
std::array& func2(std::array& arr)
{
std::array& res{arr};
for(auto e : res)
{
e += 1;
}
return res;
}

在這裡,參數可以是引用也可以不是,當然是更好,因為可以省去複製拷貝的工作。而返回值必須不能是引用。同樣的道理:res是在函數作用範圍內定義的,在函數返回(return)後,res就已經被釋放了,因此不能返回它的引用。編譯器在return res時,會把res拷貝到一個臨時對象中,所以你在外面拿到的func2的返回值其實是這個臨時對象而不是res(res已經被釋放了)。

int arr[3] = {1, 2, 3};
auto a = func2(arr); // 此後arr沒有任何變化,a是新的數組{2, 3, 4}

在這裡可以看到func2在return時,把res拷貝到一個臨時對象中,然後在外面之行auto a = func2(arr)時,再把臨時對象拷貝給a。這樣就拷貝了兩次,非常消耗資源。不過在c++11里,這個問題已經不必擔心了,因為有了右值引用。具體請樓主自己去學,這裡就不解釋了。

再強調一次,上面的方法其實並不好除非你可以保證只用這個函數處理數組長度很少變化的情況。

比如,你用func函數處理int a[3], int b[3], int c[3],這沒事,只有一個函數被實例化。而如果你用func處理 int aa[3], int bb[4], int cc[5],那麼你就會獲得三個實例化出來的函數,這樣代碼會變得很長。在這種情況下,這樣設計函數就顯然不合適了,應該考慮用vector等容器而不要用數組了。


這個問題用隊列做更容易吧


可以搞一個deque來緩存一下前面的元素


推薦閱讀:

TAG:C | 元編程 | 模板C |