c++ vector
-vector란?
동적으로 크기(용량)가 변하는 배열이라고 생각하면된다.
배열의 경우 int a[10];과 같이 선언하면 a배열은 10개의 value만 갖고있을 수 있지만 vector는 이와 같은 제약이 없다.
-헤더파일
#include<vector>
-생성
1)default 생성자:
vector<data_type> v;
비어있는 vector를 생성
2) 크기 지정 생성자:
vector<data_type> v(4);
크기(원소 수)가 4인 vector 생성 원소들은 0으로 초기화 된다.
3)크기와 초기화 쌍 생성자:
vector<data_type> v (4,100);
크기가 4이며 모두 100으로 초기화
4) 다른 vector의 원하는 범위 지정 생성자:
vector<data_type> v(first_iterator , last_iterator);
다른 vector의 복사 하기를 원하는 시작 위치와 끝 위치의 다음 iterator를 매개변수로 전달하여 vector 생성
5) 다른 vector 통째로 복사시키는 생성자
vector<data_type> v (a);
백터a를 그대로 복사한 v 생성
6) list로 원소 지정 생성자
vector<int> v( {1,2,3,4,5,6,7,2} );
list 값을 그대로하여 vector 생성
-함수
1)begin():
시작 위치를 가리키는 정방향 iterator 반환
2)end():
마지막 요소 다음 위치(맨 마지막 요소 다음)를 가리키는 정방향iterator 반환
3)rbegin():
끝 요소를 가리키는 역방향 iterator 반환
4)rend():
시작 요소 전 위치를 가리키는 역방향 iterator 반환
*역방향 iterator란?
역방향_it++ 하면 index가 1증가한 위치로 가는것이 아닌 index가 1감소한 위초로 간다.
ex) vector<int> v({1,2,3});
vector<int>::iterator it=v.rbegin();
for(; v.rend()!=it ; it++;){
cout<<*it;
}
결과는
3
2
1
5)assign()
기존 백터의 원소들을 새로운 원소들로 대체한다.
그럼으로 새로운 원소수로 size는 변화 하지만 capacity는 그대로다.(이후에 설명)
3가지 유형이 존재
첫번째> void assign (원소갯수, 초기값)
두번째> void assign ( {list} )
세번째> void assign ( first_iterator, last_iterator)
ps. 생성자와 거의유사! vector 변수를 새로 생성하지 안는거뿐
6)[]과 at():
둘다 요소에 접근시 사용한다.
*[]는 범위를 벗어나면 예외 처리x , at은 범위를 체크해서 예외 처리를 해줌
그 외에는 차이x 시간복잡도는 둘다 상수시간
ps.접근 범위 예측이 어려울 경우엔 안전하게 at을 사용하자
7)back():
가장 맨 뒤에있는 (참조)값을 리턴
8)front():
가장 맨 앞에있는 (참조)값을 리턴
9)size():
vector에 저장된 요소의 갯수 리턴
10)capacity():
int capacity()로 vector의 용량을 리턴한다.
*capacity와size의 차이는?
capacity는 vector의 용량 size는 현재 vector에 담겨있는 원소수를 의미한다.
맨 처음 vector를 소개하면서 크기(용량)가 변하는 배열이라 말했다.
용량은 현재 vector가 담을 수 있는 최대 원소의 갯수를 의마한다.
결국 vector는 용량이 가득차면 이를 용량을 자동적으로 늘려주는 자료구조이다.
결과:
7
9
11)max_size():
int max_size()
vector가 가질 수 있는 최대 용량 리턴
12) clear():
vector에 있는 모든 요소 삭제 size는 0 capacity는 그대로
13) data():
value_type* data()
vector의 첫번째 원소의 iterator가 아닌 포인터를 리턴한다.
14) empty():
vector가 비어있으면 1을 리턴 아니면 0을 리턴
15)erase:
원하는 위치의 iterator를 매개변수로 넘겨주면 해당 위치 요소 제거한다.
중간 값을 없애도 자동적으로 vector를 조절해 선형 구조를 유지한다.
*2가지 유형
->첫번째= iterator erase(iterator) iterator가 가리키는 위치 원속 삭제 시간복잡도:O(N)
->두번째= iterator erase(iterator first , iterator last) first~last직전원속들 삭제 시간복잡도: O(N)
삭제된 노드의 전방 노드 iterator를 반환
11) insert(3가지 유형):
원하는 위치에 원소를 삽입할 수 있다.
예를들어 index 5 위치에 insert한다면 기존 index 5위치~끝위치 원소는 한칸씩 뒤로 밀린다.
리턴값으로 첫번째로 삽이된 요소의 iterator를 반환
*만약 insert 이전에 iterator를 통해 어떤 요소를 가리키고있다가 insert가 발생하고 capacity의 변화가 발생하면
iterator는 잘못된 주소를 가리키게 된다. 그럼으로 꼭! insert하고 iterator를 다시 초기화해주자!!!!!
why? 1)iterator가 vector의 3번째 원소가 존재하는 "abc"주소를 가리키고있다.
2) insert발생 , capacity 증가 필요
3) 원본 데이터 -> 새로할당 받은 공간에 복사
4) 원본 데이터 공간 free
5) iterator는 이전 공간을 가리키고 있다.
시간복잡도=O(N)
첫번째> iterator insert (iterator position , type& val)
position위치에 val을 원소로 삽입
ex) v.insert( it , 5 );
두번째> iterator insert (iterator position , int n , type& val)
position위치에서 부터 n개의 val을 원소로 삽입
ex) v.insert( it , 10 , "abc" );
세번째> iterator insert (iterator position , iterator first , iterator last)
position위치에서 부터 first~last이전 원소들을 삽입
ex) v.insert( it , it_1 , it_2 );
*first와 last위치에는 선형 자료구조의 포인터도 매개변수 인자로줄 수 있다.
ex) int a[2]={1,2};
int *p=a;
v.insert(v.begin() , p , p+2);
이때 position자리는 무조건 iterator
12) push_back:
void push_back (type value);
백터 맨뒤에 원소 추가
시간복잡도: O(1) but 용량 재할당시 O(N)
ex) v.push_back(1);
13) pop_back:
void pop_back();
백터 맨뒤 원소 삭제
시간복잡도:O(1)
14) reserve:
void reserve(int n)
용량을 재할당시키는 함수이다.
n이 현재 capacity보다 작다면 작동하지 안는다.
n이 현재 capacity보다 크면 용량을 늘린다.
*insert에서 설명 했듯이 똑같이 reserve도 모든 사용중인 iterator를 다시 초기화 해줘야한다.
15) resize:
void resize ( int n , type value)
vector의 크기를 n으로 만든다.
만약 n이 현재 size보다 작으면 n+1번째 원소부터는 날려버린다.
n이 현재 size보다 크면 value부분을 생략한 경우 n-size개를 0으로 채우고
value를 지정해주면 해당 n-size개를 value로 채운다.
( 2번째 매개변수는 생략 가능)
16) shrink_to_fit:
void shrink_to_fit();
capacity를 size와 같게 capacity를 줄인다.