9-2. STL - Vector (2)

0. Vector(동적 배열)

동적으로 커지는 배열이다.

하나의 메모리 영역이 꽉찬 상태에서 데이터가 추가되면, 데이터들을 더 확장된 메모리로 복사/이동한다.

동적 배열에서는 각 원소가 하나의 메모리 블록에 연속하게 저장되는 특징을 가짐(줄줄이 소세지마냥).

 

 

1. 중간 삽입 및 삭제

(1) 중간 삽입

배열의 중간에 값을 넣기 위해서는 중간에서 오른쪽에 있는 원소들을 한 칸 씩 오른쪽으로 이동시켜야 한다.

-> 복사 / 붙여넣기가 반복되므로 비효율적으로 작동

 

(2) 중간 삭제

원소가 메모리 블록에서 연속으로 저장되기 때문에 중간의 원소를 제거하면 어떤 값을 찾는게 찾기 어렵게 됨

(비연속적이기 때문에)

따라서 데이터를 지우고 삭제 이후의 오른쪽에 있는 원소들을 한 칸 씩 왼쪽으로 이동시켜야 한다.

-> 복사 / 붙여넣기가 반복되므로 비효율적으로 작동

 

2. 처음과 끝 삽입 및 삭제

(1) 처음 삽입 / 삭제

처음에 원소를 삽입하면 처음 이후의 원소들을 오른쪽으로 한 칸 씩 이동시킴.

-> 복사 / 붙여넣기가 반복되므로 비효율적으로 작동

 

(2) 끝 삽입 / 삭제

원소가 끝에 삽입되거나 삭제되더라도 이전의 연속성에 영향을 주지 않음.

-> 해당 원소만 제거하거나 삽입하면 되기 때문에 효율적으로 작동함.

=> push_back이나 pop_back은 존재하지만 push_front나 pop_front는 존재하지 않는 이유임.

 

3. 임의 접근(Random Access)

배열의 어떤 원소에 접근하고자 하는 것을 임의 접근이라고 한다.

int main()
{
	vector<int> v;
	for (vector<int>::size_type i = 0, i < v.size(), i++) // 동적 배열 v의 각 원소에 i값 대입
	{
		v[i] = i;
	}
	v[3] = 13; // v의 3원소에 13을 대입
}

(1) insert 문법

v.insert("원소의 위치", "대치하고 싶은 값")

ex) 세번째 원소의 값을 5로 바꾸는 방법

v.insert(v.begin() + 2, 5);

 

(2) erase 문법

v.erase("위치", "영역"); // 영역 ; 어디까지 지울지, 생략 가능

ex) 세번째 원소에서 네번째 원소까지 지우기

v.erase(v.begin() + 2, v.begin() + 4); // 마지막 원소는 지우지 않음(2 이상 4 미만)

 

(3) 반복자를 활용하기

vector<int>::iterator insertIt = v.insert(v.begin() + 2, 5);
vector<int>::iterator eraseIt =  v.erase(v.begin() + 2);
vector<int>::iterator eraseIt2 = v.erase(v.begin() + 2, v.begin() + 4);

삽입이 일어나면 메모리를 한 칸씩 밀게 되며, 반복자는 삽입한 원소의 메모리 주소를 가리킨다.

삭제가 일어나면 메모리를 한 칸씩 당겨오게 되며, 반복자는 삭제된 원소의 메모리 주소를 가리킨다.

 

 

4. 특정 데이터를 찾아서 일괄 삭제하기

for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
    int data = *it;
    if (data == 3)
    {
    	v.erase(it);
    }
}

위 처럼 코드를 작성할 수 있겠다고 생각할 수 있지만, 실제로는 오류가 발생하게 된다.

반복자의 Myproxy 값이 null로 변하기 때문에 유효하지 않은 반복자가 된다.

for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
    int data = *it;
    if (data == 3)
    {
    	it = v.erase(it);
    }
}

위와 같이 작성하면 3인 값을 정상적으로 삭제하면서 한 칸씩을 당겨오게 된다.

하지만 당겨오는 과정 후에 it가 1만큼 증가하면서 지금 가리키고 있던 원소(3이 지워졌으므로 4를 가리키고 있다)를 검사하지 않고 넘어가게 된다.

for (vector<int>::iterator it = v.begin(); it != v.end();)
{
    int data = *it;
    if (data == 3)
    {
    	it = v.erase(it);
    }
    else
    {
    	++it;
    }
}

따라서 it의 값을 지우지 않은 경우에 1씩 증가시킨다.