<STL> Vector

Vector의 특성

• Vector는 동적 배열로 구현되어 있다.
  • 동적이란 프로그램이 실행될 때 무언가가 변화한다는 뜻이다.
  • Vector는 실행 시 원소의 개수가 변할 수 있다.
  • 배열에서 변화할 수 있는 것은 원소의 개수이기 때문이다.
• Vector는 연속된 메모리를 사용하여 원소를 저장한다.
• 원소가 가득차게되면 메모리를 요청하여 새로 확보한다.
  • 현재 담을 수 있는 원소의 개수보다 더 큰 메모리 공간을 요청
  •  새 메모리에 현재 원소를 모두 복사
  • 복사한 원소들의 다음 위치에 새 원소를 추가한다.
  • 이전에 사용한 메모리는 반환한다.
• Vector의 메모리 할당 연산은 큰 비용을 요구한다.

장단점

장점

• Vector의 크기는 동적으로 조정이 가능하다.
• Vector는 [] 연산자를 통해 배열과 같이 특정 인덱스의 원소에 바로 접근할 수 있다.
• Vector의 요소들은 메모리에 연속적으로 저장되어 일반 배열과 같이 cache hit rate가 높아 빠른 속도로 접근이 가능
• Vector는 다차원 배열도 생성할 수 있다.

단점

• Vector는 크기를 동적으로 조정하여, 크기가 변경될 때마다 Vector의 요소들이 메모리에서 재배치될 가능성이 있다.
  • 크기변경이 빈번하게 일어날 경우 성능 저하가 발생할 수 있다.
• Vector는 포인터를 사용하는 구조체와는 호환성이 떨어질 수 있다.
  • 요소들을 메모리에 연속적으로 저장하기 때문에, 포인터를 사용하는 구조체와 호환성이 떨어질 수 있다.
• Vector는 요소들을 연속된 메모리 공간으로 복사하는 것이 가능하지만, Vector의 요소들이 메모리에 연속적으로 저장되지 않을 경우 복사가 불가능하다.
• Vector는 요소들을 추가하거나 제거할 때마다 메모리를 재할당하기 때문에, 메모리 사용량이 불필요하게 증가할 수 있다.

Vector의 멤버

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v;
	
	cout << "sizeof vector = " << sizeof(v) << '\n';
	cout << "size = " << v.size() << '\n';
	cout << "data = " << v.data() << '\n';
	cout << "capacity = " << v.capacity() << '\n';
	return 0;
}

// 출력
sizeof vector = 16
size = 0
data = 00000000
capacity = 0

• vector의 Byte 크기는 16byte이다.
• Size, Data, Capacity 3개의 멤버 변수를 가지고 있다.
  • size() : Vector가 저장하고 있는 원소의 개수
  • data() : 동적 배열 데이터의 메모리 시작 주소
  • capacity() : Vector가 담을 수 있는 데이터의 최대 개수
• 아무 원소가 없는 vector의 size, data, capacity는 0과 NULL로 초기화 되어 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v{ 1,2,3,4,5,6 };
	
	cout << "sizeof vector = " << sizeof(v) << '\n';
	cout << "size = " << v.size() << '\n';
	cout << "data = " << v.data() << '\n';
	cout << "capacity = " << v.capacity() << '\n';
	return 0;
}

// 출력
sizeof vector = 16
size = 6
data = 00CE52F8
capacity = 6

• vector에 원소가 있다면 size, data, capacity는 값을 가지게 된다.

Vector의 메모리 할당

• vector의 size와 capacity를 비교하여 확인할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v;

	for (int i = 0; i < 1000; i++) {
		v.push_back(100);
		cout << v.size() << " " << v.capacity() << '\n';
	}
	return 0;
}

// 출럭
1 1
2 2
3 3
4 4
5 6
6 6
7 9
8 9
9 9
10 13
11 13
12 13
13 13
14 19
15 19
16 19
17 19
18 19
19 19
20 28
21 28
22 28
23 28
24 28
25 28
26 28
27 28
28 28
...
972 1066
973 1066
974 1066
975 1066
976 1066
977 1066
978 1066
979 1066
980 1066
981 1066
982 1066
983 1066
984 1066
985 1066
986 1066
987 1066
988 1066
989 1066
990 1066
991 1066
992 1066
993 1066
994 1066
995 1066
996 1066
997 1066
998 1066
999 1066
1000 1066

• size는 배열의 원소가 추가됨에 따라 1씩 증가한다.
• capacity는 초반에는 1씩 늘어나다 1.5배씩 증가하는 것을 알 수 있다.
• Vector도 배열이기 때문에 연속된 메모리에 값이 저장되어야 한다.
• 첫 생성 시 임의의 메모리를 할당받은 후 데이터를 쌓아가다 여유분까지 사용하면 더 큰 메모리 공간으로 이사한다.
  • 기존에 있던 데이터는 새로운 메모리 공간에 복사된다.
• 잦은 복사가 일어나면 실행 시간에 지연을 발생시킬 수 있으므로 capacity를 초기에 설정해 주어야한다.
  • reserve() 함수를 통해 해결할 수 있다.
  • reserve() 함수 뿐만 아니라 선언과 동시에 size와 데이터를 지정해 줄 수도 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v(1000, 0); // 선언과 동시에 초기화

	v.reserve(1000); // reserve 함수를 이용

	return 0;
}

• capacity를 초기에 설정하면 처음부터 크기를 1000으로 사용할 수 있다.
  • size가 1000을 넘지 않을 때 까지 메모리를 이동하지 않아 효율적이다.
  • 하지만 한번 정한 capacity는 변화하지 않으므로 적절한 용량을 선택해야한다.

반복자

• Vector도 iterator를 사용하여 원소를 탐색할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v;
	v.reserve(10);
	for (int i = 0; i < 10; i++)
		v.push_back(i);

	vector<int>::iterator it = v.begin();
	cout << (*it) << "\n\n";

	for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
		cout << (*it) << '\n';
	}
	return 0;
}

// 출력
0

0
1
2
3
4
5
6
7
8
9

• rbegin(), rend() 반복자를 사용하여 역으로 원소를 탐색할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v;
	v.reserve(10);
	for (int i = 0; i < 10; i++)
		v.push_back(i);

	for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
		cout << (*it) << '\n';
	}
	return 0;
}

// 출력
9
8
7
6
5
4
3
2
1
0

임의 접근

• 임의 접근(Random Access)는 아무 값이나 쉽게 접근한다는 뜻으로 벡터와 같은 배열에서 지원한다.
• 배열은 데이터를 쉽게 찾기 위해 원소가 하나의 메모리 블록에 연속하게 저장된다는 특징이 있다.
  • 이러한 특성이 임의 접근을 가능하게 해준다.

시간 복잡도

1. 접근 - O(1)
   • Vector의 임의 원소 접근 시간복잡도는 O(1)이다.
   • Vector는 [] 연산자를 통해 배열과 같이 특정 인덱스의 요소에 바로 접근할 수 있다.
   • Vector의 요소들은 메모리에 연속적으로 저장되어 있기 때문에 포인터 연산을 통해 바로 접근이 가능하다.
2. 검색 - O(n)
   • Vector에서 검색의 시간복잡도는 O(n)이다.
   • Vector는 요소들이 메모리에 연속적으로 저장되어 있기 때문에, 특정 요소를 검색하기 위해서는 요소들을 모두 순회해야 한다.
3. 삽입 및 삭제 - O(1), O(n)

• push_back()
  • Vector의 끝에 새로운 요소를 추가하는 경우 시간복잡도는 O(1)이다.
  • Vector의 끝에 요소를 추가할 때는 이미 메모리가 할당되어 있기 때문에, 추가적인 메모리 할당이 필요하지 않다.
• pop_back()
  • Vector의 끝에서 요소를 제거하는 경우 시간복잡도는 O(1)이다.
  • Vector의 끝에서 요소를 제거할 때는 메모리의 일부분만 해제하면 되기 때문에, 시간복잡도가 낮다.
• insert()
  • Vector의 특정 위치에 요소를 삽입하는 경우 시간복잡도는 O(n)이다.
  • 삽입 위치 이후의 요소들을 모두 이동시켜야 하기 때문에 시간복잡도가 높다.
• erase()
  • Vector에서 특정 위치 또는 범위에 있는 요소를 제거하는 경우 시간복잡도는 O(n)이다.
  • 제거된 요소 이후의 요소들을 모두 이동시켜야 하기 때문에 시간복잡도가 높다.

 

 

 

출처

https://ssinyoung.tistory.com/45

다시 정리하는 C++ STL 자료구조 vector

https://choi-dan-di.github.io/cpp/vector/

[C++] 벡터(Vector)

https://velog.io/@jimojjing/CSTL-Vector

[C++/STL] - Vector