[ft_containers] vector

자료구조 vector의 원형

vector라는 자료구조 자체는 이미 워낙에 많이 쓰던 녀석이니, 완벽한 재구현을 위해 원형을 분석.

물론 지금은 C++98에 해당하는 녀석들로만.

 

생성자(constructor)

1. vector();
2. vector(const vector& other);
3. explicit vector(const Allocator& alloc);
4. explicit vector(size_type count, const T& value = T(), const Allocator& alloc = Allocator());
5. template<typename InputIt> vector(InputIt first, InputIt last, const Allocator& alloc = Allocator());

1: 기본 생성자. 빈 vector를 기본 생성된 allocator로 생성.

2: 복사 생성자. 원본의 값 요소들을 사용해 vector를 초기화.

3: 주어진 Allocator를 사용해 vector를 생성.

4: value 값을 count개 만큼 채워서 생성.

5: 범위의 내용을 사용해서 vector를 생성.

alloc	vector의 모든 메모리 할당에 사용되는 allocator
count	vector의 초기 크기
value	vector의 요소를 초기화 할 값
first, last	초기 요소를 복사해 올 범위
other	vector의 초기 요소들을 초기화 할 때 원본으로 사용할 다른 vector

 

교체 (replacements)

1. void assign(size_type count, const T& value);
2. template<typename InputIt> void assign(InputIt first, InputIt last);

자료구조의 내용을 교체(대체; replacement). 

요소의 개수 역시 늘어나거나 줄어들 수 있음.

 

접근 (accessors)

1. reference at(size_type pos);
2. const_reference at(size_type pos) const;
3. reference operator[](size_type pos);
4. const_reference operator[](size_type pos) const;
5. reference front();
6. const_refence front() const;
7. reference back();
8. const_refence back() const;
9. T* data();
10. const T* data() const;

해당 위치에 있는 요소의 레퍼런스를 반환.

가능한 범위를 초과하는 pos일 경우, std::out_of_range 예외 발생.

 

주의 사항으로, 3, 4의 인덱스 연산자([])의 경우, 새로운 요소를 만들 수 없음.

다시 말해, 이미 있는 요소에 대해서만 값 변경이 가능함. (std::map과 다른 부분.)

 

front, back은 요소의 맨 앞 또는 뒤의 레퍼런스를 반환.

front는, *c.begin()와 동일하며, 비어있지 않은 자료구조에 대하여 back은, *std::prev(c.end()) 와 동일.

 

data는, 자료구조 밑에 숨겨진 실제 요소 저장(예를 들면 배열?) 스토리지의 포인터를 반환함.

size()가 0이면, 다시 말해 자료구조가 비어있으면 data()는 NULL포인터를 리턴할 수도, 안 할 수도 있음.

 

반복자 (iterators)

1. iterator begin();
2. const_iterator begin() const;
3. iterator end();
4. const_iterator end() const;
5. reverse_iterator rbegin();
6. const_reverse_iterator rbegin() const;

 

크기 (capacities)

1. bool empty() const;
2. size_type size() const;
3. size_type max_size() const;
4. void reserve(size_type new_cap);
5. size_type capacity() const;

empty()는 현재 vector가 비어있는지 여부를 반환.

begin() == end() 인지 여부를 반환하는 것으로 확인 가능.

 

size()는 현재 vector에 요소가 몇개 들어있는지 여부를 반환.

std::distance(begin(), end()) 로 확인 가능.

 

max_size()는 allocator의 max_size() 함수를 활용해서,

Allocator::max_size() 함수를 활용 가능.

 

reserve()는 현재 vector의 저장공간을 new_cap 크기로 변경.

new_cap이 현재 capacity() 보다 클 경우, 새로운 스토리지가 할당됨.

그렇지 않을 경우에는, 아무 것도 하지 않음.

max_size() < new_cap 일 경우, std::length_error 예외 발생. 또는 Allocator에서 나올 수 있는 예외.

 

capacity()는 현재 vector의 최대 용량을 반환함.

수정자 (modifiers)

1. void clear();
2. iterator insert(iterator pos, const T& value);
3. void insert(iterator pos, size_type count, const T& value);
4. template<class InputIt> void insert(iterator pos, InputIt first, InputIt last);
5. iterator erase(iterator pos);
6. iterator erase(iterator first, iterator last);
7. void push_back(const T& value);
8. void pop_back();
9. void resize(size_type count);
10. void resize(size_type count, T value = T());
11. void swap(vector& other);

1. vector에서 모든 요소를 삭제함.

  * 실행 후, size()는 0이 되며, end() 이전의 모든 반복자, 포인터 들은 무효화 됨.

 

2. 은 pos 앞에 value 값을 삽입하고, 삽입된 값의 iterator를 반환.

   * pos는 end()일 수 있음.

 

3. 은 value의 count 개수 만큼의 사본을 pos 앞에 삽입.

 

4. first 부터 last 범위의 요소에 대해 pos 이전에 값을 삽입.

  * 타입이 정수 타입(Integral Type)일 경우, 3.과 동일한 오버로드 형태로 동작함.

  * first, last가 *this의 iterator일 경우에는 정의되지 않은 동작임.

 

5. 는 pos가 삭제될 데이터임.

  * pos는 유효해야하며, 간접참조(* 연산자) 가능해야 함. (예를 들어, end()는 유효하지만 간접참조 불가능하기에 사용 불가.)

  * pos가 마지막 요소일 경우, end()가 반환됨.

 

6. 는 삭제할 범위의 first 반복자 ~ last 반복자.

  * first는 딱히 간접참조 가능할 필요 없음. (end()일 수도 있음. 아무 일도 일어나지 않겠지만..)

  * 제거 전에 last==end() 라면, 새로운 end()가 반환됨.

  * [first, last]가 비어있는 범위라면, last가 반환됨.

 

- insert할 경우, 새로운 size()가 기존 capacity()보다 클 경우, 저장 공간이 재할당되며, 기존 iterator은 모두 무효화(invalidated)됨.

 

7. 은 value를 복제(copy)하여 vector의 끝에 삽입. (insert와 동일하게 반복자 무효화 발생.)

  * 일부 구현에서, reverse(size() + 1)에 실패하여 std::length_error 발생 가능.

 

8. 은 마지막 요소를 제거. 빈 vector에 대한 pop_back의 동작은 정의되지 않음. 마지막 요소 및 end()에 대한 반복자와 포인터는 무효화.

 

9. 은 count 개수 만큼 vector의 크기를 재설정.

  - count가 size()보다 작을 경우, vector가 count개수로 크기가 줄어듦.

  - count가 size()보다 클 경우, 모자란 크기만큼 공간을 늘리며, 기본 초기화된 T로 새로운 공간들이 채워짐.

 

10. 은 상대 vector와 내용을 교환함.

  * 이 작업은 각 요소에 대하여 copy, swap을 수행하지 않음.

 

 

 

 

 

 

참조

https://en.cppreference.com/w/cpp/container/vector/vector

https://dydtjr1128.github.io/cpp/2019/07/13/Cpp-explicit-keyowrd.html