이현수

이현수

꾸준히 공부하는 컴퓨터공학과 학생입니다.

[자료구조/C++ STL] 배열(Array), STL vector

2 분 소요

배열

배열 : 메모리 상에 원소를 연속해 배치한 자료구조

배열의 성질

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

배열 시간복잡도

  • 임의의 위치에 있는 원소를 확인/변경 : O(1)
  • 원소를 끝에 추가 : O(1)
  • 마지막 원소 제거 : O(1)
  • 임의의 위치에 원소를 추가 : O(N)
  • 임의의 위치에 있는 원소를 제거 : O(N)
int a[21];
int b[21][21];

// 1. memset : cstring 헤더에 있는 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 : algorithm 헤더의 fill 함수를 이용
fill(a, a+21, 0);
for(int i=0; i<21; i++)
    fill(b[i], b[i]+21, 0)

배열을 채우는 방법은 위 코드와 같이 3가지가 있다.



STL vector

#include<iostream>
#include<vector>
using namespace std;

int main(){
    vector<int> v1(3,5); // [5,5,5]
    cout<< v1.size(); // 3
    v1.push_back(7); // [5,5,5,7]

    vector<int> v2(2);  // [0,0]
    v2.insert(v2.begin()+1, 3); // [0,3,0]

    vector<int> v3 = {1,2,3,4};  // [1,2,3,4]
    v3.erase(v3.begin()+2); // [1,2,4]

    vector<int> v4; // []
    v4 = v3;  // [1,2,4]
    cout<< v4[0]; // 1
    v4.pop_back(); // [1,2]
    v4.clear(); // []
}

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

insert, erase는 배열에서 시간복잡도가 O(N)이다. push_back, pop_back은 제일 끝에 원소를 추가하거나 빼는 것이니 O(1)이다.

또 vector에서 =를 사용하면 deep copy가 발생한다. v4는 {1, 2, 4}가 되었고 이후 v4를 바꿔도 v3에는 영향을 주지 않는다.

vector<int> v1 = {1,2,3,4,5,6};

// 1. range-based for loop (Since C++11)
for(int e : v1)
    cout<< e << ' ';

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

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

vector에 있는 모든 원소를 순회하려고 할 때 2가지 방법이 있다.

첫번째는 range-based for loop를 사용하는 것이다. 지금은 값을 바꾸지 않고 그냥 출력만 해서 별 상관이 없지만, 만약 int e : v1이라고 하면 복사된 값이 e에 들어가고 int& e : v1이라고 하면 원본이 e에 들어가 int e : v1라고 쓴 for문 내에서 e를 바꿔도 v1에는 영향이 가지 않지만, int& e : v1이라고 쓴 for문 내에서는 e를 바꾸면 원본인 v1에서 실제 해당 원소의 값이 바뀌게 된다. 이 기능은 vector 뿐만 아니라 나중에 배울 list, map, set 등에서도 모두 사용된다.

두번째 방법은 for문을 이용하는 것이다.

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가 계속 커지다가 어느 순간 런타임에러가 발생하게 된다.

참고