5. 시퀀스 컨테이너

시퀀스 컨테이너

빠른 설명

시퀀스 컨테이너는 원소가 순서대로 저장되는 자료구조다. C++에서는 vector, deque, list, Python에서는 list, tuple, deque가 대표적이다.

언제 쓰는가

• 순서가 중요한 데이터를 저장할 때
• 인덱스로 빠르게 접근해야 할 때
• 앞뒤 삽입/삭제가 필요한지에 따라 컨테이너를 고를 때

시간복잡도 감각

• vector/Python list의 뒤 삽입: 평균 $O(1)$
• 인덱스 접근: $O(1)$
• 중간 삽입/삭제: 보통 $O(N)$
• deque의 앞뒤 삽입/삭제: $O(1)$

참고자료

• cppreference - Containers library
• cppreference - std::vector
• Python Tutorial - Data Structures
• Python - Sequence Types

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
 
    cout << v[1] << '\n';
 
    deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);
    cout << dq.front() << ' ' << dq.back() << '\n';
}

Python 코드

from collections import deque
 
a = []
a.append(10)
a.append(20)
a.append(30)
print(a[1])
 
dq = deque()
dq.appendleft(1)
dq.append(2)
print(dq[0], dq[-1])