使交换更快,更易于使用和异常安全

Question

我昨晚无法入睡,开始思考std::swap.这是熟悉的C++ 98版本:

template <typename T>
void swap(T& a, T& b)
{
    T c(a);
    a = b;
    b = c;
}

如果用户定义的类Foo使用外部资源,则效率低下.常用的习语是提供一种方法void Foo::swap(Foo& other)和一种专业化std::swap<Foo>.请注意,这不适用于类模板,因为您不能部分地专门化函数模板,并且重std命名命名空间中的名称是非法的.解决方案是在一个人自己的命名空间中编写模板函数,并依赖于参数依赖查找来查找它.这主要取决于客户端遵循" using std::swap成语"而不是std::swap直接调用.非常脆弱.

在C++ 0x中,如果Foo有一个用户定义的移动构造函数和一个移动赋值运算符,提供一个自定义swap方法和一个特化std::swap<Foo>几乎没有性能优势,因为C++ 0x版本std::swap使用高效的移动而不是副本:

#include <utility>

template <typename T>
void swap(T& a, T& b)
{
    T c(std::move(a));
    a = std::move(b);
    b = std::move(c);
}

不必再捣乱swap已经从程序员那里承担了很多负担.当前的编译器不会自动生成移动构造函数和移动赋值运算符,但据我所知,这将改变.剩下的唯一问题是异常安全,因为一般来说,允许移动操作,这会打开一大堆蠕虫.问题是"移动对象的状态究竟是什么？" 使事情进一步复杂化.

然后我在想,std::swap如果一切顺利的话,C++ 0x 中的语义究竟是什么？交换之前和之后的对象状态是什么？通常,通过移动操作进行交换不会触及外部资源,只会触及"平面"对象表示本身.

那么为什么不简单地编写一个swap完全相同的模板:交换对象表示？

#include <cstring>

template <typename T>
void swap(T& a, T& b)
{
    unsigned char c[sizeof(T)];

    memcpy( c, &a, sizeof(T));
    memcpy(&a, &b, sizeof(T));
    memcpy(&b,  c, sizeof(T));
}

这是有效的:它只是通过原始内存爆炸.它不需要用户的任何干预:不必定义特殊的交换方法或移动操作.这意味着它甚至可以在C++ 98中工作(没有右值引用,请注意).但更重要的是,我们现在可以忘记异常安全问题,因为memcpy从不抛出.

我可以看到这种方法存在两个潜在的问题:

首先,并非所有对象都要交换.如果类设计者隐藏了复制构造函数或复制赋值运算符,则尝试交换该类的对象应该在编译时失败.我们可以简单地引入一些死代码来检查复制和赋值是否合法:

template <typename T>
void swap(T& a, T& b)
{
    if (false)    // dead code, never executed
    {
        T c(a);   // copy-constructible?
        a = b;    // assignable?
    }

    unsigned char c[sizeof(T)];

    std::memcpy( c, &a, sizeof(T));
    std::memcpy(&a, &b, sizeof(T));
    std::memcpy(&b,  c, sizeof(T));
}

任何体面的编译器都可以轻而易举地摆脱死代码.(可能有更好的方法来检查"交换一致性",但这不是重点.重要的是它是可能的).

其次,某些类型可能会在复制构造函数和复制赋值运算符中执行"异常"操作.例如,他们可能会通知观察者他们的变化.我认为这是一个小问题,因为这类对象可能不应该首先提供复制操作.

请让我知道你对这种交换方法的看法.它会在实践中起作用吗？你会用吗？你能识别出会破坏的库类型吗？你看到其他问题吗？讨论!

Answer 1

那么为什么不简单地编写一个swap完全相同的模板:交换 对象表示*？

一个对象一旦被构造,就会有很多种方式在你复制它所在的字节时会破坏.事实上,人们可能会想出一些看似无穷无尽的案例,这些案例不会做正确的事情 - 即使在实践中它可能在98%的情况下起作用.

这是因为所有这一切的根本问题在于,除了在C中,在C++中,我们不能将对象视为仅仅是原始字节.毕竟,这就是为什么我们需要构建和销毁:将原始存储转换为对象和对象回原始存储.一旦构造函数运行,对象所在的内存不仅仅是原始存储.如果你把它视为不是,那么你会破坏某些类型.

但是,基本上,移动对象的性能不应该比你的想法差得多,因为一旦你开始递归地内联调用std::move(),你通常最终会到达内置函数移动的位置.(如果有更多的东西可以移动某些类型,你最好不要动摇那些你自己的记忆!)当然,整体移动内存通常比单个移动快(并且编译器不太可能发现它可以优化个体移动到一个无所不包的std::memcpy()),但这是我们为不透明对象提供给我们的抽象所付出的代价.而且它非常小,特别是当你将它与我们以前的复制进行比较时.

但是,您可以对聚合类型进行优化swap()使用.std::memcpy()

Answer 2

这将破坏具有指向其自己成员的指针的类实例.例如:

class SomeClassWithBuffer {
  private:
    enum {
      BUFSIZE = 4096,
    };
    char buffer[BUFSIZE];
    char *currentPos; // meant to point to the current position in the buffer
  public:
    SomeClassWithBuffer();
    SomeClassWithBuffer(const SomeClassWithBuffer &that);
};

SomeClassWithBuffer::SomeClassWithBuffer():
  currentPos(buffer)
{
}

SomeClassWithBuffer::SomeClassWithBuffer(const SomeClassWithBuffer &that)
{
  memcpy(buffer, that.buffer, BUFSIZE);
  currentPos = buffer + (that.currentPos - that.buffer);
}

现在,如果你只是做memcpy(),currentPos指向哪里？到了旧位置,显然.这将导致非常有趣的错误,每个实例实际上使用另一个缓冲区.

Answer 3

某些类型可以交换但不能复制.独特的智能指针可能是最好的例子.检查可复制性和可分配性是错误的.

如果T不是POD类型,则使用memcpy进行复制/移动是未定义的行为.

常见的习惯用法是提供一个方法void Foo :: swap(Foo&other)和std :: swap <Foo>的特化.请注意,这不适用于类模板,...

更好的习惯用法是非成员交换并要求用户调用swap不合格,因此ADL适用.这也适用于模板:

struct NonTemplate {};
void swap(NonTemplate&, NonTemplate&);

template<class T>
struct Template {
  friend void swap(Template &a, Template &b) {
    using std::swap;
#define S(N) swap(a.N, b.N);
    S(each)
    S(data)
    S(member)
#undef S
  }
};

关键是std :: swap的使用声明作为后备.Template's swap的友谊对于简化定义很有帮助; NonTemplate的交换也可能是朋友,但这是一个实现细节.

Answer 4

我认为这是一个小问题,因为这类对象可能不应该首先提供复制操作.

也就是说,非常简单,一堆错误.通知观察者和不应复制的类的类完全不相关.shared_ptr怎么样？它显然应该是可复制的,但它显然也会通知观察者 - 引用计数.现在确实,在这种情况下,交换后引用计数是相同的,但对于所有类型肯定不是这样,如果涉及多线程则尤其如此,在常规副本的情况下不是这样,而不是交换等.对于可以移动或交换但不复制的类,这尤其错误.

因为一般来说,允许移动操作

他们绝对不是.几乎不可能在任何涉及移动的情况下保证强大的异常安全性.标准库的C++ 0x定义(从内存中)明确指出任何标准容器中可用的类型在移动时都不能抛出.

这是有效的

那也是错的.你假设任何对象的移动纯粹是它的成员变量 - 但它可能不是全部.我可能有一个基于实现的缓存,我可能会决定在我的课程中,我不应该移动这个缓存.作为一个实现细节,完全在我的权利范围内,不移动我认为不需要移动的任何成员变量.但是,你想要移动所有这些.

现在,您的示例代码确实对许多类都有效.但是,对于许多完全合法的类来说,它绝对非常有效,而且更重要的是,如果操作可以减少到那个,那么无论如何它都会编译成该操作.这打破了完美的好课程,绝对没有任何好处.