使用 stdmove 降低從 O(n2) 到 O(n)的複雜性

Created: November-22, 2018

C++ 11 引入了用於移動物件的核心語言和標準庫支援。我們的想法是，當一個物件 Ø 是暫時的，一個想要一個邏輯副本，那麼它的安全，只是被盜 Ø 的資源，比如一個動態分配的緩衝區，留下 Ø 邏輯上為空，但還是破壞，能夠複製。

核心語言支援主要是

右值引用型別構建 &&，例如 std::string&& 是一個右值參照 std::string，表明其稱為物件是臨時其資源可以只被竊取（即移動）
對移動建構函式 T( T&& ) 的特殊支援，它應該有效地從指定的其他物件移動資源，而不是實際複製這些資源，以及
對移動賦值運算子 auto operator=(T&&) -> T& 的特殊支援，它也應該從源移動。

標準庫支援主要是來自 <utility> 頭的 std::move 功能模板。此函式生成對指定物件的右值引用，指示它可以從中移動，就像它是臨時的一樣。

對於容器，實際複製通常具有 O（ n ）複雜度，其中 n 是容器中的專案數，而移動是 O(1)，恆定時間。和一種演算法，邏輯上拷貝該容器 N 倍，這可以從通常不切實際Ó降低複雜度（ N ²）只是線性 O（ N ）。

在 2013 年 9 月 19 日 Dobbs Journal 博士的文章 容器永不改變中，Andrew Koenig 提出了一個有趣的演算法效率低的例子，當使用一種程式設計風格，其中變數在初始化後是不可變的。使用此樣式迴圈通常使用遞迴表示。對於某些演算法（如生成 Collatz 序列），遞迴需要邏輯複製容器：

// Based on an example by Andrew Koenig in his Dr. Dobbs Journal article
// `Containers That Never Change` September 19, 2013, available at
// <url: http://www.drdobbs.com/cpp/containters-that-never-change/240161543>

// Includes here, e.g. <vector>

namespace my {
    template< class Item >
    using Vector_ = /* E.g. std::vector<Item> */;

    auto concat( Vector_<int> const& v, int const x )
        -> Vector_<int>
    {
        auto result{ v };
        result.push_back( x );
        return result;
    }

    auto collatz_aux( int const n, Vector_<int> const& result )
        -> Vector_<int>
    {
        if( n == 1 )
        {
            return result;
        }
        auto const new_result = concat( result, n );
        if( n % 2 == 0 )
        {
            return collatz_aux( n/2, new_result );
        }
        else
        {
            return collatz_aux( 3*n + 1, new_result );
        }
    }

    auto collatz( int const n )
        -> Vector_<int>
    {
        assert( n != 0 );
        return collatz_aux( n, Vector_<int>() );
    }
}  // namespace my

#include <iostream>
using namespace std;
auto `main()` -> int
{
    for( int const x : my::collatz( 42 ) )
    {
        cout << x << ' ';
    }
    cout << '\n';
}

輸出：

42 21 64 32 16 8 4 2

由於複製向量而導致的專案複製操作的數量大致為 O（ n 2 ），因為它是 1 + 2 + 3 + … n 的和。

具體而言，使用 g ++和 Visual C++編譯器，上面的 collatz(42) 呼叫導致了一個包含 8 個專案的 Collatz 序列和 36 個專案複製操作（8 * 7/2 = 28，加上一些）在向量複製建構函式呼叫中。

** 通過簡單地移動不再需要其值的向量，可以移除所有這些專案複製操作。要做到這一點，有必要刪除 const 和向量型別引數的引用，按值傳遞向量。函式返回已自動優化。對於傳遞向量的呼叫，並且在函式中不再使用，只需應用 std::move 來移動那些緩衝區而不是實際複製它們：

using std::move;

auto concat( Vector_<int> v, int const x )
    -> Vector_<int>
{
    v.push_back( x );
    // warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
    // See https://stackoverflow.com/documentation/c%2b%2b/2489/copy-elision
    // return move( v );
    return v;
}

auto collatz_aux( int const n, Vector_<int> result )
    -> Vector_<int>
{
    if( n == 1 )
    {
        return result;
    }
    auto new_result = concat( move( result ), n );
    struct result;      // Make absolutely sure no use of `result` after this.
    if( n % 2 == 0 )
    {
        return collatz_aux( n/2, move( new_result ) );
    }
    else
    {
        return collatz_aux( 3*n + 1, move( new_result ) );
    }
}

auto collatz( int const n )
    -> Vector_<int>
{
    assert( n != 0 );
    return collatz_aux( n, Vector_<int>() );
}

在這裡，使用 g ++和 Visual C++編譯器，由於向量複製建構函式呼叫而導致的項複製運算元正好為 0。

該演算法是必需仍然 O（ N ）中製備的在 Collatz 序列的長度，但是這是一個相當顯著的改善：O（ ñ ²）→O（ N ）。

通過一些語言支援，人們可以使用移動，並且仍然表達並強制執行變數在其初始化和最終移動之間的不變性，之後對該變數的任何使用都應該是錯誤。唉，從 C++ 14 開始，C++不支援這一點。對於無迴圈程式碼，移動後的使用可以通過重新宣告相關名稱作為不完整的 struct 強制執行，與上面的 struct result; 一樣，但這很難看，並且不太可能被其他程式設計師理解; 診斷也可能會產生誤導。

總而言之，C++語言和庫支援移動可以大大提高演算法的複雜性，但是由於支援的不完整性，代價是放棄了程式碼正確性保證和程式碼清晰度。

為了完整性，用於測量由於複製建構函式呼叫而導致的項複製運算元的已檢測向量類：

template< class Item >
class Copy_tracking_vector
{
private:
    static auto `n_copy_ops()`
        -> int&
    {
        static int value;
        return value;
    }
    
    vector<Item>    items_;
    
public:
    static auto `n()` -> int { return n_copy_ops(); }

    void push_back( Item const& o ) { items_.push_back( o ); }
    auto `begin()` const { return items_.begin(); }
    auto `end()` const { return items_.end(); }

    `Copy_tracking_vector()`{}
    
    Copy_tracking_vector( Copy_tracking_vector const& other )
        : items_( other.items_ )
    { `n_copy_ops()` += items_.size(); }

    Copy_tracking_vector( Copy_tracking_vector&& other )
        : items_( move( other.items_ ) )
    {}
};