배열

정의

메모리 상에서 원소를 연속하게 배치한 자료구조

성질

1. O(1)에 k번째 원소의 위치를 확인/변경 가능하다.
2. 추가적으로 소모되는 메모리의 양이 거의 없다. = overhead 발생 X
3. 메모리 상에 데이터들이 붙어 있는 구조이기 때문에 Cache hit rate이 높다.
4. 메모리 상에 연속한 구간을 잡아야 하기 때문에 할당에 다소 제약이 있다.

기능

임의의 위치에 있는 원소를 확인/변경 = O(1)

• 원소를 맨 끝에 추가한다.
• 맨 끝에 위치한 원소 제거한다.

임의의 위치에 원소를 추가 / 임의의 위치의 원소를 제거 = O(N)

• 임의의 위치에 원소를 추가하면 추가된 원소 뒤에 있는 원소들이 한 칸씩 밀린다.
• 임의의 위치의 원소를 제거하면 제거된 원소 뒤에 있는 원소들을 한 칸씩 당겨야 한다.

구현

STL fill

• 배열이나 벡터의 요소를 채울 때 사용한다.
• 헤더 파일 : <algorithm>
• fill(채우기 시작할 위치(인덱스), 채우기 멈출 위치(인덱스), 채울 값)

코드를 입력하세요

STL vector

2. iterator : 배열의 요소를 가리키는 포인터
3. = 사용 시 deep copy 발생