C++ std::vector 사용법
vector란
- vector란 배열과 유사한 데이터 구조체로, 메모리에 연속적으로 저장되는 동적배열이다.
vector 헤더파일
- vector을 사용하기 위해서는
#include <vector>을 넣어야 사용 가능하다. namespace std에 존재하기 때문에std::을 사용해주거나using namespace std;을 사용해주면 된다.
장점
- 크기가 동적으로 조정 가능하다.
- [] 을 사용하여 인덱스에 바로 접근이 가능하다.
- STL에서 제공하는 다양한 함수를 사용할 수 있다.
단점
- 크기가 동적으로 조정하기 떄문에 크기가 변경될 때마다 vector의 요소를 메모리에 재배치할 수 있다. 그렇기 때문에 크기를 변경하게 된다면 성능 저하가 일어날 수 있다. (push_back() 함수는 값을 넣는 과정에서 복사생성자를 호출한다. 또한 insert()을 사용하게 된다면 모든 값을 새로운 메모리에 복사한 수 해당 자리에 값을 넣는다. 그렇기 때문에 inset()나 push_back()을 사용하게 된다면 성능저하가 일어날 수 있다.) 그렇기 때문에 삽입과 삭제를 자주 하게 된다면 vector보다 list나 deque를 사용하는 것이 더 효과적이다.
- 포인터를 사용하는 구조체와 호완성이 떨어질 수 있다. (데이텨를 연속적으로 저장하기 떄문에 포인터를 사용하는 구조체와 호완성이 떨어질 수 있다.
- 요소들을 연속된 메모리 공간으로 복사하는 것이 가능하지만, 요소들이 메모리에 연속적으로 저장되지 않을 경우 복사가 불가능하다.
사용법
vector<자료형> 변수이름;
vector<int> v; // v라는 이름으롷 int형의 자료를 담는다.vector<int> v; // 를 예시로 설명| 멤버함수 사용 | 멤버함수 설명 |
|---|---|
| v.assign(n, val) | - val 값으로 n개의 원소 할당 |
| v.at(index) | - index번째 원소에 접근한다. 범위가 맞는지 아닌지를 확인하는 과정을 거친다. v[index]를 사용하게 된다면 .at()보다는 빠르지만 범위가 맞는지 아닌지를 확인하는 절차가 없다. |
| v.pop_back() | - 마지막 원소를 제거한다. |
| v.push_back() | - 마지막 원소 뒤에 원소를 추가한다. |
| v.size() | - 해당 객체가 보유한 원소들의 개수를 반환한다. |
| v.swap(v2) | - 객체 v와 v2의 원소들을 서로 바꾼다. |
| v.begin() | - 첫번째 원소를 가르킨다.(iterator와 사용) |
| v.end() | - 마지막 원소를 가르킨다.(iterator와 사용) |
| v.front() | - 첫번쩨 원소를 참조한다. |
| v.back() | - 마지막 원소를 참조한다. |
| v.clear() | - 모든 원소를 제거한다. 원소만 제거하고 메모리는 남아있다. |
| v.rbegin() | - reverse begin을 가르킨다. (거꾸로 해서 첫번째 원소를 가르킨다.) |
| v.rend() | - reverse end을 가르킨다.(거꾸로 해서 다음을 가르킨다.) (iterator와 사용) |
| v.reverse(n) | - n개의 원소를 저장할 위치를 예약한다. (미리 동정할당을 한다.) |
| v.resize(n) | - 크기를 n으로 변경한다. 크기가 더 커졌을 경우 0으로 초기호한다. |
| v.reseze(n, val) | - 크기를 n으로 변경하고 더 커졌을 경우에는 val으로 초기화한다. |
| v.insert(p, n, val) | - p번쨰 위치에 n개의 val을 삽입한다. |
| v.insert(p, val) | - p번째 위치에 val의 값을 삽입한다. |
| v.erase(iterator) | - iterator가 가르키는 원소를 제거한다. 사이즈만 줄이고 capacity(할당된 메모리)만 남는다. |
| v.capacity() | - 할당된 공간의 크기를 리턴한다. |
capacity와 size의 차이
- size는 원소의 개수이지만 capacity는 할당된 공간의 크기를 리턴한다.
반복자 사용
for (auto i: v) {
cout << i;
}시간복잡도
- 접근 - O(1)
- 임의 원소 접근 시간 복잡도는 O(1)이다. vector은 연속적으로 저장되어 있기 때문에 포인터 연산을 통해 바로 접근이 가능하다.
- 검색 - O(n)
- 검색의 시간 복잡도는 O(n)이다. 요소가 연속적으로 저장되어 있기 때문에 특정 요소를 검색하기 위해서는 모두 순회를 하여야한다.
- 삽입 및 삭제 - O(1), O(n)
- push_back():끝에 새로운 요소를 추가하는 경우, 시간복잡도 O(1)이다.
- pop_back(): 끝의 요소를 삭제시킬 경우, 시간 복잡도는 O(1)이다. 끝의 원소만 삭제시키면 되기 떄문이다.
- insert(): 시간 복잡도는 O(n)이다. 특정 위치에 요소를 삽입할 때는 모든 원소를 이동시켜야 하기 때문에 시간 복잡도가 높다고 할 수 있다.
- erase(): 특정 위치나 요소를 제거하는 경우, 시간 복잡도는 O(n)이다. 특정 위치나 요소를 제거하기 위해서 모든 원소들을 이동시켜야하기 때문에 시간 복잡도가 높다고 할 수 있다.
개발하는 개구리