배열

배열

1. k 번째 원소에 접근하는 것은 O(1)이 걸린다.
2. 메모리상에 연속한 구간을 잡아야 해서, 할당에 제약이 있다.

insert 할 때

오른쪽에서부터 한 칸 씩 오른쪽으로 옮기면 됩니다.

예를 들어

2 4 6 13 -2 1 이 있고, 13과 -2 사이에 숫자 15를 넣고 싶다면

2 4 6 13 -2 "" 1
2 4 6 13 "" -2 1
먼저 위 처럼 옮기고, 들어갈 위치에 15를 넣으면 됩니다.

erase 할 때

erase는 더 쉽습니다. 지워야 할 수의 오른 쪽 숫자들을 왼쪽으로 한 칸 씩 옮기면 됩니다.

예를 들어

2 4 6 13 -2 1 이 있고, 13을 지우고 싶다면

2 4 6 -2 "" 1
2 4 6 -2 1
이렇게 옮기면 됩니다. (추가적인 메모리도 필요하지 않습니다.)

insert, erase는 시간 복잡도가 O(N) 입니다.

전체를 특정 값으로 초기화 시키고 싶다면

for 문을 돌아도 되고,

algorithm 헤더의 fill 함수를 익히면 좋습니다.

fill (v.begin(), v.begin()+4, 1);
fill (v.begin()+4, v.end(), 2);

STL vector

• O(1)에 각 원소에 접근이 가능하다.
• 배열과 달리, 크기를 자유자재로 늘이거나 줄일 수 있다.

vector에는 insert, erase가 미리 구현이 되어 있고, O(N) 입니다.
다만, push_back, pop_back은 O(1)입니다.

vector의 = 는 deep copy 입니다.

• 즉, vector를 다른 vector로 복사 했다면 주소가 다르다는 것입니다.

vector는 range-based for loop를 이용할 수 있습니다.