[賢斌] vector<벡터> - 2

40-1-나.삽입과 삭제

요소의 집합을 관리하는 컨테이너에서 삽입과 삭제는 가장 기본적인 동작이다. 각 컨테이너별로 내부적인 구조가 다르기 때문에 삽입, 삭제 방식도 컨테이너별로 다를 수밖에 없다. 그래서 삽입, 삭제 함수는 일반 알고리즘으로 제공되기보다는 컨테이너의 멤버 함수로 제공된다. 다음 두 함수는 벡터의 제일 끝 부분에서 삽입, 삭제를 수행한다.

 

void push_back(const T& x);

void pop_back();

 

push_back은 벡터 끝에 새 요소 x를 추가하고 필요할 경우 메모리 관리까지 한다.  용량이 부족할 경우 재할당을 해서라도 x를 추가하므로 마음놓고 호출할 수 있다. pop_back은 반대로 벡터의 끝 요소를 삭제한다. 앞뒤의 요소를 읽을 때는 front, back 멤버 함수를 사용하는데 이 함수는 T형의 레퍼런스를 리턴하므로 양끝의 멤버를 읽거나 쓸 수 있다.

벡터는 앞쪽에서 요소를 삽입하거나 삭제하는 push_front, pop_front 함수는 제공하지 않는다. 벡터의 끝 부분에 추가하는 것은 빠르지만 중간이나 처음에 삽입, 삭제하는 것은 요소의 인접성을 유지하기 위해 뒤쪽 요소를 이동시켜야 하므로 무척 느리다. 만약 꼭 벡터의 중간에 요소를 삽입하고 싶다면 insert 함수를 사용한다. 벡터에 대해 push_front(V)를 하려면 insert(begin(),V)을 대신 호출하면 된다.

 

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);

 

세 가지 원형이 제공되는데 세 버전 모두 첫 번째 인수는 삽입 위치를 나타내는 벡터 내의 반복자이다. 나머지 인수로 삽입 대상을 지정하는데 요소 하나, 같은 값 여러 개, 다른 반복자 구간을 삽입할 수 있다. insert는 삽입하기 전에 메모리가 부족할 경우 재할당하여 늘리고 it 이후의 요소를 뒤쪽으로 이동시킨다. 요소를 삭제할 때는 erase 함수를 사용한다.

 

iterator erase(iterator it);

iterator erase(iterator first, iterator last);

 

반복자가 지정하는 요소 하나 또는 반복자 구간을 삭제할 수 있다. insert와 erase는 요소를 관리하는 기본 동작이므로 대부분의 컨테이너에 동일한 이름과 형식으로 존재한다. 간단하게 테스트 예제를 작성해 보자.

 

예 제 : vectorinsdel

#include <iostream>

#include <vector>

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="0123456789";

     vector<char> vc(&str[0],&str[10]);dump ("생성 직후 ", vc);

     vc.push_back('A');dump ("A 추가", vc);

     vc.insert(vc.begin()+3,'B');dump ("B 삽입", vc);

     vc.pop_back();dump ("끝 요소 삭제", vc);

     vc.erase(vc.begin()+5,vc.begin()+8);dump ("5~8 삭제", vc);

}

 

문자를 저장하는 벡터 vc를 0~9까지의 문자로 생성하여 알파벳 문자를 삽입, 삭제해 보았다. 실행 결과는 다음과 같다.

 

생성 직후   ==> 0 1 2 3 4 5 6 7 8 9

A 추가      ==> 0 1 2 3 4 5 6 7 8 9 A

B 삽입      ==> 0 1 2 B 3 4 5 6 7 8 9 A

끝 요소 삭제==> 0 1 2 B 3 4 5 6 7 8 9

5~8 삭제    ==> 0 1 2 B 3 7 8 9

 

끝에서 추가, 삭제할 때는 push_back, pop_back 함수를 사용하며 중간에서 삽입, 삭제할 때는 insert, erase를 사용했다. 결과를 보다시피 잘 동작한다.

한꺼번에 삽입, 삭제하기

insert, erase 함수는 개별 요소에 대해 동작하는 버전과 같은 값 여러 개, 또는 구간에 대해 동작하는 버전이 중복 정의되어 있는데 복수 개의 값을 삽입, 삭제할 때는 가급적이면 한꺼번에 삽입, 삭제하는 것이 유리하다. 같은 값 여러 개를 삽입해야 한다면 원하는 회수만큼 루프를 돌려도 되지만 이 방법보다는 삽입할 개수를 지정할 수 있는 insert 함수를 사용하는 것이 좋다.

한꺼번에 삽입하는 함수는 필요한 메모리양을 먼저 계산한 후 메모리를 왕창 옮기고 새로 만들어진 빈 칸에 값을 일괄 대입하므로 메모리 이동과 재할당이 딱 한 번만 일어난다. 루프를 직접 돌리면 매 삽입시마다 메모리를 한칸씩 이동할 뿐만 아니라 재할당도 여러 번 일어날 수 있어 성능이 떨어질 것이다. 다음 예제는 문자 벡터에 'Z' 문자를 10 개 삽입하는 두 가지 방법을 보여 준다.

 

예 제 : insdelmulti

#include <iostream>

#include <vector>

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()

{

     vector<char> vc1;

     for (int i=0;i<10;i++) {

          vc1.insert(vc1.begin(),'Z');

     }

     dump("개별 추가", vc1);

 

     vector<char>vc2;

     vc2.insert(vc2.begin(),10,'Z');

     dump("한꺼번에 추가", vc2);

}

 

vc1에 대해서는 10회 루프를 돌리면서 insert를 호출했고 vc2에 대해서는 insert 한 번의 호출로 10개의 'Z'를 한꺼번에 삽입했다. 이 예제에서는 고작 10개밖에 추가하지 않았으므로 차이를 전혀 느낄 수 없겠지만 만 개만 되어도 당장 차이가 나며 백만개 정도 되면 엄청난 차이가 벌어진다.

erase로 삭제할 때도 마찬가지인데 재할당은 발생하지 않겠지만 메모리 이동이 매 삭제시마다 일어나므로 구간을 지정하여 한꺼번에 삭제하는 것이 좋다. STL은 하고자 하는 작업의 성격에 따라 가장 효율적인 함수를 골라 쓸 수 있도록 멤버 함수들을 용도별로 중복 정의해 놓았다.

다른 컨테이너와 요소 교환하기

반복자 구간을 인수로 취하는 insert 함수를 사용하면 다른 컨테이너의 구간에 있는 요소를 벡터에 삽입할 수 있다. 다른 컨테이너들도 똑같은 원형의 insert 함수를 제공하므로 벡터의 구간을 다른 컨테이너로 복사하는 것도 물론 가능하다. 다음 예제는 리스트의 일정 구간을 벡터로 복사한다.

 

예 제 : insertfromother

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

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()

{

     list<int> li;

     for (int i=0;i<100;i++) {

          li.push_back(i);

     }

     vector<int> vi;

    

     vi.insert(vi.begin(), find(li.begin(),li.end(),8), find(li.begin(),li.end(),25));

     dump("추가 후", vi);

}

 

리스트의 8 ~ 25 미만까지의 구간이 빈 벡터로 복사된다. 여기서는 insert 함수를 테스트하기 위해 빈 벡터를 만든 후 구간을 삽입했지만 구간을 인수로 받는 생성자로도 동일한 일을 할 수 있다.

 

추가 후     ==> 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

 

벡터와 리스트는 내부 구조가 완전히 다르지만 일반화된 반복자를 통해 두 컨테이너의 요소를 액세스하므로 이런 삽입이 가능하다. 반복자가 컨테이너의 내부 구조에 상관없이 요소를 읽고 다음 위치로 이동하는 기능을 제공하므로 insert 함수는 상대편의 구조를 몰라도 * 연산자와 ++만으로 반복자 구간을 읽을 수 있는 것이다.

이런 작업이 가능하다는 것이 반복자의 존재 이유이며 또한 일반화된 STL의 강점이기도 하다. STL이 아니라면 리스트와 벡터의 자료 교환은 이보다 훨씬 더 복잡하고 번거로울 것이다.

반복자 무효화 현상

반복자는 컨테이너 내의 요소 위치를 가리키는 일종의 포인터인데 특정 요소를 가리키도록 한 번 설정하면 계속 같은 요소를 가리킨다. 그러나 컨테이너에 삽입, 삭제가 일어나면 메모리 재할당 및 이동이 발생하므로 이때는 조사해 놓은 반복자가 무효화될 수 있다. 즉, 반복자가 더 이상 정확한 요소를 가리키지 못하는 것이다.

먼저 삽입의 경우를 보자. 중간에 한 요소가 삽입되면 뒤쪽의 요소들은 삽입된 개수만큼 이동하므로 뒤쪽 요소를 가리키던 반복자들은 모두 무효화된다. insert 함수가 요소는 이동시키지만 이 컨테이너의 다른 요소를 가리키는 반복자까지 같이 이동시킬 수는 없기 때문이다.

삽입된 위치의 앞쪽은 무효화될 수도 있고 그렇지 않을 수도 있는데 재할당에 의해 메모리 번지가 바뀌면 무효화될 것이고 그렇지 않다면 영향을 받지 않을 것이다. 삽입에 의해 재할당이 자주 발생하지는 않지만 모든 경우에 유효성이 보장된다고 할 수는 없으므로 삽입하면 전 반복자가 무효화된다고 보는 것이 옳다.

삭제시는 삭제 구간의 뒤쪽은 무효화되지만 앞쪽은 영향을 받지 않는다. 삭제는 삽입과는 달리 메모리 재할당이 절대로 일어나지 않으므로 앞쪽 요소는 원래 자리를 항상 그대로 유지하기 때문이다. 다음 예제를 통해 삭제시의 반복자 무효화를 연구해 보자.

 

예 제 : invaliditerator

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     vector<int> vi;

     for (int i=0;i<80;i++) {

          vi.push_back(i);

     }

     vector<int>::iterator it;

     it=find(vi.begin(),vi.end(),55);

     cout << *it << endl;

     vi.erase(it+1);

     cout << *it << endl;

}

 

vi 벡터에 0~79까지의 정수를 넣고 it 반복자가 55를 가리키도록 했다. *it를 출력하면 반복자가 가리키고 있는 값 55가 출력될 것이다. 이 상태에서 it+1, 즉 바로 오른쪽에 있는 요소인 56을 삭제했다. 56의 뒤쪽만 무효화되므로 it 반복자는 원래의 위치를 가리키고 있을 것이다. erase 코드를 다음과 같이 수정해 보자.

 

vi.erase(it-1);

 

바로 왼쪽의 54 자리를 지웠는데 이렇게 되면 54 이후의 요소를 가리키는 반복자들이 전부 무효화된다. 실행 결과는 컴파일러마다 다른데 56이 한칸 앞쪽으로 이동되었으므로 56이 출력될 수도 있고 컴파일러의 반복자 유효성 점검 기능에 의해 assert가 발생할 수도 있다. 아무튼 자기보다 앞쪽이 삭제되면 뒤쪽의 반복자는 무효해지므로 더 이상 참조해서는 안된다. 이번에는 erase 구문 대신 다음 코드를 넣어 보자.

 

vi.insert(vi.begin(),1234);

 

벡터의 선두에 1234 요소를 삽입했으므로 모든 요소가 뒤쪽으로 한칸씩 이동하여 무효화될 것이다. 55를 가리키던 it 자리에는 54가 위치하므로 54가 출력될 수도 있지만 만약 메모리 재할당이라도 발생했다면 전혀 엉뚱한 값을 읽을 수도 있다.

삽입, 삭제 동작은 반복자를 무효화할 수 있는데 무효화 규칙은 컨테이너마다 다르다. 리스트는 노드들이 메모리의 도처에 흩어져 있으며 삽입, 삭제에 의해 다른 노드들이 이동되는 것은 아니므로 반복자 무효화 현상이 훨씬 덜하다. 삽입의 경우는 전혀 무효화되지 않으며 삭제의 경우는 삭제된 반복자만 무효화된다. 규칙이 조금 복잡해 보이기는 하지만 컨테이너의 내부를 대충이라도 상상할 수 있다면 어렵지 않게 유추할 수 있다.

STL 프로그래밍은 주로 반복자를 다루는 작업인데 조사해 놓은 반복자가 무효화되는 현상은 대단히 조심스럽게 다루어야 할 사항이다. 삽입에 의한 반복자 무효화를 최소화하려면 reserve로 메모리를 충분히 할당해 놓아 재할당이 일어나지 않도록 해야 하며 삭제시는 뒤쪽의 반복자를 다시 조사해야 한다. 그러나 조심 조심 반복자를 사용하는 것보다는 컨테이너에 조금이라도 변형을 가했다면 이전에 조사해 놓은 반복자 전체를 믿지 않는 편이 더 확실하다.