特例:交换两个变量的值
(对于一般解决方案,请参见下文。)
要在 C++ 中交换两个变量的值,您应该始终使用swap
:
using std::swap;
swap(x, y); // Do NOT say: std::swap(x, y) -- Read about Koenig lookup!
不要打扰它会怎么做;它会做得非常快。如果处理器支持,C++ 标准库的实现将尽最大努力将其优化为一条指令(但标准并没有告诉实现这样做)。对于仅寄存器变量,例如 x86 指令xchg
将尽可能快地执行此操作。不要试图用一些“三异或操作”来调整它,它不会更快。如果你不走运,它不会被优化为类似xchg
.
C++03 中的泛型swap
操作引入了一个临时变量并执行三个复制构造。在 C++11 中有移动语义,对象被移动而不是复制。对于您自己的类型,假设某些数据结构仅包含指向实际数据的指针,您应该优化此过程以使其在恒定时间内执行:
在 C++03中,您可以在命名空间中专门化std::swap
或实现自己的swap
函数(请参阅此问题的两个最佳答案)以优化交换:只需交换类中的每个成员即可交换它们的数据。对于仅包含指针的数据结构示例,只需交换指针即可。
在 C++11中,有新的移动语义,它允许您实现数据从一个对象到另一个对象的移动,这将导致非常相似的行为。(移动语义已被引入用于更一般的问题,例如交换两个对象:如果一个对象不再需要,但另一个对象必须是第一个对象的“副本”,则可以简单地移动它。)阅读移动语义和移动构造函数以获取详细信息。
对于C++03 和 C++11,还有另一种方法:您可以实现隐式共享数据和写时复制,用于重类(如数据结构)。在上面的示例中,您的数据结构包含指向实际数据的指针,请实现引用计数。复制数据结构时,只需将引用计数器加一即可。修改数据时,确保它没有被共享(ref count = 1),否则只有在那时才复制它来“分离”它。这会导致恒定时间的复制和交换操作。
一般情况:多个任意表达式
对于不依赖于输入/输出的其他语句,例如(a, b) = (x, y)
,只需“按原样”编写它们,并且它将至少完美地以流水线方式运行,因为它们没有任何依赖关系:
a = x;
b = y;
如果它们依赖于输入/输出,例如您在编辑中的示例,您可以将其拆分并引入临时对象。尝试使用一些花哨的表达技巧(例如 xor-ing)来解决这些问题,您不会帮自己一个忙。编译器知道很多汇编程序的技巧(比如xchg
),你只知道用普通 C++ 表达这些技巧(比如 xor)。
在 C++11 中,std::tuple
允许std::tie
您在不引入临时变量的情况下分配多个表达式(它们将在幕后引入以保存存储在元组中的值,并尝试完全优化它们或至少只使用寄存器来保存如果可能的话):
using std::tie;
using std::make_tuple;
tie(ones, twos) = make_tuple((ones ^ n) ^ ~twos, (ones & n) | (twos & ~n));
请注意,右侧对/元组的类型必须与左侧的目标值匹配,因为此处不隐含转换。如果遇到问题,请static_cast
在右侧执行 a,告诉std::make_tuple
显式类型或仅使用构造函数来std::tuple
要求显式类型,例如:
using std::tie;
using std::tuple;
tie(ones, twos) = tuple<int,int>((ones ^ n) ^ ~twos, (ones & n) | (twos & ~n));