How to swap two strings in O(1) time complexity in C or C++?

Question

I want to swap two string without copying all the characters as it takes more time. I think using address of the strings it can be done within O(1) time complexity. But I am not being able to figure it out. Can you help me to do it?

I tried it using address. But there is some syntax error.

#include <bits/stdc++.h>
using namespace std;

int main ()
{
  std::string buyer ("money");
  std::string seller ("goods");
  string *temp;
  
  std::cout << "Before the swap, buyer has " << buyer;
  std::cout << " and seller has " << seller << '\n';
  cout<< " Before the swap "<<(&buyer)<<" "<<(&seller)<<"\n";
  temp=(&buyer); (&buyer)=(&seller); (&seller)=temp;
  cout<< " After the address swap "<<(&buyer)<<" "<<(&seller)<<"\n";
  swap (buyer,seller);
  cout<< " After the built-in swap "<<(&buyer)<<" "<<(&seller)<<"\n";

  return 0;
}

You can't change the address of an object. To swap two strings, using either `std::swap` or `std::string::swap` — NathanOliver, Mar 01 '23 at 15:49
I have exciting news for you: using move semantics this can be done in `O(1)`! — Sam Varshavchik, Mar 01 '23 at 15:49
[cppreference](https://en.cppreference.com/w/cpp/string/basic_string/swap) seems to suggest that using `std::string::swap` is rather better than O(n). — Adrian Mole, Mar 01 '23 at 15:50
[`std::swap`](https://en.cppreference.com/w/cpp/string/basic_string/swap2) already is O(1), so look no further — Yksisarvinen, Mar 01 '23 at 15:53
@Yksisarvinen doesn't the swap function copy all the characters? — Md. Saidul Islam, Mar 01 '23 at 15:58
When I see `#include ` or `using namespace std;`, I downvote a question immediately. — 273K, Mar 01 '23 at 15:58
@Md.SaidulIslam `std::swap` will use move mechanics if it can so you will only get a copy when the string is small enough to fit in the SSO buffer. — NathanOliver, Mar 01 '23 at 16:02
@273K Well I want to do that too. But then again it is hard for beginners to know what "good" sources and "bad" sources to learn from are... — Pepijn Kramer, Mar 01 '23 at 16:03
Looks like you are not learning c++ from a good source. Good sources to learn cpp from are : A [recent C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or have a go at https://www.learncpp.com/ (that's pretty decent, and pretty up-to-date). For C++ reference material use : [cppreference](https://en.cppreference.com/w/). And after you learned the C++ basics from those sources, look at the [C++ coreguidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) regularely to keep up-to-date with the latest guidelines. — Pepijn Kramer, Mar 01 '23 at 16:03

Jeremy Friesner · Answer 1 · 2023-03-01T16:00:50.567

As the commenters have pointed out, std::swap(buyer, seller) does what you want in O(1) (by swapping the pointer member-variables inside the two strings, not by copying strings' characters), so there's no reason to use pointer-indirection except perhaps as a learning exercise.

So, as a learning example only, here's how you could do it using just pointers:

#include <string>
#include <iostream>

int main ()
{
  std::string buyer ("money");
  std::string seller ("goods");

  std::string * temp1 = &buyer;
  std::string * temp2 = &seller;

  std::cout << "Before the swap, buyer has " << *temp1;
  std::cout << " and seller has " << *temp2 << '\n';

  // These three lines are equivalent to std::swap(temp1, temp2)
  std::string * temp3 = temp1;
  temp1 = temp2;
  temp2 = temp3;

  std::cout << "After the swap, buyer has " << *temp1;
  std::cout << " and seller has " << *temp2 << '\n';

  return 0;
}

another good learning exercise could be to implement a `O(1)` swap for eg `struct foo { std::string value; };`. I mean swapping pointers is always cheap and requires no copy — 463035818_is_not_an_ai, Mar 01 '23 at 16:00

How to swap two strings in O(1) time complexity in C or C++?

1 Answers1