[C++] 배열 (feat. 바킹독)

배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양(오버헤드)가 거의 없음
3. cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

시간 복잡도

1. 임의의 위치에 있는 원소를 확인/변경 : O(1)
2. 원소를 끝에 추가/제거 : O(1)
3. 임의의 위치에 원소를 추가/제거 : O(N)

 

실제로 임의의 위치에 원소를 추가/제거하는 함수를 작성해보자

void insert(int idx, int num, int arr[], int& len){
  len++;
  int tmp;
  for(int i=len; i>idx; i--){ //맨 끝에서부터 반복문
    arr[i] = arr[i-1];
  }
  arr[idx]=num;

}

void erase(int idx, int arr[], int& len){
  len--;
  for(int i=idx; i<len; i++){
    arr[i] = arr[i+1];
  }
}

 

💡 배열 Tip

전체 값을 특정 값으로 초기화 시킬때...

하지만 여기서 memset 방법은 전혀 추천하지 않고, 무난하게 for문 방법이나 algorithm헤더의 fill 함수를 이용하는것이 좋다고 한다.

 

STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 접근할 수 있다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있다.

 +) vector에서 =를 사용하면 deep copy가 발생한다.
 + ) insert와 erase가 메소드로 이미 구현이 되어있다. (v.begin()+x 와 같은 형식으로 인자를 주는것을 알 수 있는데, 이는 STL iterator에 관한 개념이다)

 

vector에 있는 모든 원소를 순회하려고 할 때, range-based for loop를 이용할 수 있다.
지금은 값을 바꾸지 않고 그냥 출력만 해서 별 상관이 없지만, 만약 int e : v1이라고 하면 복사된 값이 e에 들어가고 int& e:v1이라고 하면 원본이 e에 들어간다. 그렇기 때문에 전자의 경우 for문 내에서 e를 바꿔도 v1에는 영향이 가지 않지만, 후자의 경우는 e를 바꾸면 원본인 v1에서 실제 해당 원소의 값이 바뀌게 된다.

하지만 여기서 3번과 같은 경우는 매우 잘못된 방법이다.
기본적으로 vector의 size 메소드는 시스템에 따라 unsigned int 혹은 unsigned long long을 반환한다.

그렇기 때문에 32비트 컴퓨터 기준 3번같이 쓰면,
v1이 빈 vector일 때 v1.size() - 1이 unsigned int 0에서 int 1을 빼는 식이 되고, unsigned int와 int를 연산하면
unsigned int로 자동 형변환이 발생하기 때문에 (unsigned int)0 - (int)1은 -1이 아니라 4294967295이 되어버린다.
4294967295이라는 이상한 값은 unsigned int overflow로 인해 생기게 된 값이다.

그래서 아무것도 출력을 하지 않고 종료되는 것이 아닌, v1[0], v1[1], v1[2], ...  이렇게 i가 계속 커지다가 어느 순간 런타임에러가 발생하게 될 것이다.