[0x03] 배열

배열

정의

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

성질

• O(1)에 k번째 원소를 확인/변경 가능
• 추가적으로 소모되는 메모리의 양 overhead가 거의 없음
• 메모리가 붙어있으므로 cache hit rate가 높음
• 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

연산

• 임의의 위치 원소 확인/변경 : O(1)
• 원소를 끝에 추가 / 마지막 원소 변경 : O(1)
• 임의의 위치에 원소 추가/제거 : O(N) → 뒤에 원소들 한 칸 뒤로 밀어야 함

초기화

전역변수로 선언할 경우 int는 0으로 초기화

지역변수는 쓰레기값 들어가기 때문에 { } 등으로 초기화해야 함

int a[21];
int b[21][21];

1. memset (비추천)

memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

1. for

for (int i=0; i<21; i++) a[i] = 0;

for (int i=0; i<21; i++)
	for (int j=0; j<21; j++)
		b[i][j] = 0;

1. fill (추천) : algorithm 헤더

fill(a, a+21, 0);
for (int i=0; i<21; i++)
	fill(b[i], b[i] + 21, 0);

Vector

1. insert → O(N)

v.insert(v.begin() + start_idx, value);

1. delete → O(N)

v.erase(v.begin() + start_idx);

1. vector에서의 =는 deep copy → 복사본 바꿔도 원본에 영향 X

range-based for loop

1. 복사본

for (int num : numbers) -> num 값 바꿔도 numbers에 영향 X

1. 원본

for (int& num : numbers) -> num 값 바꾸면 numbers에 반영

for loop : 잘못된 예시

기본적으로 vector.size()는 unsigned int임

(unsigned int) 0 - (int) 1 → overflow 발생

for (int i=0; i<=v1.size() - 1; i++)
	cout << v[i] << ' ';