C++ 배우기 18(STL, vector)

STL(Standard Template Library)

표준 템플릿 라이브러리라고 부르며, C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다고 한다.

프로그램에 필요한 자료구조와 알고리즘을 제공해준다. 우리가 자주 쓰던 std namespace의 안에 있다.

이 STL안에는 알고리즘, 컨테이너, 함수자, 반복자라는 4가지의 구성요소가 있다.

 

컨테이너(container)

특정 타입의 원소들을 담아 다루기 위한 객체, 자료를 저장하는 클래스 템플릿의 집합이다.

구현하려는 동작에서 가장 오버헤드가 걸릴 것을 고려하여 컨테이너를 선택하면 성능 향상에 도움이 된다.

순차 컨테이너와 연관 컨테이너로 나뉘게 되는데,

순차 컨테이너에는 array, vector, list, deque가 있고, 연관 컨테이너에는 set, multiset, map, multimap이 있다.

 

반복자(iterator)

포인터처럼 동작하는 객체로,  컨테이너 안의 내부 데이터를 순회할 수 있는 객체들을 말하며,

컨테이너의 원소를 가리키고 접근하여 다음 원소를 가리키는 순회 기능을 한다.

input iterators, output iterators, forward iterators, bidirectional iterators, random iterators와 같은

5가지의 종류를 구현한다.

 

알고리즘(algorithm)

검색, 정렬, 수정 등을 역할을 수행하며, 반복자로 지정되는 작업을 정의해놓은 함수 템플릿이다.

 

함수자(functor)

STL은 함수 호출 연산자(operator())를 오버로드하는 클래스들을 포함하는데, 이 클래스의 인스턴스들이

함수 객체 또는 함수자로 부른다.

함수처럼 동작하는 객체로 함수 호출 연산자(operator())를 오버로딩한 객체이다.

---

vector(벡터)

위에서 봤던 STL의 컨테이너 중 하나이다. vector를 생성하면 동적 할당이 되고 heap 메모리 영역에 생성이 된다.

C++에서 일반적으로 사용하던 배열은 미리 할당한 메모리 공간에서만 활용이 가능하고, 크기가 고정되어 있었다.

또한 순서대로 나열하는 메모리가 연속적인 특징이 있어서 모든 배열의 요소가 같은 타입을 가져야만 했다.

그에 반해 vector는 배열과 비슷하긴 하지만 좀 더 확장된 기능을 가지고 있다고 볼 수 있다.

vector는 자동으로 생성과 해제를 해주면서 그때그때 크기의  변경이 가능하다.

 

물론 일반적인 배열이 속도가 좀 더 빠르지만, vector는 메모리 관리와 예외처리 등 세세한 부분에서 좀 더 효율적인

관리가 가능하다는 점이 있다.

 

vector 생성

vector 생성 방법에도 여러 가지가 있다. 밑의 방법을 사용하기 전에 먼저 #include<vector>를 불러오는 것을 기억하자.

방법	설명
vector<자료형> 변수명;	해당하는 자료형의 벡터 생성
vector<자료형> 변수명(크기);	지정 크기만큼의 벡터 생성(초기값이 0으로 들어있음)
vector<자료형> 변수명 = {변수1, 변수2, 변수3...};	대입한 변수값으로 초기화된 백터 생성
vector<자료형> 변수명[] = {, };	2차원 백터 배열 생성 및 초기화( 행 가변, 열 고정)
vector<vector<자료형>> 변수명;	2차원 백터 배열 생성(열, 행 모두 가변)
vector<자료형> 변수명.assign(범위, 초기화값);	생성한 백터의 지정한 범위만큼 초기화값 초기화

vector<int>vec1; //벡터 생성
vector<int>vec2(5); //크기 5의 벡터 생성
vector<int>vec3 = { 1,2,3,4,5 }; //오른쪽 값으로 초기화된 벡터 생성
vector<int>vec4[] = { {1,2,3,4,5} ,{1,2,3,4,5} }; //2차원 벡터 배열 생성(행 가변, 열 고정)
vector<vector<int>>vec5; //2차원 벡터 배열 생성(행 열 가변)
vector<int>vec6; //생성한 벡터의 크기 5의 초기값 10으로 초기화
vec6.assign(5, 10);

 

vector iterators(반복자)

방법	설명
벡터명.begin()	벡터의 시작점의 주소값 반환
벡터명.end()	벡터의 끝부분 + 1의 주소값 반환

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

cout << *abc.begin(); //출력 결과 : 1
cout << *abc.end(); //현재 벡터의 크기를 벗어난 값이라 오류 발생

 

vector 요소 접근

방법	설명
벡터명.front()	벡터의 첫번째 값 접근
벡터명.back()	벡터의 마지막 값 접근

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

cout << abc.front(); //출력 결과 : 1
cout << abc.back(); //출력 결과 : 5

 

vector 요소 삽입

방법	설명
벡터명.push_back(값);	벡터 마지막 부분에 값 추가
벡터명.insert(삽입할 위치의 주소값, 값);	벡터의 삽입할 위치의 주소에 지정한 값을 삽입
벡터명.erase(삭제할 위치의 주소값);	삭제할 위치의 주소값을 찾아 벡터에서 삭제
벡터명.clear();	벡터의 모든 요소를 삭제(메모리 공간은 그대로 남음)
벡터명.resize(크기);	벡터의 크기를 지정한만큼 늘리고 0으로 모두 초기화

vector<int>abc;

abc.push_back(1); //출력 결과 : 1
abc.push_back(2); //출력 결과 : 1 2

abc.insert(abc.begin() + 1, 9); //출력 결과 : 1 9 2
abc.insert(abc.end(), 7); //출력 결과 : 1 9 2 7

abc.erase(abc.begin()); //출력 결과 : 9 2 7

abc.clear(); //abc벡터 안의 값 삭제

abc.resize(10); //출력 결과 : 0 0 0 0 0 0 0 0 0 0

clear()를 통해서 벡터의 값을 지우게 되면 벡터의 요소들은 사라지지만 capacity()는 아직 남아있다.

따라서 clear() 이후 다시 사용하지 않는다면 메모리 공간이 낭비되는 메모리 누수가 발생할 수도 있다.

 

 

vector 크기

방법	설명
벡터명.size()	현재 벡터가 생성된 크기값 반환
벡터명.capacity()	현재 벡터의 최대 할당 크기값 반환(내부버퍼 포함)
벡터명.reserve(크기)	capacity()의 크기를 임의로 지정
벡터명.shrink_to_fit()	불필요한 capacity()의 내부버퍼를 제거

vector<int> abc(5);

cout << abc.size(); //출력 결과 : 5
cout << abc.capacity(); //출력 결과 : 5

abc.push_back(9);
cout << abc.size(); //출력 결과 : 6
cout << abc.capacity(); //출력 결과 : 7

abc.push_back(9);
cout << abc.size(); //출력 결과 : 7
cout << abc.capacity(); //출력 결과 : 7

abc.push_back(9);
cout << abc.size(); //출력 결과 : 8
cout << abc.capacity(); //출력 결과 : 10

abc.reserve(20); //capacity 내부버퍼 포함 크기 20으로 지정

abc.push_back(9);
cout << abc.size(); //출력 결과 : 9
cout << abc.capacity(); //출력 결과 : 20

abc.shrink_to_fit(); //불필요한 capacity의 내부버퍼 제거

cout << abc.size(); //출력 결과 : 9 
cout << abc.capacity(); //출력 결과 : 9

push_back()으로 계속 벡터의 크기를 늘리니까 그에 맞춰 size()도 같이 늘어나는 것을 볼 수 있다.

여기서 중요한건 capacity()의 값인데, 점점 늘어날수록 현재 사용되는 size() 값보다 미리 많게 할당되는 것을 볼 수 있다.

또한 미리 할당된것을 다 사용하면 다음번에는 +1된 크기를 미리 할당하는 것을 볼 수 있다.

 

이처럼 벡터는 크기가 늘어날 것을 대비하여 미리 내부버퍼를 준비한다. 그런데 크기가 계속 커질수록 미리 준비하는

내부버퍼의 크기 또한 +1씩 증감된다.

 

reserve()

그런데 벡터의 크기가 capacity()의 값을 초과할 때마다 메모리에서 재할당(reallocate)가 일어나게된다.

여기서 재할당은 벡터의 모든 값을 새로운 메모리 공간에 복사한 뒤, 기존의 벡터를 파괴하는 방식이다.

이러한 재할당이 자주 일어나게 된다면 프로그램의 성능 저하가 발생하는 문제가 있다.

그래서 이를 해결하고자 capacity() 크기를 미리 넉넉하게 설정해줄 수 있는 reserve() 함수가 존재한다.

 

shrink_to_fit()

그런데 또 여기서 reserve() 함수로 너무 많은 크기를 설정하고 나중에 쓰지 않는 내부 버퍼들이 남게 되는 것도 문제이다.

그래서 이를 해결하고자 불필요한 내부 버퍼를 제거해주는 shrink_to_fit() 함수가 존재한다.