5

I have a long string. In the string, I have two non-overlapping parts. They can have a gap between them. The lengths can be different.

For example a string:

This is a "foo", that is a "bar"

I need to "swap" foo and bar, to get the result:

This is a "bar", that is a "foo"

I know the positions and positions of the ends of the strings to swap.

I was able to figure out this function, by doing three rotates:

void swapInPlace(std::string& data, size_t a, size_t next_a, size_t b, size_t next_b) {
  const size_t gap_len = b - next_a;
  const size_t b_len = next_b - b;
  std::rotate(data.begin()+a, data.begin()+next_a, data.begin()+b);
  std::rotate(data.begin()+a+gap_len, data.begin()+b, data.begin()+next_b);
  std::rotate(data.begin()+a, data.begin()+a+gap_len, data.begin()+a+gap_len+b_len);
}

This works, and is without an allocation, but is it the best that can be done?

Improve this question
10
  • 2
    How about swap + rotate? Commented Sep 8 at 13:31
  • Hm, not sure what I would be swapping. But I figured out how to do it with two rotates now Commented Sep 8 at 13:35
  • How about do std::swap_ranges and one std::rotate? Anyway to do any kind of decision some tests (benchmarks) are needed. Commented Sep 8 at 13:35
  • 1
    @KarelBílek yes we know, but you can swap greatest common length and then do rotate which will cover part of longer item. Commented Sep 8 at 13:39
  • 2
    If you believe that the code works correctly, consider presenting your work (with its unit tests if you can) in a more-complete fashion over at Code Review. You'll likely get some suggestions on making it more efficient, easier to read, and better tested. Before you do that, make sure to read A guide to Code Review for Stack Overflow users first, as some things are done differently over there - e.g. question titles should simply say what the code does, as the question is always, "How can I improve this?". Commented Sep 23 at 6:45

4 Answers 4

Reset to default
6

You might swap the common size and rotate the remaining part:

void swapInPlace(std::string& s, size_t a, size_t next_a, size_t b, size_t next_b)
{
    const auto min_length = std::min(next_a - a, next_b - b);

    std::swap_ranges(s.begin() + a, s.begin() + a + min_length, s.begin() + b);
    if (next_a - a < next_b - b) {
        std::rotate(s.begin() + next_a,
                    s.begin() + b + min_length,
                    s.begin() + next_b);
    } else {
        std::rotate(s.begin() + a + min_length,
                    s.begin() + next_a,
                    s.begin() + next_b);
    }
}

Demo

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Fails on tests: godbolt.org/z/oexMb8aTd
You could skip the if-else and just call the 2 rotates. By construction, one of them will do the right thing, and the other will be a no-op. So it's the same thing performance wise, but less branching is nice :)
Not sure it will do less checks, as a check will be done in std::rotate instead. For me, It seems clearer with the condition.
Indeed, it won't do less checks. Like I said, it's not a performance difference, just a readability difference. And I can certainly understand if the explicit if-else is more readable, or conveys intent better.
2

A common implementation of rotate uses reverse. Let's do that directly:

void swapInPlace(std::string& data, size_t a, size_t next_a, size_t b, size_t next_b) {
  auto ba = data.begin() + a;
  auto ea = ba + (next_a - a);
  auto bb = data.begin() + b;
  auto eb = bb + (next_b - b);
  // example:
  //    ba  ea bb
  //    |   |  | eb
  //    |   |  | |
  //    v   v  v v
  // abc1234rst78xyz
  std::reverse(ba, ea);
  // abc4321rst78xyz
  std::reverse(ea, bb);
  // abc4321tsr78xyz
  std::reverse(bb, eb);
  // abc4321tsr87xyz
  std::reverse(ba, eb);
  // abc78rst1234xyz
}
Improve this answer

Comments

0

Solution with two rotates

void swapInPlace(std::string& s, size_t a, size_t next_a, size_t b, size_t next_b) {
    const size_t len_b = next_b - b;
    const size_t len_a = next_a - a;
    const size_t len_gap = b - next_a;

    std::rotate(s.begin() + a, s.begin() + b, s.begin() + next_b);

    const auto new_a_start = s.begin() + a + len_b;

    std::rotate(new_a_start, new_a_start + len_a, new_a_start + len_a + len_gap);
}
Improve this answer

1 Comment

Do you need all the len and new_a_start variables? Just rotate(begin + a, begin + next_a, begin + b) for the first part, and rotate(begin + a, begin + b, begin + b_next) for the second part works. (Slightly more work since the second substring gets moved a little more than strictly necessary, but in that case, the swap + rotate would be better anyway).
-1

Why restrict it to plain strings?

#include <algorithm>
#include <iterator>

template<std::random_access_iterator It>
void swap_in_place(It pa, It pz, It qa, It qz)
{
    //  Ppp...Qqqqq     or   Ppppp...Qqq
    auto pm = std::swap_ranges(qa, qz, pa);
    //  Qqqqq.Ppp..     or   Qqqpp...Ppp
    std::rotate(pm, pm < pz ? pz : qa + (pz - pa), qz);
    //  Qqqqq...Ppp     or   Qqq...Ppppp
}

Demo:

#include <iostream>
#include <string>

int main()
{
    std::wstring s{LR"--(That is a "foobar", this here is a "baz")--"};
    {
        auto pa = s.begin() + 11;
        auto pz = pa + 6;
        auto qa = s.begin() + 36;
        auto qz = qa + 3;
        swap_in_place(pa, pz, qa, qz);
        // That is a "baz", this here is a "foobar"
        std::wcout << s << '\n';
    }

    {
        auto pa = s.begin() + 1;
        auto pz = pa + 3;
        auto qa = s.begin() + 18;
        auto qz = qa + 8;
        swap_in_place(pa, pz, qa, qz);
        // This here is a "baz", that is a "foobar"
        std::wcout << s << '\n';
    }
}
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.