Method “Insert” for list vs vector

Insert() 메서드 사용시 vector와 list 의 차이

Background

Vector와 list는 c++에 사용되는 container로, 둘다 C의 array처럼 생겼지만, dynamically allocated array에 기반한 vector 자료형과 달리 list는 doubly-linked lists로 구현되어 있다.

vector는 array와 같이 메모리 access에 빠른 장점이 있고, 끝부분에서 element를 줄이거나 추가할 때 효율적이다. vector의 경우 element 추가/제거 때문에 size와 달리 capacity라는 개념을 사용한다. capacity는 size와 같거나 큰 값으로, size보다 많은 양의 element를 추가하는 경우 주소의 relocation을 방지하기 위해 사용한다. (capacity라는 속성을 추가로 가지고 있기 때문에 vector는 array보다 사이즈가 크다. 또한 capacity를 넘길 정도로 많은 양의 element가 추가된다면 메모리 relocation이 발생한다.) 한편 array 기반이기 때문에 element의 추가가 vector의 끝이 아닌 다른 곳(처음, 중간, etc.)에서 일어난다면 array와 같이 속도가 느린 편이다.

반면 list는 element가 추가된다고 메모리 relocation이 발생하지 않는다. 따라서 element를 추가, 삭제 하는데 있어서 array나 vector보다 빠른 속도를 보여준다. 대신에 데이터에 대한 직접적인 접근이 느리며, 예를 들어서 6번 째 element를 보려고 한다면 mylist[5]로 접근이 불가능하고 ++mylist.begin()를 5번 수행하거나 std::advance(mylist.begin(), 5)와 같은 방식으로 접근해야 한다. (mylist.begin() + 5가 안되는 이유는 list의 iterator는 BidirectionalIterator이기 때문이다. RandomAccessIterator인 vector는 myvec.begin()+5와 같은 연산이 가능한다. 따라서 array나 vector에 비해 메모리 접근에 있어 속도가 느린 편이다.

vector와 list의 Insert()

list든 vector든 insert를 사용해서 Element를 추가하는 경우 모두 size가 바뀌게 된다. 문제는 vector의 경우 capacity가 변동이 되는 순간 memory relocation일 일어난다는 것이다. 아래 코드를 실행하면 그 차이를 알 수 있게 된다.

#include <iostream>
#include <list>
#include <vector>
using namespace std;
void print(list<int> myl)
{
    for (auto e:myl)
    {
        cout << e << " ";
    }
    printf("\n");
}
void print(vector<int> myv)
{
    for (auto e:myv)
    {
        cout << e << " ";
    }
    printf("\n");
}

int main()
{
    list<int> mylist = {1,2,3};
    vector<int> myvec = {1,2,3};
    list<int>::iterator lit = mylist.begin();
    vector<int>::iterator vit = myvec.begin();
    mylist.insert(lit, 2, 100);
    myvec.insert(vit, 2, 100);
    print(mylist);
    print(myvec);
    cout << "The list iterater 'lit' points: " << *lit << "\n";
    cout << "The vector iterater 'vit' points: " << *vit << "\n";
    return 0;
}

실행결과

100 100 1 2 3 
100 100 1 2 3 
The list iterater 'lit' points: 1
The vector iterater 'vit' points: 459884720

element의 insert가 수행되어도 list의 iterator ‘lit’는 계속 1을 가리키고 있는 반면 vector의 iterator ‘vit’는 insert()로 인해 capacity가 변동이 되어 memory relocation이 발생했다. 따라서 가리키고 있는 주소에는 쓰레기 값이 들어있는 것을 볼 수가 있다. vector에서 이러한 경우를 방지하려면 main()문이 아래와 같이 수정되어야 한다.

#include <iostream>
int main()
{
    list<int> mylist = {1,2,3};
    vector<int> myvec = {1,2,3};
    list<int>::iterator lit = mylist.begin();
    vector<int>::iterator vit = myvec.begin();
    mylist.insert(lit, 2, 100);
    vit = myvec.insert(vit, 2, 100) + 2;
    print(mylist);
    print(myvec);
    cout << "The list iterater 'lit' points: " << *lit << "\n";
    cout << "The vector iterater 'vit' points: " << *vit << "\n";
    return 0;
}

결과

100 100 1 2 3 
100 100 1 2 3
The list iterater 'lit' points: 1
The vector iterater 'vit' points: 1

Conclusion

따라서 본인이 코드를 작성할 때 iterator에 의한 연산을 자주 해야 될 것 같다고 생각되면 list를 쓰는게 vector를 쓸 때보다 실수를 줄일 수 있을 것이다. 나는 참고로 초기에 정해진 크기가 주어지지 않는 array를 동적으로 할당할 때만 vector를 사용하고 있다.