vector

• 위치 접근 : O(1)
• 위치 접근 : O(1)
• 뒤에 원소 추가 제거 : amortized O(1) - push_back, pop_back
• 임의의 위치 원소 추가 및 제거 : O(n) - insert, erase
  

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec;

    vec.push_back(10); // 맨 뒤에 10 추가
    vec.push_back(20); // 맨 뒤에 20 추가
    vec.push_back(30); // 맨 뒤에 30 추가
    vec.push_back(40); // 맨 뒤에 40 추가
    vec.pop_back();    // 맨 뒤에 제거

    cout << vec.size() << endl;     // 3 : 원소 개수
    cout << vec.capacity() << endl; // 4 : 전체 사이즈, 여분 포함 - 그때 그때 다름

    vec.insert(vec.begin(), 100); // iter 자리에 100 삽입
    vec.erase(--vec.end());       // iter 자리 삭제

    // []를 통한 접근
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << ",";
    }
    cout << endl;

    // iterator를 통한 접근 - capacity 만큼 됨...
    for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter)
    {
        cout << *iter << ",";
    }
    cout << endl;

    return 0;
}

list

• double linked list
• 임의의 위치 추가, 제거 : O(1) 이나 찾는데 O(n)
• cache hit율 떨어짐
• 정말 필요한가 고민해보고 사용

#include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> li;

    li.insert(li.end(), 1);
    li.insert(li.end(), 2);
    li.insert(li.end(), 3);
    li.insert(li.end(), 4);
    li.insert(li.end(), 5);

    li.remove(3);         // 3 원소 제거
    li.erase(li.begin()); // iter 삭제

    // iter 접근
    for (list<int>::iterator iter = li.begin(); iter != li.end(); ++iter)
    {
        cout << *iter << " - ";
    }
    cout << endl;

    return 0;
}

deque

• vector와 비슷하나 앞, 뒤 추가/삭제 작업이 O(1)
• 원소들이 메모리상에서 연속적으로 존재하지 않음...
• 꽉찬 상태에서 추가할 때, vector는 새로운 공간 할당 및 복사가 이루어짐.
• deque는 기존의 원소를 복사할 필요가 없음

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;

    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.push_front(40);
    dq.push_front(50);
    dq.push_front(60);

    dq.pop_front();
    dq.pop_back();

    for (deque<int>::iterator iter = dq.begin(); iter != dq.end(); iter++)
    {
        cout << *iter << " - ";
    }
    cout << endl;

    return 0;
}