如何在c ++中更快地交换函数？

Question

我正在用c ++编写一个字符串排序算法,我想知道我是否可以更快地进行这种交换操作.

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

如果你能提供帮助,我将不胜感激......

Answer 1

String类有自己的swap函数.

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

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

看到这里.

Answer 2

你可以使用std::swap():

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

但是不能保证这会快得多,而且这可能不是你代码的缓慢部分.您是否测量过交换操作与其余代码相比的性能？

得到正确答案的+1,即使你不知道它是对的;-) 21.3.7.8的C++ 03说`std :: swap`为字符串重载,它调用`swap`成员功能.21.3.5.8保证这是恒定的时间.没有关于移动语义的废话.我们不能完全确定它比提问者的代码更快,COW或其他优化的可能性将提问者的代码保存在预期的"O(n)"中,其中`n`是字符串的长度.但它很可能会更好,而且肯定不错. (4认同)
你甚至期望`std :: swap`更快吗？如果是这样的话？但是大多数情况下肯定使用`std :: swap`而且确实没有必要为它编写自己的包装器,只需直接调用即可. (2认同)
我几乎认为这应该是一个评论而不是一个答案,因为问题是如何使它更快,你提到不能保证这会更快.事实上,这可能与他已经做的完全一样. (2认同)

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函数将向传入的变量返回右值引用(T &&).当您尝试分配此右值引用时,它将调用类型的移动运算符(如果有).如果移动操作符不可用,它将照常调用复制操作符.

在这种情况下std::string,上面的交换函数将不会使用C++ 11进行字符串复制; 只复制内部数据,如字符串长度和C字符串指针.如果没有C++ 11,它将执行实际字符串内容的三个副本.

无论如何,字符串的`std :: swap`重载.C++ 03的21.3.7.8或C++ 11的21.4.8.8.因此,"如果没有C++ 11,它将执行实际字符串内容的三个副本". (2认同)