vector
1. Sequence Container
2. pop back / pop front 만 가능
3. random access 가능
4. erase로 원하는 원소나 위치, 범위를 삭제할 수 있다.
근데 자주하면 ㅈㄴ 비효율적임. 그냥 다른 자료구조 사용하는게 나음
그리고 애초에 vector로 erase 할거면 안사용하는게 맞음
그냥 vector는 int arr[SIZE] 사용하는 대신 사용하는거임
[vector : 동적인 배열]
vector는 일반 배열(int arr[SIZE])처럼 개체들을 연속적인 공간에 저장한다.
즉, iterator 뿐 아니라 position index(operator [])로도 접근이 가능하다는 것이다.
동적으로 확장/축소가 가능한 동적 배열(dynamic array)로 구현되어 있다.
자동으로 메모리가 할당된다.
추가, 삭제 시 메모리를 신경안써줘도 된다.
자기가 다 알아서 관리한다.
vector는 맨 뒤쪽 + 특정 idx에 값을 삽입하거나 삭제할 수 있다.
하지만 배열 기반이므로 삽입 삭제가 빈번하게 일어나면 비효율적이다
삽입 삭제가 빈번한 상황일때는 vector는 그냥 안사용하는게 맞음 (list나 deque을 생각)
왜냐하면 삽입 삭제가 일어나면 vector는 배열과 똑같은 구조이므로
하나의 원소가 삭제된다면 그 뒤에 원소들을 한 칸씩 앞으로 땡겨와야하기 때문이다.
따라서 시간복잡도가 O(N)이 나온다. 가장 최악의 경우가 맨 앞에꺼 삭제하는 거니까.
삽입상황도 똑같이 생각해보면 된다.
그러므로 중간 삽입,삭제가 빈번한 상황일 경우 vector를 쓰면 매우 비효율적이다.
맨 뒤에서만 삽입 삭제가 일어날 경우에만 사용해야한다.
맨 뒤에 추가,삽입 작업을 할때에는 시간복잡도가 O(1)이다.
왜냐하면 vector는 배열기반이므로 원소개수로 마지막 data를 random access로 접근할 수 있기 때문이다.
( 만약 중간 삽입,삭제 or 맨앞 쪽에서도 삽입,삭제가 일어나는 상황이면 list를 쓰는게 좋다 )
vector를 보면 stack과 비슷하다고 생각할 수 있는데 둘이 헷갈리면 안된다.
vector는 새로운 자료구조라기보다는 그냥 매우 편리한 배열 (C의 array) 라고 생각해주면 좋다.
그냥 ps할때는 배열 대신 사용하는거임
참고로 vector는 erase함수는 있지만 remove(x) 함수는 없다.
[vector functions]
insert
insert 함수의 첫번째 인자는 iterator임
erase
erase 함수는 특정 범위에 속하는 모든 값을 삭제하거나
특정 값 위치를 iterator로 보내면 해당 값을 삭제할 수 있다
erase 함수의 인자는 항상 iterator이다!
resize reserve
이런건 ps때 안쓴다. 몰라도 된다
[vector 정렬]
#include <algorithm> 해서 sort로 정렬할 수 있다.
기본은 오름차순 정렬임
내림차순 하려면 greater 해주면 됨
sort(v.begin(), v.end(), greater<int>());
[중복제거]
가끔 쓰인다.
unique 함수가 있는데 그건 절대 쓰면 안된다!!
일단 unique 함수를 쓰려면 정렬을 한 뒤에 써야하고
그리고 unique 함수가 중복빼고 아예 새로운 vector를 반환하는게 아니라
그냥 중복된건 뒤로 미루는거임
그래서 배열 길이도 unique 전과 똑같고 전체 출력하면 중복된 값들은 모두 뒤로 미뤄져 있음
그래서 그냥 unordered_set으로 받고 마지막에 set을 vector로 바꾸는게 훨씬 효율적임
unordered_set<int> us;
vector<int> v(us.begin(), us.end());