https://cplusplus.com/reference/vector/vector/?kw=vector

template < class T, class Alloc = allocator<T> > class vector;

Description

• Vectors are sequence containers representing arrays that can change in size.
  
  👉 vector는 사이즈를 바꿀 수 있는 배열을 나타내는 sequence 컨테이너

• Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.
  
  👉 배열처럼 인접한 storage location을 사용함. 따라서 element는 일반적인 포인터 offset으로도 액세스 할 수 있음. 배열과 다른 점은 동적으로 사이즈를 바꿀 수 있다는 것. 사이즈는 컨테이너 자체에서 자동으로 다룸.

• Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.
  
  👉 vector는 재할당 될 수 있음. 이는 메모리를 새로 할당하고 기존의 원소를 새 배열에 모두 이동시키는 것을 뜻함. 비용이 많이 드는 작업이기 때문에 원소 추가할 때마다 매번 벡터를 재할당하진 않음.

• Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size).

• Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity.
  
  👉 벡터 재할당 방법은 libraries 전략에 따라 다를 수 있음 but 크기가 대수적으로 증가하는 간격에서만 재할당이 이뤄져야 함. 일정한 시간복잡도를 제공 할 수 있어야 함.

Member types

• https://cplusplus.com/reference/vector/vector/?kw=vector
  

Member functions

OCCF

constructor

• https://cplusplus.com/reference/vector/vector/vector/
• constructor에서 동적할당 일어나야 함
• https://cplusplus.com/reference/memory/allocator/construct/
• 동적할당 후 벡터 원소를 채우는 건 _allocator.construct 로 해줘야 함. 원소 value_type이 템플릿 타입이기 때문에 단순 int, char 등의 타입으로 생각하면 안 됨. 객체로 생각하고 접근. std::allocator.construct가 객체 생성하는 역할.
• vector(size_type n, const value_type &val)과 vector(InputIterator first, InputIterator last) 사이의 오버로딩을 명확하게 해주기 위해 enable_if가 필요하다.
• https://modoocode.com/255
• type_traits.hpp에서 enable_if와 is_iterator를 구현해주고 이를 이용하여 InputIterator가 올바른 이터레이터인 경우에만 range constructor로 오버로딩 되게 한다.

template < class InputIterator >
  vector(
    typename ft::enable_if < ft::is_iterator < InputIterator > ::value, InputIterator > ::type first,
    InputIterator last,
    const allocator_type & alloc = allocator_type()): _allocator(alloc), _capacity(last - first), _size(last - first) {
    _data = _allocator.allocate(_capacity);
    for (InputIterator it = first; it != last; it++)
      *(_data++) = *it;
  } // range

destructor

• constructor에서 동적할당 해줬기 때문에 메모리 해제해줘야 함

operator=

• https://cplusplus.com/reference/vector/vector/operator=/
• 걍 대입연산자 오버로딩.

Iterators

begin

• https://cplusplus.com/reference/vector/vector/begin/
• 벡터의 첫 번째 요소 가리키는 iterator 반환.
• iterator, const_iterator 버전 두 개

end

• https://cplusplus.com/reference/vector/vector/end/
• 벡터의 마지막 요소 가리키는 iterator 반환.
• iterator, const_iterator 버전 두 개

rbegin

• https://cplusplus.com/reference/vector/vector/rbegin/
• 벡터 마지막 요소 가리키는 reverse_iterator 반환.
• reverse_iterator, reverse_const_iterator 버전 두 개
• reverse_iterator(end()) 으로 initialization constructor 사용해주면 될 듯

rend

• https://cplusplus.com/reference/vector/vector/rend/
• 벡터 첫 번째 요소 가리키는 reverse_iterator 반환.
• reverse_iterator, reverse_const_iterator 버전 두 개
• reverse_iterator(begin()) 으로 initialization constructor 사용해주면 될 듯

cbegin

• https://cplusplus.com/reference/vector/vector/cbegin/
• c++11 함수 구현 X
• 반환 타입이 const_iterator인 begin.
• 그럼 왜 begin에서도 const_iterator 반환인 경우를 오버로딩 했나? -> https://stackoverflow.com/questions/31208640/what-is-the-difference-between-cbegin-and-begin-for-vector

cend

• https://cplusplus.com/reference/vector/vector/cend/
• c++11 함수 구현 X

Capacity

size

• https://cplusplus.com/reference/vector/vector/size/
• 현재 벡터에 저장된 원소 개수 반환

max_size

• https://cplusplus.com/reference/vector/vector/max_size/
• 할당가능한 벡터 최대 사이즈 반환
• std::allocator에 max_size 함수 있음. 그거 사용
• 대신 PTRDIFF_MAX를 초과할 수는 없음. _allocator.max_size()가 PTRDIFF_MAX 보다 커도 PTRDIFF_MAX를 반환.
• https://cplusplus.com/reference/memory/allocator/max_size/
• !! https://stackoverflow.com/questions/28516686/does-max-size-of-stdvectorchar-have-a-bug &
  https://gcc.gnu.org/ml/gcc/2011-08/msg00221.html
• ex) 64비트 운영체제라면 char형은 2^64 - 1 만큼 할당할 수 있어야 하지만, 그렇게 할당해버리면 end - begin이 ptrdiff_t의 범위를 초과하게 됨. 그렇기 때문에 애초에 std::vector에서는 ptrdiff_t가 감당할 수 있는 범위로 제한하고 있는듯.

resize

• https://cplusplus.com/reference/vector/vector/resize/
• n개의 요소를 포함하도록 컨테이너의 크기를 조정합니다.
• n이 current size보다 작으면, 넘치는 부분을 destroy.
• n이 현재 컨테이너 크기보다 크면 n 크기에 도달하는 데 필요한 만큼의 요소를 끝에 삽입하여 콘텐츠를 확장합니다.
• n이 현재 컨테이너 용량보다 크면 할당된 저장 공간이 자동으로 재할당됩니다.

capacity

• https://cplusplus.com/reference/vector/vector/capacity/
• 벡터에 할당된 사이즈 반환

empty

• https://cplusplus.com/reference/vector/vector/empty/
• Test whether vector is empty

reserve

• https://cplusplus.com/reference/vector/vector/reserve/
• 매개변수 n이 vector capacity 보다 크면 n혹은 n보다 크게 벡터를 재할당 해서 원소 이전.
• 재할당할 때 2배씩 capacity를 키워준다고 함.
• 테스트해보니 이전 _capacity * 2 한 값보다 n이 크면 그 n으로 하고 아니면 _capacity * 2로 할당해주는 듯.
• 이전 하고 나면 기존의 iterator들과 reference들은 invalid 해지기 때문에 주의해야함
• 요청된 크기가 최대 크기(vector::max_size)보다 크면 length_error 예외가 발생. & 재할당의 경우 컨테이너의 할당자를 사용하여 스토리지가 할당되며, 실패 시 예외가 발생할 수 있음(기본 할당자의 경우 할당 요청이 성공하지 않으면 bad_alloc이 throw됨).
  => std::allocator에서 알아서 throw 됨

Element access

oprator[]

• https://cplusplus.com/reference/vector/vector/operator[]/
• 걍 _data[] 반환 해주면 됨

at

• https://cplusplus.com/reference/vector/vector/at/
• n이 _size보다 크면 out_of_range 에러 throw.
• 범위를 확인하지 않는 []와 대조된다.

front

• https://cplusplus.com/reference/vector/vector/front/
• 벡터의 첫 번째 원소 레퍼런스를 반환.
• iterator를 반환하는 begin과 대조된다.
• 빈 컨테이너에서 이 함수를 호출하면 정의되지 않은 동작이 발생한다.
• 할당하지 않은 상태에서 레퍼런스 반환 해서 그런듯? 함수 내에서 예외처리 해주지 않고 무조건 첫 번째 원소 레퍼런스 반환하게 하면 됨.

back

• https://cplusplus.com/reference/vector/vector/back/
• 벡터의 마지막 원소 레퍼런스 반환.
• iterator를 반환하는 end와 대조된다.
• 이것도 빈 컨테이너일 때 정의되지 않은 동작 발생

Modifiers

assign

• https://cplusplus.com/reference/vector/vector/assign/
• 벡터에 새 내용을 할당하고 현재 내용을 바꾸고 그에 따라 크기를 수정한다.

push_back

• https://cplusplus.com/reference/vector/vector/push_back/
• 현재 마지막 요소 다음에 벡터의 끝에 새 요소를 추가합니다. val의 내용이 새 요소로 복사(또는 이동)됩니다.
• 이렇게 하면 컨테이너 크기가 1씩 증가하여 새 벡터 크기가 현재 벡터 용량을 초과하는 경우에만 할당된 저장 공간이 자동으로 재할당됩니다.

pop_back

• https://cplusplus.com/reference/vector/vector/pop_back/
• 벡터의 마지막 요소를 제거하여 컨테이너 크기를 1로 효과적으로 줄입니다.
• 반환하는 원소 없음. 걍 지우는 거. 마지막 원소 destory한 다음 size 줄이면 될 듯.
• 원소 0일 때 따로 처리 안 해줌. 원래 std vector도 그럼.

insert

• https://cplusplus.com/reference/vector/vector/insert/
• 이건 인자로 받은 positoin 앞에 삽입하는 거
• 벡터는 배열을 사용하기 때문에 insert하면 position 뒤의 인덱스를 다 한 칸씩 뒤로 미뤄줘야 함.
• 다른 list 기반에 비해 비효율적.

erase

• https://cplusplus.com/reference/vector/vector/erase/
• 범위 혹은 position에 있는 원소 destroy.
• erase한 범위 다음에 있던 원소를 가리키는 iterator반환.
• first부터 last까지 지우고 뒤에 있는 거 first쪽으로 땡겨오니까 결국 first 반환해주면 됨.

swap

• https://cplusplus.com/reference/vector/vector/swap/
• 두 벡터 교환. a <-> b
• 이전에 = assignmanet를 구현해놨기 때문에 걍 원래 스왑 할 때 쓰는 tmp = x; x = *this; *this = tmp; 쓰면 됨 -->!!! ㄴㄴ 이러면 불필요한 해제 일어나게 됨. 걍 각 변수마다 ft::swap 써서 변수끼리 서로 교환할 수 있도록 해줘야 함

clear

• https://cplusplus.com/reference/vector/vector/clear/
• 현재 있는 원소 다 destroy 하고 사이즈 0으로 바꾸는 것

할당 함수 비교

함수명	content change	size change	capacity change
reserve	기존 컨텐츠 안 건들임	size 안 바꿈	capacity만 바꿈
resize	기존 컨텐츠 안 건들임. but 바꾸려는 사이즈가 현재 컨텐츠 사이즈보다 더 크면 나머지 부분은 새로운 값으로 채울 수 있음	size 바꿈	capacity 바꿈
assign	기존 컨텐츠 건들임. 아예 싹 바꾸는 거	size 바꿈	capacity 바꿈

Allocator

get_allocator

• https://cplusplus.com/reference/vector/vector/get_allocator/
• 걍 지금 벡터의 allocator 사본 반환하면 됨

Non-member function overloads

relational operators

• https://cplusplus.com/reference/vector/vector/operators/
• 벡터 컨테이너 lhs와 rhs 간에 적절한 비교 작업을 수행.

operator==

• 같음 비교(operator==)는 먼저 크기를 비교하여 수행하고, 일치하면 operator==를 사용하여 요소를 순차적으로 비교하고 첫 번째 불일치에서 중지합니다(같은 알고리즘을 사용하는 것처럼).
• algorithm header에 있는 equal을 namespace ft로 하나 더 만들어줘서 사용
• https://cplusplus.com/reference/algorithm/equal/?kw=equal

operator!=

• 만들어둔 == 사용해서 !(lhs == rhs) 해주면 됨

operator<

• 보다 작음 비교(operator<)는 lexicographical_compare 알고리즘을 사용하는 것처럼 작동합니다. 이 알고리즘은 operator<를 사용하여 요소를 순차적으로 비교합니다(즉, a<b 및 b<a 모두 확인).
• algorithm 헤더에 있는 lexicographical_compare namespace ft로 하나 더 만들어줘서 사용
• https://cplusplus.com/reference/algorithm/lexicographical_compare/

operator<=

• 구현해뒀던 operator< 사용
• !(rhs < lhs) lhs <= rhs랑 똑같음

operator>

• 구현해뒀던 operator< 사용
• (rhs < lhs)

operator>=

• 구현해뒀던 operator< 사용
• !(lhs < rhs) rhs <= lhs 랑 똑같음

swap

• https://cplusplus.com/reference/vector/vector/swap-free/
• x.swap(y)가 호출된 것처럼 동작합니다.

끝~~