No - std::rotate is just doing this with in-place swaps.
Say you have "A1 A2 B1" and want to rotate (swap) adjacent blocks A1-A2 and B1, where WLOG the smaller of these is B1, and A1 is same size as B1.
What you do is first swap B1 with A1 (putting B1 into it's final place).
B1 A2 A1
Now recurse to swap A2 and A1, giving the final result:
B1 A1 A2
Swapping same-size blocks (which is what this algorithm always chooses to do) is easy since you can just iterate though both swapping corresponding pairs of elements. Each block only gets moved once since it gets put into it's final place.
I see it says that it may throw bad_alloc, but it's not clear why, since the algorithm itself (e.g see "Possible implementation" below) can easily be done in-place.
I'm wondering if the bad_alloc might be because a single temporary element (of whatever type the iterators point to) is going to be needed to swap each pair of elements, or maybe to allow for an inefficient implementation that chose not to do it in-place?
Comments
No - std::rotate is just doing this with in-place swaps.
Say you have "A1 A2 B1" and want to rotate (swap) adjacent blocks A1-A2 and B1, where WLOG the smaller of these is B1, and A1 is same size as B1.
What you do is first swap B1 with A1 (putting B1 into it's final place).
B1 A2 A1
Now recurse to swap A2 and A1, giving the final result:
B1 A1 A2
Swapping same-size blocks (which is what this algorithm always chooses to do) is easy since you can just iterate though both swapping corresponding pairs of elements. Each block only gets moved once since it gets put into it's final place.
You are thinking of std::swap, std::rotate does throw bad_alloc
I see it says that it may throw bad_alloc, but it's not clear why, since the algorithm itself (e.g see "Possible implementation" below) can easily be done in-place.
https://en.cppreference.com/w/cpp/algorithm/rotate.html
I'm wondering if the bad_alloc might be because a single temporary element (of whatever type the iterators point to) is going to be needed to swap each pair of elements, or maybe to allow for an inefficient implementation that chose not to do it in-place?