[자료구조] 벡터 Vector

세번째 자료구조 포스팅은 벡터이다!
c++ 로 알고리즘 연습 하면서 수도없이 썼던 벡터인데 이참에 좀 더 알아보고 제대로 쓰자!!

벡터 Vector

벡터는 배열과 매우매우 유사하다.

하지만 배열과 달리 벡터는 초기에 10개의 방을 만들었어도 데이터를 추가할 수 있는데 이는 벡터가 클래스로 구현되어 있기 때문이라고 한다! 나 역시 이부분때문에 벡터를 편리하게 이용하고 있는 것 같다!

하지만 벡터 역시 배열처럼 연속된 메모리 영역을 사용하기 때문에 주소 시작점 부터 데이터를 차곡차곡 쌓아나가고 자연스레 벡터 중간에 데이터를 삽입하거나 삭제하는 과정은 비효율적일 수 밖에 없다.

구현자체가 간단하고 마지막 위치에 데이터를 추가하거나 삭제하는 것은 간단하다. 또한 배열과 동일하게 index 를 사용하여 데이터에 바로 접근이 가능하다. 즉 찾으려는 데이터의 위치를 알고 있다면 빠르게 데이터를 찾을 수 있는 자료구조이다.

하지만 데이터의 위치를 모를때에는 선형 탐색을 통해서 데이터를 찾아야만 하므로 검색 속도가 느릴 수 있다. 엄청 많은 데이터가 줄지어 서있는데 그중 내가 찾는 데이터가 맨 끝에 있는 경우엔 O(N) 의 시간이 걸릴 것이다.

활용

벡터는

• 저장하고자 하는 데이터의 갯수가 가변적일 때
• 중간에 위치한 데이터를 삭제하거나 삽입할 일이 없을 때
• 저장할 데이터가 많다면 검색이 거의 필요하지 않을 때
• 위치를 아는 데이터를 빠르게 접근하고자 할 때

에 적합한 자료구조 이다!

내가 추가적으로 기억할만한 연산

// 벡터 복사
vector<int> v1{1,2,3,4,5};
vector<int> v2(v1); // v1->v2 복사

// 대입 연산자를 활용한 벡터 복사
vector<int> v1{1,2,3,4,5};
vector<int> v2 = v1;

연산	의미
v1==v2	v1, v2의 원소가 같은가
v1!=v2	v1, v2의 원소 중 하나라도 다른 원소가 있는가
v1=v2	v1에 v2를 복사
v[i]	v의 인덱스 i 에 있는 원소 참조
v1>v2	v1 이 v2 보다 크다
v1>=v2	v1 이 v2 보다 크거나 같다
v1<v2	v1 이 v2 보다 작다
v1<=v2	v1 이 v2 보다 작거나 같다

• <, <=, >, >= : 특별히 지정하지 않으면 가장 앞에 있는 원소끼리 비교!

Reference

[자료구조 STL vector 1탄]