使用 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_ ) )
    {}
};