Vector & List & dequeue

std::vector

1. 동적 배열 ( 배열의 크기 고려 안해도 됨)
2. 내부적으로 동적 메모리를 자동으로 관리
3. 배열과 유사하게 요소들을 순차적으로 저장

vector<int> v;
vector<int> v(5); * 기본값으로(0) 초기화된 5개의 원소
vector<int> v(5,2); * 2로 초기화된 5개의 원소

vector 멤버함수

iterator(반복자)

vector<int>::iterator it;

• v.begin() : 첫번째 요소의 반복자 위치
• v.end() : 마지막 요소 다음의 반복자 위치(NULL)

추가 및 삭제

• v.push_back(element) : 마지막 원소 뒤에 원소 element를 삽입
• v.pop_back() : 벡터 제일 뒤의 원소를 삭제

조회

• v[idx] : idx번째 원소를 참조
• v.at(idx) : idx번째 원소를 참조 & 범위를 점검
• front() : 첫번째 원소를 반환
• back() : 마지막 원소를 반환
  크기
• v.size() : 원소의 개수를 리턴
• v.capacity() : 할당된 공간의 크기를 리턴 & 공간 할당의 기준은 size에 따라 훨씬 커짐
  (기존 메모리의 *2의 크기로 capacity가 증가 - 2, 4 ,8 ,16 ...)

std::list

1. 연결리스트를 STL로 구현
2. 연결리스트와 비슷하게 중간 요소에 데이터 삽입 및 삭제가 용이
3. 임의의 접근에는 시간복잡도가 불리 ( 인덱스로 접근이 불가 )

원소 추가/ 삭제 시에 O(1)으로 매우 빠르게 수행됨
반복자는 오직 한 칸씩 움직일 수 없음(반복자 연산이 제한됨)
iterator(반복자)

list<int>::iterator it;

• li.begin() : 첫번째 요소의 반복자 위치
• li.end() : 마지막 요소 다음의 반복자 위치(NULL)

추가 및 삭제

• li.push_front(element) : list 맨 앞에 원소 element를 삽입
• li.pop_front() : 벡터 제일 앞의 원소를 삭제
• li.push_back(element) : 마지막 원소 뒤에 원소 element를 삽입
• li.pop_back() : 벡터 제일 뒤의 원소를 삭제
• insert(iterator, element) : iterator 가 가리키는 부분 "앞"에 원소를 추가
• erase(iterator) : iterator가 가리키는 부분에 원소를 삭제

조회

• front() : 첫번째 원소를 반환
• back() : 마지막 원소를 반환

	list<int> L = {1,2};
    list<int>::iterator t = L.begin();
    L.push_front(10); // 10 1 2
    cout << *t << '\n';
    L.push_back(5); // 10 1 2 5
    L.insert(t, 6); // 10 6 1 2 5
    t++;
    t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                    // 10 6 1 2 5, t가 가리키는 값은 5

std:deque

1. 2개의 큐를 가지고 있는 자료구조 ( 배열 기반의 구조 )
2. 스택과 큐의 역할을 수행 ( FIFO와 LIFO 방식 둘다 가능 )
3. list 에서 deque의 역할을 수행 할 수 있음

deque dq;
deque dq(10); * 기본값으로(0) 초기화된 10개의 원소를 가진 dq를 생성
deque dq(10, 4); * 4의 값으로 초기화된 10개의 원소를 가진 dq를 생성

deque 멤버 함수

• deque에는 capacity 멤버 함수가 없음

iterator(반복자)

deque<int>::iterator it;

• dq.begin() : 첫번째 요소의 반복자 위치
• dq.end() : 마지막 요소 다음의 반복자 위치(NULL)

추가 및 삭제

• dq[idx] : idx번째 원소를 참조
• dq.at(idx) : idx번째 원소를 참조 & 범위를 점검
• front() : 첫번째 원소를 반환
• back() : 마지막 원소를 반환