01. [C++] STL (Standard Template Library) - Vector

 

STL (Standard Template Library)

 

프로그래밍에 필요한 자료구조와 알고리즘을

템플릿화하여 제공하는 C++ 표준 라이브러리이다.

(컨테이너, 반복자, 알고리즘, 함수객체 4가지를 제공한다.)

 

 

[ 컨테이너 분류 ]

1. 원소 배치 방식에 따라

표준 시퀀스 컨테이너 (선형적인 구조) : vector, list, deque

표준 연관 컨테이너 (비선형적인 구조) : map, multimap, set, multiset

 

2. 메모리 저장 방식

배열 기반 (연속된 메모리 공간) : vector, deque

노드 기반 (비 연속된 메모리 공간) : list, map , multimap, set, multiset

 

3. 컨테이너 어댑터

기존 컨테이너의 기능을 제한하거나 축소시킨 컨테이너이다.

queue, priority queue, stack

 

 

 

---

 

 

 

Vector

 

표준 시퀀스 컨테이너.

동적 배열 기반.

연속된 메모리를 갖는다.

인덱스 접근이 가능하다. (탐색에 유리.)

배열이라는 한정된 공간이기 때문에 포화상태가 온다.

포화상태일 때 재할당 및 복사가 일어난다. (빈번한 삽입과 삭제에 불리.)

 

 

[ Vector의 선언 ]

 

vector 헤더를 포함시킨 후,

vector<자료형> '변수 이름'을 통해 선언.

자료형 위치에는 구조체나 클래스도 올 수 있다.

 

 

 

[ vector의 원소 삽입 및 제거 ]

push_back : 뒤에서 부터 원소를 삽입한다.

(vector는 push_front 함수는 제공하지 않는다.)

 

pop_back : 가장 뒤에 있는 원소를 현재 vector에서 제거한다.

(vector는 pop_front 함수는 제공하지 않는다.)

 

size : vector가 저장하고 있는 현재 원소의 개수.

 

 

 

 

 

 

 

[ vector의 메모리 예약 ]

 

 

capacity : 현재 vector가 저장할 수 있는 최대 원소의 개수. 즉, vector가 할당한 배열의 길이.

최초 vector의 capacity(용량)은 0인 상태이다.

capacity에 대한 초기화 없이 원소를 삽입할 경우 빈번한 재할당과 복사가 일어나게 된다.

 

 

 

 

빈번한 포화 상태를 방지하기 위해서는 capacity 초기화가 필요하다.

reserve : vector의 메모리 공간을 미리 예약해주는 함수.

reserve 함수를 이용하여 재할당과 복사를 방지할 수 있다.

 

(이미 예약한 공간은 줄일 수 없다.

기존의 크기보다 큰 범위로 새로 예약을 하면 재할당과 복사가 일어난다.)

 

 

 

[ vector의 멤버 함수들 ]

empty : 컨테이너가 비었는지 조사하는 멤버 함수. (비었으면 true 반환)

front : 맨 첫번째 원소를 읽어오는 함수.

back : 맨 마지막 원소를 읽어오는 함수.

 

clear : 컨테이너에 저장된 모든 원소를 제거.

shrink_to_fit : 현재의 size 수만큼 capacity의 수를 조정하는 함수.

 

swap : 두 컨테이너가 가진 모든 정보를 교환하는 함수.

 

 

 

[ vector의 반복자 ]

반복자(iterator)

컨테이너에 저장한 원소의 위치 정보를 갖는 객체이다. (포인터를 흉내 낸 객체.)

각 컨테이너마다 원소 저장방식 및 접근 방식이 다르다. (각 컨테이너마다 반복자 자료형을 갖고 있음.)

반복자를 이용하여 접근하는 방법을 획일화해놓았다.

(임의 접근 반복자, 양방향 방복자, 순방향 반복자, 입력 반복자, 출력 반복자)

 

 

vector의 반복자 : 임의접근 반복자.

+, -, +=, -=, [] 등의 임의 접근에 관한 연산자가 오버 로딩되어있다.

begin         가장 첫 원소의 위치정보(반복자)를 반환.

end         마지막 원소 다음 위치정보(반복자)를 반환.

 

 

[ 반복자를 이용한 원소 순회 ]

간접 참조 연산자가 오버로딩 되어있다.

 

 

 

[ 임의 접근 반복자 ]

인덱스를 통한 임의 접근이 가능하다.

 

 

 

[ 반복자를 이용한 중간 삽입 ]

 

반복자를 이용해서 중간 삽입을 한 이후에는

현재 반복자의 위치정보는 모두 무효화되므로 새로 설정해줘야 한다.

 

 

 

[ 반복자를 이용한 중간 제거 ]