如何在C++中加快交换函数的速度？

Question

我正在使用C++编写一些字符串排序算法，我想知道是否可以使这个交换操作更快。

void swap(string *items,int a, int b ){
        string temp;
        temp = items[a];
        items[a] = items[b];
        items[b] = temp;
}

I'll be appreciate if you can help...

- ibrahim

---

你确定这是你的程序性能瓶颈吗？你觉得它为什么慢？ - Seth Carnegie

我们应该忘记小的效率问题，大约97%的时间：过早优化是万恶之源。——唐纳德·科斯塔·诺思 - user406009

我猜想导致你的排序算法变慢的是需要进行交换调用的次数，而不是交换操作本身。 - Esailija

每次交换操作都会完整复制三个字符串，因此如果字符串很长，假设这会导致问题是非常现实的。 - Collin Dauphinee

然而，在那关键的3%中，我们不应错失机会。一个好的程序员不会被这种理由所麻痹，他会明智地仔细查看关键代码；但前提是要先确定哪些代码是关键的。 —— 唐纳德·科斯塔·诺思 - chill

Answer 1

String类有它自己的交换函数。

items[a].swap(items[b]);

这是最快的方法，因为它访问了字符串内部并避免了所有复制。

在此查看。

- Antti Huima

---

这是目前最好的答案，+1 - Seth Carnegie

我完全忘记了 std::string 支持交换，如果你没有 rvalue 引用（即使你有），这可能是最好的解决方案。 - Collin Dauphinee

请注意，Greg的答案保证该函数将被使用。 - GManNickG

请注意，这是更一般的 std::swap() 内部执行的操作。 - sth

@sth 特定类具有与STL中同名函数的方法的原因是，这些方法对于特定类而言比一般的STL模板函数更快。我在某本书中读到过。 - xcrypt

通用函数应在适当时调用特定类的方法。 - sth

Answer 2

您可以使用 std::swap()：

void swap(string *items, int a, int b) {
    std::swap(items[a], items[b]);
}

但是这并不能保证代码速度会有显著提升，而且这可能也不是你的代码中最慢的部分。你是否测试过与代码其他部分相比，交换操作的性能表现如何呢？

- Greg Hewgill

---

你会期望std::swap更快吗？如果是，为什么？但是最好使用std::swap，而且没有必要编写自己的包装器，直接调用即可。 - David Heffernan

我几乎认为这应该是一条评论而不是答案，因为问题是如何使它更快，而你提到没有保证这会更快。实际上，这可能正好与他已经在做的事情完全相同。 - Seth Carnegie

@DavidHeffernan：我认为std::swap会更快，特别是在C++11中，移动构造器的语义可以比三个赋值运算符更好。 - Greg Hewgill

这应该肯定放在答案里。 - David Heffernan

即使你不知道答案是正确的，得到正确答案还是要点赞的；C++03标准的21.3.7.8指出std::swap针对字符串进行了重载，并调用了swap成员函数。根据21.3.5.8保证这是常数时间操作，不会有任何关于移动语义的麻烦。我们无法完全确定它是否比提问者的代码更快，因为可能存在COW或其他优化能将提问者的代码从预期的O(n)（其中n是字符串的长度）中解救出来。但这很可能更好，而且肯定不差。 - Steve Jessop

Answer 3

使用std::swap；它将尽可能地完成最优秀的工作。如果您的编译器支持C++11的右值引用，这意味着它将利用移动语义来避免在交换函数中发生的复制。

然而，如果您的编译器不支持右值引用，它很可能会像您的交换函数一样执行。

大多数标准库实现将实现std::swap类似于以下内容：

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

std::move 函数将返回传入变量的 rvalue 引用（T&&）。当您尝试分配这个 rvalue 引用时，如果类型有可用的移动操作符，则会调用它。如果没有移动操作符，则像平常一样调用复制操作符。

在 std::string 的情况下，上面的 swap 函数在 C++11 中不会进行字符串拷贝，只会拷贝内部数据，如字符串长度和 C 字符串指针。而没有 C++11，则需要执行三次实际字符串内容的拷贝。

- Collin Dauphinee

---

无论如何，对于字符串，std::swap有一个重载。C++03的21.3.7.8或C++11的21.4.8.8。因此，“没有C++11，它将执行三个实际字符串内容的副本”这种说法是不正确的。 - Steve Jessop

Answer 4

你可以将算法更改为适用于类型为string*的元素，而不是string。然后，在你的swap函数中的所有赋值都将操作指针，并且速度更快，因为不涉及字符串复制。

- TotoroTotoro