[STL] Vector

2024. 12. 31.

 

1. vector?

- dynamic array

- random access iterator (포인터처럼 대부분의 연산 가능)

- 성질은 일반 배열과 유사함.

#include <vector>

시간복잡도

Space	O(n)	Insert	O(n)	Push_back	O(1)
Search	O(n)	Delete	O(n)	Pop_back	O(1)
Migration	O(n)	: 넣거나 지운 위치 앞뒤로 미루고, 당겨야해서 n번이 필요함.		: 얘는 그 과정이 필요하지 않아서 1번

​

2. 공간할당

+ 공간 크기를 바꾸려면?

v.clear()      //size = 0, capacity는 변화 없음.
v.reserve(x)   //capacity를 x로 변경. 기존 크기보다 클 때만 실행. 기존 크기보다 작으면 무시함. 
v.rexize(x)    //size를 x로 변경. capacity가 x보다 작으면 할당 후 변경
/* size가 x보다 작으면 남는 공간을 0으로 삭제함. 
size가 x보다 크면 x 사이즈까지만 자르고 뒤에 남는 것은 버림. 용량은 그대로. */

​

3. 원소 삭제

1. erase()	2. 마지막 element로 덮어쓰기
O(n) element들의 순서가 유지O	O(1) element들의 순서가 유지X
v.erase(v.begin()+2);	① v[2] = v.back(); ② v.pop_back();

+ 2번방법은 순서가 무관하다면 좋은 방법임. vector의 개수가 많아질수록 더더욱.

​

4. vector 주요 문법

template<
    class T,
    class Allocator = std :: allocator<T>  // 모든 컨테이너가 allocator포함하므로 별도 설정x
> class vector;

vector <T> v  // size_t : unsigned long long

iterator v.begin(), v.eng()    // iterator 반환 v.begin == v.front
reverse_iterator v.rbegin(), v.rend()
T v[int idx]    // 배열의 인덱스에 접근. T v[0] T v[i]
bool v.empty()   // vector가 비어있는지 확인하기 - iterator 공통
void v.clear()   // 초기화  - iterator 공통
size_t v.size()  // 크기, 개수  - iterator 공통
size_t v.capacity()  // 용량
void v.resize(int n), v.reserve(int n) // 크기 변경, 용량 변경
T v.front(), v.back() // 맨앞, 뒤의 value값을 반환
void v.push_back(T x), v.pop_back()   // 맨 뒤에 원소 넣고 빼기

iterator v.insert(iterator pos, T x) // x를 pos위치에 넣어라(index 아님)
iterator v.insert(iterator pos, int count, T value) // value값을 pos위치에 count개 넣어라
iterator v.insert(iterator pos, iterator first, iterator last) // [first,last)를 pos에 넣어라
// 얘네를 실행하면 처음 입력된 element의 iterator를 반환함. 등록된 위치의 iterator, 구간은 맨 앞
// 구간 입력할 때 v.begin 이게 맨앞 두번째는 v.begin+1 이런 방식으로 입력. index로 쓰는거 아님

iterator v.erase(iterator pos)
iterator v.erase(iterator firest, iterator last)
// 마지막 지워진 element의 다음 iterator 반환
// ex) iterator v.erease(v.begin, v.begin+3)  -> 1,2,3번 element 지우고 4번 반환

 

 

5. vector 예시

vector <T> v
for (int i=1; i<=5; i++)v.pudh_back(i); // 1 2 3 4 5

for (int i=0; i<v.size(); i++) cout << v[i] << ' ';  // 배열처럼 돌기 inedx 이용
for (auto x:v) cout << x << ' '; //range base loof 사용하기

vector<int>::iterator it //(iterator type)
for (auto it = v.begin(); it != v.end; ++it) cout << *it << ' ';  // 일반적인 iterator 순회

vector<int>::reverse iterator it //(iterator type)
for (auto it = v.rbegin(); it != v.rend; ++it) cout << *it << ' '; // 5 4 3 2 1

v.insert(v.begin(),6);  // 6 1 2 3 4 5
v.insert(v.end(), 7);   // 6 1 2 3 4 5 7
v.insert(v.begin() +3, 8);   // 6 1 2 8 3 4 5 7

v.erase(v.begin() +1);   // 6   2 8 3 4 5 7    // erase는 reverse사용 x error남
v.erase(v.end() -1);     // 6 2 8 3 4 5
v.pop_back();             // 6 2 8 3 4

v[2] = 0;    // 6 3 0 3 4
v.empty();   // 0
v.size();    // 5

sort(v.begin(), v.end());   // 0 2 3 4 6