40-2-다.링크의 재배치
리스트의 노드를 연결하는 링크는 포인터이므로 조작할 수 있는 여지가 아주 많다. 다른 컨테이너에서는 요소를 직접 이동해야 하는 작업도 리스트는 링크만 재배치하여 아주 간단하게 빠른 속도로 수행할 수 있다. 리스트에는 링크 재배치의 장점을 살릴 수 있는 여러 가지 멤버 함수들이 준비되어 있다.
void swap(list& Right);
void reverse( );
void merge(list& Right);
이 함수들은 모두 전역 알고리즘 함수로도 제공된다. 리스트가 똑같은 이름의 멤버 함수를 제공하는 이유는 링크 재배치의 장점을 활용하면 일반적인 알고리즘보다 훨씬 더 빠르게 동작하기 때문이다. 예를 들어 리스트끼리 교환하는 swap 함수는 실제로 요소를 교환할 필요없이 리스트끼리 head, tail 정보만 바꾸면 간단하게 구현할 수 있다.
어차피 노드들은 메모리의 아무 곳에나 흩어져 있고 링크에 의해서만 연결되므로 시작점과 끝점의 링크만 수정하면 소속도 쉽게 바뀐다. 설사 리스트의 요소가 백만개를 넘는다 하더라도 불과 두 쌍의 포인터만 교환하면 모든 작업이 완료된다. reverse도 요소들을 거꾸로 재배치하여 일일이 옮길 필요없이 next, prev 링크를 반대로 바꾸기만 하면 되고 리스트끼리 병합하는 merge도 마찬가지로 링크를 조작하여 한쪽 리스트를 다른 쪽의 끝과 연결하기만 하면 된다.
이 함수들은 간단하게 테스트해 볼 수 있는데 앞 예제의 li.remove('l')을 li.reverse() 호출로 바꾸면 문자들이 반대로 뒤집혀 출력될 것이다. 물리적인 이동이 발생하는 것이 아니므로 뒤집는 속도도 굉장히 빠르다. swap이나 merge도 두 개의 리스트를 만든 후 교환 및 병합해 보면 쉽게 테스트할 수 있다.
링크를 조작하는 가장 멋지고도 실용적인 함수는 splice이다. splice는 새끼줄같은 것을 꼬아서 서로 잇는다는 의미인데 뜻 그대로 두 개의 리스트를 서로 잇거나 한쪽 요소들을 뽑아서 다른쪽으로 이동시킨다. 다음 세 개의 원형이 정의되어 있다.
void splice(iterator it, list& x);
void splice(iterator it, list& x, iterator first);
void splice(iterator it, list& x, iterator first, iterator last);
첫 번째 원형은 it 위치에 x리스트의 모든 요소들을 이동시킨다. 마치 작은 새끼줄을 큰 새끼줄의 허리 부근에 연결하는 것과 같다. 복사가 아닌 이동이므로 x에 있던 요소들은 모두 제거된다. x는 호출하는 객체와는 당연히 달라야 하는데 자신을 자신에게 이을 수는 없는 노릇이다.
두 번째 원형은 x의 first위치에 있는 요소 하나만 it위치로 이동시킨다. 세 번째 원형은 하나의 요소가 아니라 반복자 구간을 지정하여 일정 범위의 요소를 한꺼번에 이동시킨다는 점이 다르다. 같은 리스트내에서의 이동도 가능하므로 이 두 원형은 x가 호출하는 객체 자신이어도 상관없다. 다음 예제는 splice 함수의 세가지 원형을 모두 테스트하는데 주석을 풀어가면서 실행해 보자.
|
예 제 : splice |
#include <iostream>
#include <list>
using namespace std;
template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";
copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }
void main()
{
const char *alpha="abcdefghij";
const char *num="12345";
list<char> la(&alpha[0],&alpha[10]);
list<char> ln(&num[0],&num[5]);
list<char>::iterator ita,it1,it2;
dump("알파벳",la);dump("숫자",ln);
ita=la.begin();ita++;ita++;
it1=ln.begin();it1++;it1++;
it2=ln.end();it2--;
// 전체 이동
//la.splice(ita,ln);
// 앞쪽 2번째만 이동
// la.splice(ita,ln,it1);
// 구간 이동
la.splice(ita,ln,ln.begin(),ln.end());
dump("알파벳",la);dump("숫자",ln);
}
크기 10의 알파벳 리스트 la와 크기 5의 숫자 리스트 ln을 선언해 두고 이 두 리스트끼리 요소들을 이동해 보았다. ita가 la의 2번째 노드를 가리키도록 해 놓고 이 위치에 ln 리스트 전체를 이동해 보았다. 실행 결과는 다음과 같다.
알파벳 ==> a b c d e f g h i j
숫자 ==> 1 2 3 4 5
알파벳 ==> a b 1 2 3 4 5 c d e f g h i j
숫자 ==>
ita 자리인 c위치에 숫자 리스트의 숫자들이 모두 삽입되었고 숫자 리스트는 텅 비어 있다.
앞쪽 2번째만 이동하면 숫자 리스트의 3만 알파벳 리스트로 옮겨지며 나머지 요소들은 제자리를 그대로 유지한다. ln의 3이 b와 c사이에 링크로 연결되며 ln의 2, 4 노드끼리 연결될 것이다.
알파벳 ==> a b c d e f g h i j
숫자 ==> 1 2 3 4 5
알파벳 ==> a b 3 c d e f g h i j
숫자 ==> 1 2 4 5
구간 이동은 지정한 구간만 이동시킨다. 예제에서는 ln은 2번째 요소인 3에서부터 끝에서 1번째 요소인 4까지를 이동시켰다.
알파벳 ==> a b c d e f g h i j
숫자 ==> 1 2 3 4 5
알파벳 ==> a b 3 4 c d e f g h i j
숫자 ==> 1 2 5
전체를 이동하는 첫 번째 버전에 비해 일부만 이동된다는 차이가 있다.
사실 전체를 이동시키는 splice(it, x)는 전체 구간을 이동하는 splice(it, x.begin(),x.end())와 동일한 함수라고 할 수 있다. 구간을 이동할 때는 구간의 시작과 끝 주변의 링크들만 조작하면 된다. 중간의 노드는 링크를 조작하지 않아도 같이 따라 갈 것이다.