Array

Array

배열의 성질

• O(1)에 k번째 원소를 확인/변경 가능
• 추가적으로 소모되는 메모리의 양이 거의 없음
• cache hit rate가 높음(메모리상 데이터들이 붙어있음)
• 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
• 임의의 위치에 원소를 추가: O(N) 뒤로 다 밀어야함
• 임의의 위치에 원소를 제거: O(N) 지우고 빈자리 채우기
• 원소를 끝에 추가 및 제거: O(1)

  사용 Tip

• 전체를 특정 값으로 초기화

  #include<iostream>
  #include<cstring>
  using namespace std;
  int a[21];
  int b[21][21];
  int main(void){
    // #1 memset 실수할 여지가 많음(0이나 -1이 아닌경우,2차원 이상의 배열을 함수의 인자로 넘기고 그곳에서 memset을 사용하는 경우) 비추천
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    // #2 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;
        }
    }
    // #3 fill 가장 추천
    fill(a,a+21,0);
    for(int i=0;i<21;i++){
        fill(b[i],b[i]+21,0);
    }
    return 0;
  }
  

  vector

  vector의 성질

• 원소가 메모리에 연속하게 저장
• 각 원소에 접근: O(1)
• 배열과 달리 크기를 자유롭게 늘리고 줄일 수 있음
• insert,erase: O(N)
• push_back,pop_back: O(1)
• push_front,pop_front: O(N)

  사용 Tip

  #include<iostream>
  #include<vector>
  using namespace std;
  vector<int> v1={1,2,3,4,5,6};
  int main(void){
    // 1. range-based for loop
    // e에 v1 원소들이 하나씩 들어감(복사된 값)
    // int& e:v1 이면 원본이 들어감(e를 바꾸면 원본이 바뀜)
    for(int e:v1){
        cout<<e<<' ';
    }
    // 2. not bad
    for(int i=0;i<v1.size();i++){
        cout<<v1[i]<<' ';
    }
    // 3. WRONG
    //vector의 size method는 unsigned int를 반환
    // v1.size()가 0이면 unsigned int(0) - int(1)이 되고 unsigned int로 자동 형변환이 되기 때문에
    // unsigned int(0)-int(1) = 4294967295
    // unsigned int overflow
    for(int i=0;i<=v1.size()-1;i++){
        cout<<v1[i]<<' ';
    }
    return 0;
  }