📌 std::vector
: 배열 크기를 유동적으로 결정할 수 있다.
: 동적 배열(dynamic array) 작업을 더 안전하고 쉽게 해준다.
-> 실제 응용 프로그램 개발에서 유용하게 사용할 수 있는 몇몇 기능을 제공하지 않음
대부분의 실제 응용 프로그램에서 데이터는 동적이며 고정 크기가 아니다.
(데이터의 크기를 미리 알고 있기가 쉽지 않다.)
Ex) 병원 관리 시스템의 경우, 더 많은 의사를 고용할 수도 있고 응급 환자가 급격하게 증가할 수도 있다.
1. std:: array의 단점
- std::atray의 크기는 컴파일 시간에 결정되는 상수이어야 합니다.
-> 프로그램 실행 중에는 변경할 수 없습니다. - 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없습니다.
- std::array의 메모리 할당 방법을 변경할 수 없습니다. 항상 스택 메모리를 사용합니다.
2. 가변 크기 배열
: C 스타일 배열 or std::array가 가지고 있는 가장 두드러진 문제 중 하나인 '고정 크기' 문제를 해결한다.
std::vector는 초기화 과정에 데이터의 크기를 제공하지 않아도 된다.
<예제 코드>
: 벡터를 초기화하는 몇 가지 방법
//크기가 0인 벡터 선언
std::vector<int> vec;
//지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec = {1, 2, 3, 4, 5}:
//크기가 10인 벡터 선언
sta::vector<int> vec(10);
//크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언
std::vector<int> vec(10, 5);✔️ 첫 번째 초기화 코드처럼 벡터는 원소 크기를 지정하지 않고 선언할 수 있다.
✔️ 벡터 크기를 명시적으로 지정하지 않거나 초깃값을 지정하여 크기를 유추할 수 있게 코드를 작성하지 않을 경우
-> 컴파일러 구현 방법에 따른 용량(capucity)을 갖는 벡터가 생성된다.
✔️ 벡터의 크기 : 벡터에 실제로 저장된 원소 개수를 나타내는 용어
-> 용량과는 다른 의미
그러므로 첫 번째 초기화의 경우, 크기는 0이지만 용량은 0 또는 작은 양수일 수 있습니다.
3. 원소 추가
1) push_back() 함수 : 벡터의 맨 마지막에 원소를 추가한다.
-> 벡터에서 자주 사용하는 연산
-> 매우 빠르게 동작함
<예제 코드>
: 동작 의사 코드(pseudocode) -> 실제 구현은 약간 다를 수 있으나 동작 방식은 거의 같음
push_back(val):
if size < capacity //새 원소를 추가할 공간이 있는 경우
- 마지막 원소 다음에 val 저장
- 벡터 크기를 1만큼 증가
- return;
if vector is already full //할당된 메모리 공간이 가득 차 있는 경우
- 2*size 크기의 메모리를 새로 할당
- 새로 할당한 메모리로 기존 원소 전부를 복사/이동
- 데이터 포인터를 새로 할당한 메모리 주소로 지정
- 마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가✔️ 맨 뒤에 원소를 삽입할 때, 뒤쪽에 남아 있는 공간이 있다면 O(1)의 시간이 걸린다.
✔️ 공간이 충분하지 않으면 모든 원소를 복사/이동해야 하며, 이때는 O(n)의 시간이 걸린다.
✔️ 대부분의 구현에서는 용량이 부족할 때마다 벡터 용량을 두 배로 늘린다.
O(n) 시간 동작은 n개의 원소를 추가한 후에만 발생하며, 이러한 경우는 많지 않다.
push_back() 연산의 평균 시간 복잡도는 O(1)에 가깝다.
push_back()은 매우 빠르게 동작하며, 이 때문에 벡터를 많이 사용한다.
2) insert() 함수 : 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가할 수 있다.
-> 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요하다.
-> 필요한 경우 메모리를 새로 할당하는 작업도 수행된다.
✔️ 원소들을 이동하는 연산 때문에 insert() 함수는 O(n)의 시간이 걸린다.
<예제 코드>
: 원소를 삽입하는 방법
//다섯 개의 정수를 갖는 벡터 정의
std::vector<int> vec - {1, 2, 3, 4, 5};✔️ 벡터는 push_front() 함수를 지원하지 않음!
-> 맨 앞에 새로운 원소를 추가하려면 원소 십입 위치를 인자로 받는 insert() 함수 사용
📌 백준 문제 풀이
