c++ - 使用 std::move 进行就地排列的性能

Question

我编写了一个就地排列算法[TAOCP3中的练习]，其中内部循环是

template<typename T>
void inplace_permute(T *pT, int *P, const int n)
{
  // part of the inner loop
  pT[j] = std::move(pT[k]);
  P[j] = j;

  // more logic to update j, k, etc.
}

这里，pT是要排序的元素数组，P是排列表，n是元素数量。

如果 T 是复杂类型(例如字符串)，std::move 会提高性能吗？同样重要的是，如果 T 是原始类型(例如 int？)，是否可以对其进行优化

Answer 1

我将你的问题总结为:

What does std::move do ?

基本上，std::move 使得可以使用移动构造函数和移动赋值运算符。

通常，这些接近于按位复制(它们不完全是一个)，因此性能通常与类的大小相关。

因此，std::move(someint) 和 std::move(somestring) 如果它们具有相似的大小，那么它们将具有相似的性能，即使其中一个是内置类和用户类。

但还是有一些差异。

• 在内置函数中，移动只是按位复制。由于未指定移出值，因此不需要清零。您可能希望在移动后为其分配一个已知值(0 或其他值)
• 在通常具有资源(例如动态分配的缓冲区)的用户类上，移动意味着:清理移动到的实例(用于分配)，进行按位复制，重置移动的实例-来自实例。所以还有一些工作要做。

为了理解这一点，我们可以通过示例字符串实现来说明这一点:

class String {
public:
  // Many things
  String(String&& right);
  String& operator=(String right);

  friend void swap(String& left, String& right);

private:
  // On 64 bits platform, 4x as big as an `int`
  size_t capacity;
  size_t size;
  char* buffer;
};

// Move Constructor
String::String(String&& right):
   capacity(right.capacity), size(right.size), buffer(right.buffer)
{
  right = String(); // reset right
}


// Assignment Operator
String& String::operator=(String right) {
  swap(*this, right);
  return *this;
}

// Swap
void swap(String& left, String& right) {
  using std::swap;
  swap(left.capacity, right.capacity);
  swap(left.size    , right.size);
  swap(left.buffer  , right.buffer);
}

如您所见，赋值 pT[j] = std::move(pT[k]); 的含义(语义上):

• 创建临时文件(制作 pT[k] 的按位拷贝)
• 重置pT[k]
• 在临时变量和pT[j]之间交换状态
• 销毁临时存储(通常会释放从 pT[j] 继承的存储空间)

编译器或多或少应该能够将其优化为:

• 在pT[j]和pT[k]之间交换状态
• 销毁pT[k](仅释放存储)
• 在 pT[k] 中重建一个新实例

或者，粗略地说:

swap(ptj, ptk);    // swap 3 fields
delete ptk.buffer; // might be a no-op
ptk = String();    // 0-out 3 fields

注意:这是一个玩具实现，在 gcc 上会更简单，在 VC++ 上会更复杂，因为它们使用不同的数据表示形式。