[STL] Vector에 관해서

 + 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

 + 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!

[Vector]

 + vector는 STL의 대표적인 sequence container로 배열과 비슷하여 많이들 사용합니다.

 + template 기반으로, 여러 type의 자료들을 보관할 수 있으며, 요소에 따라 동적으로 관리됩니다.

 + 다른 container들에 비해 구조가 단순해서 사용방법이 쉬우며, 속도도 빠른 편입니다.

 + 밑의 Dynamic특징으로 인해, vector의 요소는 하나의 memory block에 연속적으로 저장이됩니다.

 + 연속적으로 저장되기에, index나 at()으로 요소에 접근하기에 굉장히 효율적입니다.

[Dynamic]

 + vector에 요소가 추가 될 때마다 크기가 증가하지만, 이것은 실제로 계속 relocate되는 것이 아닙니다.

 + relocate는 상당히 부하가 심한 작업으로, 크기가 늘어날 때 마다 해주기에는 큰 퍼포먼스가 뒤따릅니다. 그래서 내부적으로 한 번에 크게 용량을 잡아줍니다. 즉, 외부에선 하나씩 늘어나는 것 처럼 보여도, 내부는 아닌 것이죠.

 + 내부적으로 vector의 라이브러리들(크기를 증가시키는 것들)은 memory usage와 relocate 작업 사이의 균형을 맞춰 증가하게하는 여러 전략들을 가지고 있습니다.

 + 주의해야할 점은 vector는 크기가 일정하게 증가해야하며, 그로인해 일정한 시간복잡도가 제공되어야 한다는 것입니다.

 + 그래서 vector는 일반 배열보다 많은 메모리 용량을 잡아먹지만, 효율적으로 동적 성장하고 좋은 저장관리능력을 가지게 되는 것입니다.

 + 다른 Dynamic container와 비교하면, 마지막 요소를 빼고 넣는 능력은 뛰어나지만, 중간의 요소를 빼고 넣는건 뒤쳐집니다.

[사용해야하는 경우]

 + 저장할 데이터의 수가 가변적일 때

 + 중간에 데이터 삽입, 삭제가 적거나 없을 때

 + 저장된 요소를 자주 검색하지 않을 때

 + 랜덤 엑세스를 자주할 때

[method]

생성자
vector v	빈 vector 생성
vector v(n)	n개의 원소를 가지는 vector 생성
vector v(n,x)	n개의 x값을 원소로 가지는 vector 생성
vector v(v2)	v2를 복사한 vector 생성(복사 생성자 호출)
vector v(b,e)	v는 반복자 구간 [b.e)로 초기화된 원소를 갖는다.

멤버함수
v.assign(n,x)	v에 x값으로 n개의 원소를 할당한다.
v.assign(b,e)	v를 반복자 구간 [b,e)로 할당한다.
v.at(i)	v의 i번째 원소를 참조한다.
v.back()	v의 마지막 원소를 잠조한다.
p=v.begin()	p는 c의 첫 원소를 가리키는 반복자
p=v.cbegin()	p는 c의 첫 원소를 가리키는 상수 반복자
v.capacity()	x는 v에 할당된 공간의 크기
v.clear()	v의 모든 원소를 제거한다.
v.empty()	v가 비어있는지 확인한다.
v.end()	v의 끝을 표식하는 반복자를 반환
v.cend()	v의 끝을 표식하는 상수 반복자를 반환
q = v.erase(p)	p가 가르키는 원소를 제거한다. q는 다음 원소를 나타낸다.
q = v.erase(b,e)	반복자 구간 [b,e)의 모든 원소를 제거한다. q는 다음 원소
v.front()	v의 첫 번째 원소를 참조한다.
v.insert(p,x)	p가 가리키는 위치에 x를 삽입한다. 삽입한 원소를 가리키는 반복자를 반환
v.insert(p,n,x)	p가 가리키는 위치에 n개의 x값을 삽입한다.
v.insert(p,b,e)	p가 가리키는 위치에 반복자구간 [b,e)의 원소를 삽입한다.
v.max_size()	v가 담을 수 있는 최대 원소의 개수(메모리크기)
v.pop_back()	v의 마지막 원소를 제거한다.
v.push_back()	v의 끝에 x를 추가한다.
p = v.rbegin()	p는 v의 역 순차열의 첫 원소를 가리키는 반복자다.
p = v.crbegin()	p는 v의 역 순차열의 첫 원소를 가리키는 상수 반복자다.
p = v.rend()	p는 v의 역 순차열의 끝을 표식하는 반복자다.
p = v.crend()	p는 v의 역 순차열의 끝을 표식하는 상수 반복자다.
v.reserve(n)	n개의 원소를 저장할 공간을 예약한다.
v.resize(n)	v의 크기를 n으로 변경하고, 확장되는 공간의 값을 기본값으로 초기화한다.
v.resize(n,x)	v의 크기를 n으로 변경하고, 확장되는 공간의 값을 x값으로 초기화한다.
v.size()	v의 원소 갯수
v.swap(v2)	v와 v2를 swap한다.

멤버함수2
v.shrink_to_fit()	사용되지 않는 capacity size를 제거한다. 즉, size() == capacity()로 만든다.
v.emplace(i, value)	container 내부에서 value를 생성한 뒤, i(iterator)위치에 삽입한다. (복사생성자 실행x)
v.emplace_back(value)	container 내부에서 value를 생성한 뒤, vector 맨 뒤에 삽입한다. (복사생성자 실행x)
v.get_allocator()	vector의 allocator 객체를 반환한다.

// 소스코드 추가할 것~~~~~

[push_back vs emplace_back]

 + 두 함수를 비교하는 상황은 단순히 기존의 요소를 vector에 삽입하는 것이 아닌, 따로 생성하여 새로운 요소를 삽입하는 생성 삽입 할 경우입니다.

 + push_back은 전달받은 객체를 임의 복사하거나 이동시켜서 값을 복사합니다. 즉, 따로 추가 연산작업이 필요합니다.

void push_back(const T& value);

void push_back(T&& value);    // C++11

 + 하지만, emplace_back은 필요한 인자를 직접 parameter로 받아 내부에서 생성-삽입-소멸 하므로 따로 임시 객체가 생성되지 않습니다. 그래서 push_back보다 성능면에서 우수합니다.

list.emplace_back("홍길동", 23);

emplace_back > push_back

 + push_back으로 하여도 컴파일러 내부적으로 최적화 하기 때문에 emplace_back으로 하는 것과 별차이가 없을 수 있다. 

 + 그러나 모든 상황에서 emplace_back이 유리하다고 할 순 없습니다. push_back이 효율적일 수도 있습니다.

*** 참고해야할 점

 - 만약 입력될 원소의 갯수를 알 수 있다면, 미리 reserve를 사용하여 메모리를 할당해놓으면 효율적이다. 중간의 relocate작업 제거효과.

 - 벡터를 비울 때, clear보다 새로운 벡터와 swap하는게 더 확실히 비울 수 있다. 왜냐하면 clear를 하게되면 capacity는 그대로 남아있기 때문.

   ex) vector<int>().swap(v);

 - vector의 요소에 접근할 때, []보다 at을 이용하면 좋다. []는 범위 점검을 하지않으나, at은 범위 점검을 하여 벗어나면 out_of_range예외를 throw한다.

 - puch_back함수보다 emplace_back함수가 대체로 효율적이다.(무조건적인건 아님 반대로 push_back이 더 효율적일 때도 있음)

---

** 참고사이트 **

 - http://shaeod.tistory.com/630

 - http://hyeonstorage.tistory.com/324

 - http://en.cppreference.com/w/cpp/container/vector/emplace_back

 - https://msdn.microsoft.com/ko-kr/library/dd647620.aspx

Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.