C++ Vector를 이용한 배열의 동적 메모리 할당

 

Cplusplus 인용 -

 

VectorVectors are sequence containers representing arrays that can change in size.

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actualcapacitygreater than the storage strictly needed to contain its elements (i.e., itssize). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals ofsizeso that the insertion of individual elements at the end of the vector can be provided withamortized constant timecomplexity (seepush_back).

Therefore, compared to arrays, vectors consume more memory in exchange for the ability to manage storage and grow dynamically in an efficient way.

Compared to the other dynamic sequence containers (deques,listsandforward_lists), vectors are very efficient accessing its elements (just like arrays) and relatively efficient adding or removing elements from itsend. For operations that involve inserting or removing elements at positions other than the end, they perform worse than the others, and have less consistent iterators and references thanlistsandforward_lists.

- 사이즈 변경이 가능한 연속 컨테이너

- 배열과 달리 동적으로 길이 변경이 가능하다

 

알고리즘 문제를 풀면서 주어진 숫자만큼의 크기를 가지는 배열을 생성하고자 할 때

 

int N;

scanf("%d",&N);

int a[N];

int N;
scanf("%d",&N);
int a[N];

 

이런식의 할당이 오류를 불러온다는 것을 처음 알았다

이런 경우에는 vector를 이용해 동적 할당을 하는 것이 올바르다고 하다

 

인프런 강의 22번 문제를 풀다가 깨달음

 

#include <stdio.h>
#include<vector>

int main(){
    int n,k,i,sum=0,max;
    scanf("%d %d",&n, &k);
    std::vector<int> a(n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<k;i++){
        sum+=a[i];
    }
    max=sum;
    for(i=k;i<n;i++){
        sum=sum+(a[i]-a[i-k]);
        if(sum>max) max=sum;
    }
    printf("%d\n",max);
    return 0;

}

물론 std:: 붙이기 귀찮으니까

using namespace std; 하면 됨

 

 

Vector는 가변 길이 배열이다

 

가변 길이 배열인만큼 정해진 길이 내에서는 연산이 빠르다

 

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec;
  vec.push_back(10);  // 맨 뒤에 10 추가
  vec.push_back(20);  // 맨 뒤에 20 추가
  vec.push_back(30);  // 맨 뒤에 30 추가
  vec.push_back(40);  // 맨 뒤에 40 추가

  for (std::vector<int>::size_type i = 0; i < vec.size(); i++) {
    std::cout << "vec 의 " << i + 1 << " 번째 원소 :: " << vec[i] << std::endl;
  }
}

특히 배열의 첫번째나 끝의 원소에 접근할 때에는 속도가 빠르다 (정해진 범위 내에서)

push_back

pop_back 

연산을 기억하자

 

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec;
  vec.push_back(10);
  vec.push_back(20);
  vec.push_back(30);
  vec.push_back(40);

  // 전체 벡터를 출력하기
  for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
    std::cout << *itr << std::endl;
  }

  // int arr[4] = {10, 20, 30, 40}
  // *(arr + 2) == arr[2] == 30;
  // *(itr + 2) == vec[2] == 30;

  std::vector<int>::iterator itr = vec.begin() + 2;
  std::cout << "3 번째 원소 :: " << *itr << std::endl;
}

또한 iterator의 경우에도 begin() 과 end()를 이용해서 원소에 접근 가능하다

단 가운데에 끼어있는 원소의 경우에는 접근이 약간 힘들어짐.

 

#include <iostream>
#include <vector>


template <typename T>
void print_vector(std::vector<T>& vec) {
  // 전체 벡터를 출력하기
  for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
       ++itr) {
    std::cout << *itr << std::endl;
  }
}
int main() {
  std::vector<int> vec;
  vec.push_back(10);
  vec.push_back(20);
  vec.push_back(30);
  vec.push_back(40);

  std::cout << "처음 벡터 상태" << std::endl;
  print_vector(vec);
  std::cout << "----------------------------" << std::endl;

  // vec[2] 앞에 15 추가
  vec.insert(vec.begin() + 2, 15);
  print_vector(vec);

  std::cout << "----------------------------" << std::endl;
  // vec[3] 제거
  vec.erase(vec.begin() + 3);
  print_vector(vec);
}

 

insert와 erase로 원소의 삽입/삭제가 가능하다 (iterator 사용으로 가운데 원소에 접근)

 

범위 기반 for 문 가능

 

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec;
  vec.push_back(1);
  vec.push_back(2);
  vec.push_back(3);

  // range-based for 문
  for (int elem : vec) {
    std::cout << "원소 : " << elem << std::endl;
  }

  return 0;
}

 

elem = vec[i];

와 같이 복사한 효과로서 벡터 범위 내에서 for loop를 실행 가능.