{"id":111962,"date":"2026-01-05T07:00:00","date_gmt":"2026-01-05T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=111962"},"modified":"2026-01-03T08:01:34","modified_gmt":"2026-01-03T16:01:34","slug":"20260105-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20260105-00\/?p=111962","title":{"rendered":"How can you swap two non-adjacent blocks of memory using only forward iterators?"},"content":{"rendered":"

Last time, we looked at how you can swap two adjacent blocks of memory using only forward iterators<\/a> and noted that we can try to use the same trick to develop a forward-only solution to the problem of swapping two non-adjacent blocks of memory<\/a>.<\/p>\n

Our original diagram looked like this, with a block of memory of the form A1, A2, B1, B2, C1, C2, D1, D2, D3, E1, and the goal of swapping the B’s and D’s, producing A1, A2, D1, D2, D3, C1, C2, B1, B2, E1.<\/p>\n\n\n\n\n\n\n\n\n\n
A1<\/td>\nA2<\/td>\nB1<\/td>\nB2<\/td>\nC1<\/td>\nC2<\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nE1<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u2929<\/td>\n\u00a0<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
A1<\/td>\nA2<\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nC1<\/td>\nC2<\/td>\nB1<\/td>\nB2<\/td>\nE1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The first thing we’ll do is get rid of the A’s and E’s, since they aren’t really participants at all.<\/p>\n\n\n\n\n\n\n\n\n\n
B1<\/td>\nB2<\/td>\nC1<\/td>\nC2<\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u2929<\/td>\n\u00a0<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
D1<\/td>\nD2<\/td>\nD3<\/td>\nC1<\/td>\nC2<\/td>\nB1<\/td>\nB2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

If either the B or D block is empty, then we are left with a rotation, and we already know how to do that using only forward iterators.<\/p>\n

Otherwise, start with first<\/code> pointing at the start of B and mid<\/code> pointing at the start of D.<\/p>\n\n\n\n\n\n
B1<\/td>\nB2<\/td>\nB3<\/td>\nC1<\/td>\nC2<\/td>\nD1<\/td>\nD2<\/td>\n <\/td>\n<\/tr>\n
\u2191<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u2191<\/td>\n\u00a0<\/td>\n\u2191<\/td>\n<\/tr>\n
first<\/td>\nmid<\/td>\nlast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Walk forward from first<\/code> and mid<\/code>, swapping the initial elements from B and D, until you either run out of B elements or run out of D elements.<\/p>\n

Again, there are three cases.<\/p>\n

If the B block is bigger than the D block, then our first pass finishes with the first<\/code> pointer somewhere in the middle of the B block and the mid<\/code> pointer making it all the way to the last<\/code>.<\/p>\n\n\n\n\n\n
D1<\/td>\nD2<\/td>\nB3<\/td>\nC1<\/td>\nC2<\/td>\nB1<\/td>\nB2<\/td>\n <\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u2191<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u2191<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\nfirst<\/td>\nmid
\nlast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The entire D block is in its final position, and getting the B3 block to the end is a rotation of [first<\/code>, last<\/code>) that moves C1 to the front, and we can use the existing forward-only rotation algorithm to finish the job.<\/p>\n

The second case is that the D block is bigger than the B block. In this case, we finish with the first<\/code> pointer at the end of the original B block and the mid<\/code> in the middle of the original D block.<\/p>\n\n\n\n\n\n
D1<\/td>\nD2<\/td>\nC1<\/td>\nC2<\/td>\nB1<\/td>\nB2<\/td>\nD3<\/td>\n <\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u2191<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u2191<\/td>\n\u2191<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\nfirst<\/td>\nmid<\/td>\nlast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Again, we can finish the job with a forward-only rotation, this time rotating the [first<\/code>, last<\/code>) block to put mid<\/code> at the front.<\/p>\n

The final case is that there are exactly the same number of B’s and D’s: All of the D’s have moved to the front and all of the B’s have moved to the back.<\/p>\n\n\n\n
D1<\/td>\nD2<\/td>\nC1<\/td>\nC2<\/td>\nB1<\/td>\nB2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

In this case, we are finished.<\/p>\n

This final case does not need to be treated as a special case. We can just treat it as either of the first two cases, and the right thing will happen since the final forward-only rotation will realize that there is nothing to rotate. In fact, the vacuous case at the start (where either there are no B’s or no D’s) does not need to be treated as a special case either.<\/p>\n

This algorithm performs n<\/var> swaps because we perform k<\/var> swaps in the first phase, and the rotation in the second phase is known to perform n<\/var>\u00a0\u2212\u00a0k<\/var> swaps. You can also calculate this directly by observing that every swap moves one element to its final position.<\/p>\n","protected":false},"excerpt":{"rendered":"

Applying the rotation trick to our new problem.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-111962","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

Applying the rotation trick to our new problem.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111962","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=111962"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111962\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=111962"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=111962"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=111962"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}