C++ 使用std :: move将复杂度从O（n²）降低到O(n)
示例
C++11引入了用于移动对象的核心语言和标准库支持。这个想法是，当一个对象o是一个临时对象并且想要一个逻辑副本时，它可以安全地窃取o的资源（例如动态分配的缓冲区），而在逻辑上则是o空的，但仍然是可破坏和可复制的。
核心语言支持主要是
的右值引用类型助洗剂&&，例如，std::string&&是一个右值参照std::string，表示的是称为对象是临时其资源可以只被窃取（即移动）
对move构造函数的特殊支持，该构造函数T(T&&)应该有效地从指定的其他对象移动资源，而不是实际复制这些资源，并且
对移动分配运算符的特殊支持，该运算符autooperator=(T&&)->T&也应该从源头移动。
标准库支持主要std::move是<utility>标题中的功能模板。此函数产生对指定对象的右值引用，表明可以将其移出，就像它是临时的一样。
对于容器，实际复制通常具有O（n）复杂度，其中n是容器中的项目数，而移动是O(1)，即恒定时间。和一种算法，逻辑上拷贝该容器Ñ倍，这可以从通常不切实际O（减少复杂性Ѳ）只是线性O（Ñ）。
在2013年9月19日发表于DobbsJournal博士的文章“永不改变的容器”中，安德鲁·科尼格（AndrewKoenig）提出了一个有趣的算法效率低下的示例，该算法在初始化后变量不可变的编程风格下使用。使用这种样式，循环通常使用递归表示。对于某些算法（例如生成Collatz序列），递归需要逻辑上复制容器：
//基于安德鲁·科尼格（AndrewKoenig）在他的《多布斯杂志》（DobbsJournal）文章中的示例
//“不变的容器”，2013年9月19日，可在以下网站获取：
// <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>() );
}
} //我的命名空间
#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²），因为它是1+2+3+...n的总和。
具体而言，在g++和VisualC++编译器中，上述的调用collatz(42)导致在VectorCopy构造函数调用中产生8个项目和36个项目复制操作的Collatz序列（8*7/2=28，另加一些）。
所有这些项目复制操作都可以通过简单移动不再需要其值的向量来删除。为此，有必要删除const和引用向量类型参数，并通过value传递向量。函数返回已自动优化。对于传递了矢量的调用，但在函数中不再使用它们的调用，仅适用std::move于移动这些缓冲区，而不是实际复制它们：
using std::move;
auto concat( Vector_<int> v, int const x )
-> Vector_<int>
{
v.push_back( x );
//警告：在return语句中移动本地对象会防止复制省略[-Wpessimizing-move]
// See https://stackoverflow.com/documentation/c%2b%2b/2489/copy-elision
//返回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; //绝对要确保此后不使用`result`。
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++和VisualC++编译器，由于矢量复制构造函数的调用而导致的项目复制操作的数量恰好为0。
该算法是必需仍然O（Ñ）中制备的在Collatz序列的长度，但是这是一个相当显着的改善：O（ñ²）→O（Ñ）。
有了某种语言支持，人们也许可以使用移动，并且仍然可以在变量的初始化和最终移动之间表达和强制执行变量的不变性，此后对该变量的任何使用都将是一个错误。C，从C++14开始，C++不支持该功能。对于无循环代码，可以通过将相关名称重新声明为不完整来强制执行事后使用struct，就像structresult;上面一样，但这很丑陋，其他程序员不太可能理解；诊断也可能会产生误导。
总结起来，C++语言和库对移动的支持可以大大提高算法的复杂性，但是由于支持的不完整，以放弃提供的代码正确性保证和代码清晰度为代价const。
为了完整起见，插入式矢量类用于测量由于复制构造函数调用而导致的项目复制操作的数量：
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_) )
{}
};