40-2-나.삽입, 삭제

삽입, 삭제 함수도 벡터와 동일하다. 멤버 함수의 이름뿐만 아니라 원형까지 동일하며 사용 방법도 물론 똑같다.

iterator insert(iterator it, const T& x = T());

void insert(iterator it, size_type n, const T& x);

void insert(iterator it, const_iterator first, const_iterator last);

iterator erase(iterator it);

iterator erase(iterator first, iterator last);

다만 처리 속도는 벡터보다 훨씬 빠른데 위치와 요소 개수에 상관없이 상수 시간내에 삽입, 삭제된다. 속도가 빠르다는 것 외에도 반복자가 무효화되지 않는 장점도 있다. 삽입, 삭제되는 노드와 앞 뒤 노드의 링크만 바뀌므로 나머지 노드들은 위치에 전혀 변화가 없다. 단, 삭제되는 노드의 반복자만 예외적으로 무효화된다. 간단한 함수지만 잘 동작하는지 확인은 해 봐야 하므로 예제만 구경해 보자.

예 제 : listinsert

#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 *str="abcdefghij";

list<char> lc(&str[0],&str[10]);

list<char>::iterator it;

dump("최초",lc);

it=lc.begin();it++;it++;it++;it++;it++;

lc.insert(it,'Z');

dump("Z 삽입",lc);

it=lc.end();it--;it--;it--;

lc.erase(it);

dump("h삭제",lc);

}

문자형의 리스트 lc를 선언하고 a ~ j까지 10개의 알파벳 문자를 저장해 놓았다. 시작 위치에서 다섯 번 뒤로 이동한 후 이 위치에 'Z' 문자를 insert 함수로 삽입했다. f문자앞에 Z가 삽입될 것이다. 그리고 끝에서 세칸 앞쪽으로 이동한 후 erase 함수로 이 위치를 삭제했다. 끝에서 세 번째에는 h문자가 있는데 이 문자가 삭제될 것이다.

++을 여러 번 사용하여 이동하는 것이 무척 마음에 안들겠지만 리스트의 반복자는 양방향 반복자가 아니므로 it += 5 연산으로 한꺼번에 다섯 칸을 이동할 수는 없다. 양방향 반복자는 링크를 따라 차례대로 이동하는 수밖에 없다. 꼭 한 번에 이동하고 싶다면 find 함수로 원하는 요소를 검색해서 이동하거나 advance 함수를 사용할 수 있는데 이 함수들도 어차피 ++을 여러 번 반복하므로 소요되는 시간은 마찬가지이다.

최초 ==> a b c d e f g h i j

Z 삽입 ==> a b c d e Z f g h i j

h삭제 ==> a b c d e Z f g i j

동작은 물론 잘하는데 이 짧은 예제에서는 느끼기 힘들지만 삽입, 삭제 속도가 엄청나게 빠르다. 요소가 아무리 많아도, 어떤 위치의 값을 삭제하나 항상 일정한 시간내에서 완료할 수 있다. 특정값을 가지는 요소를 모두 삭제하고 싶을 때는 다음 멤버 함수를 사용한다.

void remove(const Type& val);

void remove_if(UniPred F)

remove는 삭제할 값을 바로 지정하고 remove_if는 조건자에 맞는 요소만 삭제한다. 값을 검색한 후 삭제하므로 find와 erase를 순서대로 수행한다고 생각하면 된다. 다음 예제는 문자 리스트에서 'l'을 찾아 모두 삭제한다.

예 제 : listremove

#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 *str="double linked list class";

list<char> li(&str[0],&str[strlen(str)]);

dump("최초",li);

li.remove('l');

dump("l삭제",li);

}

문자들 중 l만 모조리 삭제된다.

최초 ==> d o u b l e l i n k e d l i s t c l a s s

l삭제 ==> d o u b e i n k e d i s t c a s s

조건자 버전을 사용하면 일정한 조건을 만족하는 요소만 골라 삭제할 수도 있다. 예를 들어 모음만 삭제한다거나 공백만 제거하는 것도 가능하다. 같은 이름의 전역 remove 알고리즘도 있는데 리스트의 remove 멤버 함수와는 동작하는 방식이 조금 다르다. 이 차이점에 대해서는 다음 장에서 알아보도록 하자.