핵심 요약
Microsoft Developer가 대형 메모리 블록에서 비연속 두 구간을 추가 메모리 없이 교환하는 알고리즘을 소개합니다. 세 번의 회전으로 교환하는 기본 아이디어와 std::rotate의 작동 원리, 역전 트릭으로 비용을 낮추는 방식을 다룹니다. 분석에 따르면 일반적인 세 회전은 교환 대상 전체 길이 n에 대해 2n 스왑이 들고, 역전 트릭을 직접 적용하면 총 n 스왑으로 줄어듭니다.
구현 방법
- swap_discontiguous처럼 두 구간의 비연속 교환에 네 차례의 std::reverse를 활용하는 방법
- 먼저 두 구간의 양쪽을 각각 역전하고, 중간 부분을 역전하고, 마지막으로 전체를 역전하는 순서의 아이디어
- std::rotate의 forward 이터레이터 지원과 고정된 특수화에 따른 최적화 포인트
주요 결과
- 일반적으로 세 회전하는 경우 2n 스왑, 역전 트릭으로 n 스왑까지 감소
- 추가로, std::rotate가 forward 이터레이터만으로도 동작하는 점과 라이브러리 차원에서의 최적화 사례가 존재
