[Algorithm] STL 벡터(Vector)

벡터

벡터는 동적배열을 만드는 연산을 수행한다.

벡터를 사용하기 위해서는 <vector>를 포함해야 한다.

또한 vector는 namespace std에 존재한다.

 

벡터의 요소는 어떤 자료형이라도 올 수 있다.

두 번째 템플릿 매개변수로 메모리 모델을 정의할 수 있는데 기본 메모리 모델은 allocator 모델이다.

 

기능 

벡터는 자신의 요소를 내부의 동적 배열로 복사한다.

벡터는 임의 접근을 제공한다.

즉, 위치를 안다면 상수 시간 내에 접근할 수 있다.

동적배열이기 때문에 중간에 데이터를 삽입/삭제 하는 경우 성능이 떨어진다.

 

벡터는 현재 요소를 저장하기 위한 메모리보다 많은 메모리를 할당한다.

현재 메모리보다 더 많은 요소가 삽입되면 벡터는 재배치를 수행한다.

벡터의 용량은 매우 중요한데 그 이유는 2가지가 있다.

 

1. 배열을 재배치할 경우 벡터의 요소에 대한 모든 참조자, 포인터, 반복자가 무효가 된다.

2. 재배치하는데 시간이 걸린다.

 

재배치를 피하기 위해서 특정 용량을 미리 reserve()로 확보할 수 있다.

혹은 생성자에 추가로 인자를 제공하여 벡터를 초기화하는 방법도 있다.

 

벡터의 용량은 줄어들지 않기 때문에 요소가 삭제되어도 아무런 변화가 없다.

 

연산 

생성자와 소멸자

연산	설명
vector<Elem> c	기본 생성자, 아무런 요소도 갖지 않는 벡터를 만든다
vector<Elem> c(c2)	복사 생성자, 같은 데이터형의 다른 벡터 c2를 복사한다. 모든 요소를 복사한다.
vector<Elem> c = c2	복사 생성자, 같은 데이터형의 다른 벡터 c2를 복사한다. 모든 요소를 복사한다.
vector<Elem> c = rv	이동 생성자. rv의 내용을 갖는 새로운 벡터를 만든다 ( C++11 이후 지원 )
vector<Elem> c(n)	이동 생성자. rv의 내용을 갖는 새로운 벡터를 만든다 ( C++11 이후 지원 )
vector<Elem> c(n,elem)	기본 생성자로 초기화된 n개의 요소를 갖는 벡터를 만든다
vector<Elem> c(beg, end)	n개의 elem을 요소로 갖는 벡터를 만든다
vector<Elem> c(initlist)	초기화자 목록 내의 요소로 초기화된 벡터를 만든다 ( C++11 이후 지원 )
vector<Elem> c = initlist	초기화자 목록 내의 요소로 초기화된 벡터를 만든다
c.~vector()	모든 요소를 삭제하고 메모리를 해제한다.

 

 

수정하지 않는 연산

연산	설명
c.empty()	컨테이너가 비었는지 여부를 반환 ( c.size()==0과 같지만 속도가 더 빠를 수 있다 )
c.size()	현재 요소의 수를 반환
c.max_size()	최대 저장 가능한 요소의 수를 반환
c.capacity()	재할당없이 저장할 수 있는 요소의 최대 수르리 반환
c.reserve(num)	벡터의 옹량을 증가
c.shrink_to_fit()	요소의 수에 맞도록 용량을 줄이라고 요청, 반드시 성공하는 것은 아니다 ( C++11 이후 지원 )
c1 == c2	c1이 c2와 같은지 반환, 모든 요소가 같아야 한다
c1 != c2	c1이 c2와 다른지 반환
c1 < c2	c1이 c2보다 작은지 반환
c1 > c2	c1이 c2보다 큰지 반환
c1 <= c2	c1이 c2보다 작거나 같은지 반환
c1 >= c2	c1이 c2보다 크거나 같은지 반환

 

 

할당

연산	설명
c = c2	c2의 모든 요소를 c에 할당
c = rv	rv의 모든 요소를 c에 이동할당 ( C++11 이후 지원 )
c - initlist	초기화자 목록 내의 모든 요소를 c에 할당 ( C++11 이후 지원 )
c.assign(n, elem)	n개의 elem을 요소로 할당
c.assign(beg, end)	범위 [beg, end) 내 요소를 할당
c.assign(initlist)	초기화자 목록 내의 모든 요소를 c에 할당
c1.swap(c2)	c1과 c2의 데이터를 교환
swap(c1, c2)	c1과 c2의 데이터를 교환

 

 

요소 접근

벡터의 모든 요소에 접근하기 위해서는 범위 기반 for문, 반복자, 특정 연산을 사용해야 한다.

다른 이유로 막혀있지 않다면 C++이 제공하는 연산을 사용해 요소를 수정할 수 있다.

연산	설명
c[idx]	인덱스 idx에 있는 요소 반환, 범위 검사를 하지 않음
c.at(idx)	인덱스 idx에 있는 요소 반환, 범위 검사를 한다. 범위를 넘어선 경우 범위 오류 예외를 던짐
c.front()	첫 번째 요소 반환, 첫 번째 요소가 있는지 확인하지 않음
c.back()	마지막 요소 반환, 마지막 요소가 있는지 확인하지 않음

 

 

iterator 함수

벡터 반복자는 임의 접근 반복자이다.

따라서 STL의 모든 알고리즘을 사용할 수 있다.

반복자는 더 작은 인덱스에 요소가 삽입되거나 제거되거나 재할당이 일어날 때까지 유효하다.

연산	설명
c.begin()	첫 번째 요소에 대한 임의 접근 반복자 반환
c.end()	마지막 요소 다음 위치에 대한 임의 접근 반복자 반환
c.cbegin()	첫 번째 요소에 대한 임의 접근 상수 반복자 반환 ( C++11 이후 지원 )
c.cend()	마지막 요소 다음 위치에 대한 임의 접근 상수 반복자 반환 ( C++11 이후 지원 )
c.rbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 반복자 반환
c.rend()	역방향 반복에서의 마지막 요소의 다음 위치에 대한 역방향 반복자 반환
c.crbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )
c.crend()	역방향 반복에서의 마지막 요소의 다음 위치에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )

 

 

요소 삽입과 제거

반복자는 유효한 위치를 가리켜야하고, 범위의 시작은 범위의 끝을 지나지 않은 지점을 가리켜야 한다.

인자들이 유효한지는 프로그래머가 검사해야한다.

연산	설명
c.push_back(elem)	elem의 복사본을 벡터의 끝에 삽입
c.pop_back()	마지막 요소 삭제, 반환하지 않음
c.insert(pos, elem)	반복자 위치 pos 앞에 elem의 복사본을 삽입 후 새 요소의 위치를 반환
c.insert(pos,n,elem)	반복자 위치 pos앞에 elem의 복사본 n개 삽입 후 새 요소 중 첫 번째 요소 위치 반환, 새 요소가 없는 경우 pos 반환
c.insert(pos, beg, end)	반복자 위치 pos 앞에 범위 [beg, end) 내 모든 요소의 복사본을 삽입 후 새 요소 중 첫 번째 요소 위치 반환, 새 요소가 없는 경우 pos 반환 ( C++11 이후 지원 )
c.insert(pos, initlist)	반복자 위치 pos 앞에 초기화 목록 내 모든 요소의 복사본 삽입 후 새 요소 중 첫 번째 요소의 위치 반환, 새 요소가 없는 경우 pos 반환 ( C++11 이후 지원 )
c.emplace(pos,args...)	반복자 pos 앞에 인자 args로 초기화된 요소의 복사본을 삽입 후 새 요소의 위치 반환 ( C++11 이후 지원 )
c.emplace_back(args...)	인자 args로 초기화된 요소의 복사본을 벡터에 끝에 삽입, 아무것도 반환하지 않음 ( C++11 이후 지원 )
c.erase(pos)	반복자 위치 pos에 있는 요소 삭제 후 다음 요소의 위치 반환
c.erase(beg, end)	범위 [beg, end) 내 모든 요소 삭제 후 다음 요소의 위치 반환
c.resize(num)	요소의 수를 num개로 바꿈, 만약 size()가 커질 경우 새 요소들은 자신의 자료형에 맞는 기본 생성자로 초기화된다
c.resize(num, elem)	요소의 수를 num개로 바꿈, 만약 size()가 커질 경우 새 요소들은 elem의 복사본으로 초기화된다
c.clear()	모든 요소를 제거, 컨테이너를 비운다.

 

 

벡터를 C 배열처럼 사용하기

vector<>의 요소들이 연속된 메모리 상에 존재한다는 걸 보장한다.

따라서 &v[i] == &v[0] + i 는 참이다.

 

예외처리 

벡터가 호출한 함수가 예외를 던진다면 C++ 표준 라이브러리는 다음과 같은 사항을 보장한다.

1. 요소가 push_back()으로 삽입하던 중 예외가 발생하면 이 함수는 아무 영향도 미치지 않는다.

2. 요소의 복사/이동연산이 예외를 던지지 않을 경우 insert(), emplace(), emplace_back(), push_back()은 성공하거나 아무런 영향도 미치지 않는다.

3. pop_back()은 어떠한 예외도 던지지 않는다.

4. erase()는 요소의 복사/이동연산이 예외를 던지지 않는 경우 예외를 던지지 않늗나.

5. swap()과 clear()는 아무런 예외를 던지지 않는다.

6. 요소의 복사/이동연산이 절대로 예외를 던지지 않는 경우 모든 연산은 성공하거나 아무런 영향도 미치지 않는다.

 

이 모든 보장은 소멸자가 예외를 던지지 않는다는 전제하에 제공된다.

 

클래스 vector<bool> 

불리언 요소를 위한 vector<>의 특수화이다.

이는 비트벡터를 지원하는 것인데 문제점은 주소값이다.

C++에서 주소값의 최소 단위는 1바이트이다

그런데 vector<bool>은 각 요소에 1비트만 할당하여 사용한다.

따라서 참조자와 반복자에게 특별한 처리를 해야한다.

vector<bool>의 크기는 동적이다.

따라서 정적 비트벡터가 필요하다면 bitset을 사용하자.

vector<bool>만 제공하는 연산들이 있다.

연산	설명
c.flip()	모든 불리언 요소의 값을 뒤집는다,. 모든 비트의 보수
c[idx].flip()	인덱스 idx에 있는 불리언 요소의 값을 뒤집는다. 단일 비트의 보수
c[idx] = val	인덱스 idx에 있는 불리언 요소에 값 val 할당
c[idx1] = c[idx2]	인덱스 idx2에 있는 요소의 값을 인덱스 idx1에 있는 요소에 할당