常量時間'cons'

有沒有什麼辦法（例如修改參數類型）使下面的'cons'函數花費的時間不是O（n）時間。即構建列表應該花費O（n）時間，而不是O（n^2）時間。常量時間'cons'

我可以在下列條件下這樣做的：

（1）沒有動態內存分配
（2）X仍必須保持有效（即可以不用臨時變量的引用）
（3）型頭可具有其單獨編譯一個構造（未可以內聯）的如何可以工作

#include <type_traits> 

template <typename HEAD, typename TAIL> 
struct List 
{ 
    List(HEAD head, TAIL tail) : head(head), tail(tail) {} 
    typename std::remove_reference<HEAD>::type head; 
    typename std::remove_reference<TAIL>::type tail; 
}; 

template <typename HEAD, typename TAIL> 
List<HEAD, TAIL> cons(HEAD head, TAIL tail) 
{ 
    return List<HEAD, TAIL>(head, tail); 
} 

struct Empty {}; 

int main() 
{ 
    auto x = cons(1, cons(2, cons(3, Empty()))); 
    // x should still be valid here 
}

實施例。

編譯器知道x的類型，所以在堆棧上分配空間。

使堆棧看起來是這樣的：

| Int1 | Int2 | Int3 | 
| p | p+4 | p+8 |

凡p是一個任意地址。

編譯器創建調用cons(2, cons(3, Empty()))，將返回值指向p+4。

Inside cons(2, cons(3, Empty()))，編譯器創建調用cons(3, Empty())指示返回值爲p+8。

這樣，每次調用cons時，不需要複製tail。

我只是不確定代碼，所以編譯器可以（如在，被允許）做這種優化。如果有另一種獲得不斷運行時間的方式，我很樂意使用它。

來源

2011-08-08 Clinton

我不明白你的「沒有動態內存分配」的要求。這不正是通常情況下的'缺點'嗎？ –

你能解釋一下，你現在的「cons」是線性的嗎？有一定數量的爭論沒有以任何方式進行檢查。你的意思是最後的表達？ –

所以你正在製作一個鏈表。它包含的不是對事物的引用，而是對它們的複製。所以我猜O（n^2）來自這樣一個事實：每個嵌套的'cons'調用都會拷貝它的參數，它將每個先前創建的對象複製到新的對象中。 –

我會在我的調查後給出我自己的問題的答案，但如果有人知道更好的方法，我仍然會有興趣。

（1）將List更名爲TempList。
（2）將TempList的構造函數（包括移動和複製）設爲私有。
（3）使的朋友。
（4）將HEAD和TAIL成員製作爲參考。

現在TempList只保留引用，所以沒有副本。然而，這些可能是對臨時對象的引用，但這沒關係，因爲臨時對象持續到表達式的末尾，並且因爲TempList只具有私有構造函數，所以它不能分配給表達式的LHS。只有cons可以創建一個TempList，不能活得比它創建的表達。

現在創建一個功能save或該效果，需要一個TempList並返回一個真正的List東西，有它存儲的數據的另一種類型按價值。

因此，我們必須

auto x = save(cons(1, cons(2, cons(3, Empty()))));

和數據將被複制或移動時最多一次（拯救），整個結構現在正在O(n)。只要內嵌了cons和save，TempList結構可能會被優化掉。

來源

2011-08-08 05:07:02 Clinton

這並不能解釋這比'std :: tuple （1，2，3）'更好。 –

@尼科爾·布拉斯：對不起，可能不是一個好例子，但讓我們說'而不是'cons'我們有'f1'，'f2'和'f3'。說一些像'join'，'remove'，'insert'等等的東西。你會如何爲std :: tuple編寫函數，而不用在每一步執行拷貝？ – Clinton

無論如何，你將不得不執行復制或移動任何內部的東西，因爲你的'List'本身包含實際的對象，而不是對它們的引用。你不能執行'join'，'remove'，'insert'而不復制/移動或指針。如果可以的話，它已經是'std :: tuple'的一部分。 –

你似乎正在重塑std::tuple與更糟糕的std::make_tuple幫手。改爲使用它。該標準不會爲std::tuple或std::make_tuple的轉發構造函數提供複雜性保證，但它有點不實際，因爲這兩者使用完美轉發，因此每個元素只需一次移動/複製/安置構造就可以調用std::make_tuple;剩下的就是洗牌參考。至少這是一個線性數量的結構。

當然，不能保證你的編譯器能夠優雅地處理所有的參考混洗，但是你仍然在錯誤的層次上進行優化。

爲了便於說明，幾乎但不太會發生什麼：

template<typename... T> 
class tuple { 
    T... members; // this is not correct, only here for illustration 

    // The forwarding constructor 
    template<typename... U> 
    explicit 
    tuple(U&&... u) 
     : member(std::forward<U>(u)...) 
    {} 
}; 

template<typename... T> 
tuple<typename std::decay<T>::type...> 
make_tuple(T&&... t) 
{ return tuple<typename std::decay<T>::type...>(std::forward<T>(t)...); }

因此，在調用auto tuple = std::make_tuple(1, 2, 3)，有三個臨時int■從呼叫make_tuple，然後是三個int&& xvalues從首先調用std::forward<int>(t)...在make_tuple之內，它們綁定到構造函數的參數，這些構造函數的參數再次作爲int&& xvalues轉換爲由它們構造的std::tuple<int, int, int>的概念三個成員。

只是意識到我說過結構的數只適用調用std::make_tuple，而不是整個表達式auto tuple = std::make_tuple(...);。由於元組從函數返回，因此可能需要將最後一個變量移動/ RVO。它仍然是線性的，它仍然是編譯器喜歡優化的東西之一，並且它仍然是擔心優化的錯誤地點。

然而，C++ 0x中是如此充滿了善良，它已經可以做你在你的答案描述：

int i = 3; 
std::tuple<int, int, int> tuple = std::forward_as_tuple(1, 2, i);

到forward_as_tuple的調用將返回一個std::tuple<int&&, int&&, int&>。這個幫助器永遠不會返回一個帶有值的元組，只有一個「淺」的引用元組。然後，std::tuple<int, int, int>的適當轉換構造函數將用兩個移動和一個副本初始化其「成員」。請注意，這個愚蠢的（未）優化會讓您冒險寫auto tuple = std::forward_as_tuple(1, 2, i);這是一個帶有兩個懸空引用的元組。

來源

2011-08-08 06:22:20

常量時間'cons'

回答

相關問題