- Vector STL
배열을 사용할 때는 크기를 명시해주어야하고, 무조건 해당 크기 안에서만 사용가능하다.
그러나 Vector는 일종의 가변 배열로, 크기를 늘렸다 줄였다 할 수 있다.
Vector는 Vector 헤더에 선언되어있다.
vector<int> v(100); ----------------1)
v[20] = 10; ----------------2)
v[60] = -4; ----------------3)
1) type이 int이고 0으로 초기화된 100칸짜리 가변배열 v
2), 3) 일반적인 배열처럼 인덱스에 접근해서 값을 바꿀 수 있다.
- STL을 함수 인자로 넘길 때
답은 0
STL도 구조체와 비슷하게 함수 인자로 보내면 복사본을 만들어서 보내기 때문에 func1에서 바꾼 것은 원본에 영향을 주지 않는다.
1) cmp1 함수
두 vector를 인자로 넘겨받아 idx 번째 원소의 값을 비교한 결과를 반환하는 함수
Q) 두 vector의 크기가 N이라고 할 때 이 함수의 시간 복잡도는? O(N)
=> v1,v2를 인자로 실어 보낼 때 원본으로부터 복사본을 만드는 비용을 생각해야한다.
v1,v2의 크기가 N이므로 N개의 원소들을 하나하나 복사하는 과정은 O(N)이다.
그러나, idx 번째의 원소 값을 비교하는데 vector전체를 복사하는 것은 비효율적이다. 이럴 때 참조자를 이용하면 된다.
2) cmp2함수
v1,v2의 type을 vector<int>의 reference로 만들었다. 즉, cmp2가 호출될 때 복사본을 따로 만들어내지 않고 참조 대상의 주소정보만 넘어가기 때문에 시간 복잡도는 O(1)이 된다.
댓글