如何在C/C++中以O(1)时间复杂度交换两个字符串？

代码错误根源 #

你尝试直接给变量的地址赋值（(&buyer)=(&seller);），这是完全错误的——变量在内存中的地址是编译期固定的常量，根本无法被修改，这就是你触发语法错误的原因。

为什么不需要手动操作地址？ #

C++标准库的std::swap针对std::string已经做了极致优化，它的时间复杂度就是O(1)，完全不会复制字符串的字符内容。因为std::string内部通过指针管理堆上的字符缓冲区，swap操作只是交换两个字符串对象的内部指针、大小、容量等成员变量，全程不涉及字符拷贝。

正确实现方式 #

方式1：直接使用std::swap（推荐） #

这是最简单高效的写法，标准库已经帮你完成了最优实现：

#include <iostream>
#include <string>

int main ()
{
  std::string buyer ("money");
  std::string seller ("goods");
  
  std::cout << "Before swap: buyer = " << buyer << ", seller = " << seller << '\n';
  
  std::swap(buyer, seller); // O(1)操作，无字符复制
  
  std::cout << "After swap: buyer = " << buyer << ", seller = " << seller << '\n';

  return 0;
}

方式2：用指针间接交换（若坚持指针逻辑） #

如果你想通过指针实现“交换指向”的效果，可以用指针变量指向原字符串对象，然后交换指针的指向——注意：这里交换的是指针变量的值，而非原字符串对象的地址：

#include <iostream>
#include <string>

int main ()
{
  std::string buyer ("money");
  std::string seller ("goods");
  std::string *p_buyer = &buyer;
  std::string *p_seller = &seller;
  
  std::cout << "Before swap: *p_buyer = " << *p_buyer << ", *p_seller = " << *p_seller << '\n';
  std::cout << "Pointer addresses: p_buyer = " << p_buyer << ", p_seller = " << p_seller << '\n';
  
  // 交换指针的指向
  std::string *temp = p_buyer;
  p_buyer = p_seller;
  p_seller = temp;
  
  std::cout << "After swap: *p_buyer = " << *p_buyer << ", *p_seller = " << *p_seller << '\n';
  std::cout << "Pointer addresses: p_buyer = " << p_buyer << ", p_seller = " << p_seller << '\n';

  return 0;
}

这种方式同样不会复制字符，只是改变了指针指向的对象，也是O(1)操作。

总结 #

• 永远不要试图修改变量的地址，这是C++语法不允许的行为。
• std::swap(std::string&, std::string&)本身就是O(1)效率，直接使用即可，无需自行实现。
• 若要用指针实现交换逻辑，交换的是指针变量的值，而非原对象的地址。

内容的提问来源于stack exchange，提问作者Md. Saidul Islam