[STL] vector #3

vector = 동적 배열 = 동적으로 커지는 배열 = 배열

원소가 하나의 메모리 블록에 연속하게 저장된다.

 

중간 삽입/삭제 (BAD)

vector의 중간 삽입은 새로운 데이터를 중간에 하나만 딱 밀어넣는게 아니라, 기존에 있던 데이터를 모두 이동시키는 것이기 때문에 비효율적이다. 데이터 크기가 클수록 더욱 비효율적이다.

또한 vector는 연속된 메모리 블록이기 때문에, 원소를 중간 삭제했을 때 데이터를 날리고 끝나는 게 아니라 나머지 데이터도 이동해야 돼서 비효율적이다.

[0] [1] [2] [3] [4]

[0] [1] [5] [2] [3] [4]

결론은 vector의 중간 삽입/삭제는 비효율적이다.

 

처음/끝, 삽입/삭제 (처음 - BAD / 끝 - GOOD)

처음 삽입/삭제는 뒤에 있는 데이터가 이동되어야 하는데, 끝 삽입/삭제는 이동이 필요없다.

 

임의 접근 (Random Access)

v[2] = 3;

vector가 배열 형태처럼 지원하는 이유는 모든 데이터들이 옹기종기 하나로 뭉쳐있기 때문에 가능하다. 그래서 vector는 Random Access를 지원한다.

원하는 데이터를 일일이 처음부터 숫자를 세는게 아니라, 바로 n번째 데이터로 접근해서 사용할 수 있는 것이다.

 

삭제할 때, 주의사항

쭉~ 스캔을 하면서, 3이라는 데이터가 있으면 일괄 삭제하고 싶다.

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

    if (data == 3)
        v.earse(it);
}

iterator는 삭제되어서 null이 됐고, 더이상 컨테이너 소속이 아닌걸로 볼 수 있기 때문에 더이상 활용하면 안된다. 하지만 for문으로 인해 다음 ++it를 하다보니 크래쉬가 난다.

 

iterator는 erase를 하는 순간, 유효하지 않기 때문에 break;를 걸거나 아니면

it = v.earse(it); 로 iterator를 다시 갱신해서 유효한 주소로 가지게 만든다.

하지만 갱신된 데이터는 바로 그 후에 for문이 끝나 ++it가 되기때문에, 갱신한 데이터는 코드 체크를 못한 상태가 된다.

그래서 ++it를 for조건문에서 빼고 else에 넣어야한다.

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

    if (data == 3)
        it = v.earse(it);
    else
        ++it;
}