[C++11] Standard Template Library: <vector> | 표준 템플릿 라이브러리: <vector>

Standard Template Library: <vector>

 

표준 템플릿 라이브러리: <vector>

 

 

 

- C++98에서 처음으로 고안된 STL로 제공하는 동적 배열을 관리할 때 사용하는 컨테이너이다.

 

- Homogeneous Container를 제공한다.
- Built-In Array 와 동일하게, 표준 배열 표기법을 사용할 수 있다.

 

- Built-In Array Type과 <array> Template은 원소들을 동일한 메모리 지역에 저장시키는데 반해,
  <vector> 는 원소들을 Heap에 저장시킨다.

- 내부적으로 <vector> 는 동적으로 할당된 Built-In Array를 사용하여 원소들을 저장하는데,
  capacity를 넘어서서 원소들을 저장하기 위해서는 새로운 배열 공간을 할당하며 Overhead가 발생되기에,
  원소가 추가된다 하더라도 그때마다 배열 공간을 재할당하지는 않는다.
- 즉, <vector> 는 실제 저장된 원소의 개수보다 더 큰 메모리 공간을 할당해놓을 수 있다.
- Capacity 의 크기는 Logarithmically 하게 증가된다.

- <vector>는 <array> 에 비해 스토리지를 효율적으로 관리하고, 동적으로 확장할 수 있게 하는 대신
  더 많은 메모리 공간을 사용한다.

 

- <deque>, <list>, <forward_list> 와 비교하여
  <vector> 는 원소에 효율적으로 Access 할 수 있고, 원소를 양 끝단에서 삽입/삭제하는데 비교적 효율적이다.
- 양 끝단이 아닌, 다른 위치에서 원소를 삽입/삭제하는 연산은 다른 컨테이너들 보다 비효율적이다.

* allocator Obejct (URL)
- 많은 STL Container Template에서는 효율적인 메모리 관리를 위해 <memory> Header의
  allocator Object를 상속받아 사용하고 있다.

 

 

 

vector Properties

 

- <vector> 는 아래와 같이 정의할 수 있다:

 

1. Sequence
   - Sequence Container에 저장된 원소들은 메모리 내부에 선형 순서를 유지하여 저장된다.
   - 각각의 원소들은 Sequence 내의 포지션(순서, 인덱스)으로 접근할 수 있다.
    
2. Dynamic array
   - 모든 원소에 대해 Direct Access 할 수 있다.
   - 포인터 연산과 Sequence의 양 끝단에서 빠른 삽입/제거 연산을 지원한다.
    
3. Alocator-aware
   - 메모리 공간을 동적으로 관리하기 위해 allocator 를 사용한다.

 

---

Vector Summary (Vector 요약)

 

 

Template parameters

 

• T
• Alloc

 

Member Types

 

• value_type
• allocator_type
• reference
• const_reference
• pointer
• const_pointer
• iterator
• const_iterator
• reverse_iterator
• const_reverse_iterator
• difference_type
• size_type

 

Member Functions : Constructors and Destructor

 

• Constructor
• Destructor
• operator=

 

Member Functions : Iterators

 

• begin
• end
• rbegin
• rend
• cbegin
• cend
• crbegin
• crend

 

Member Functions : Capacity

 

• size
• max_size
• resize
• capacity
• empty
• reserve
• shrink_to_fit

 

Member Functions : Element Access

 

• operator : [ ]
• at
• front
• back
• data

 

Member Functions : Modifiers

 

• assign
• push_back
• pop_back
• insert
• erase
• swap
• clear
• emplace
• emplace_back

 

Member Functions : Allocater

 

• get_allocator

 

Non-Member Function Overloads

 

• relational operators
• swap

 

Template Specializations

 

• vector<bool>

 

---

Template parameters

 

1. T

- 원소의 타입이다.

- 원소의 타입이 Move Constuctible 함이 보장되어야
  Reallocation 시 복사되지 않고 온전히 이동될 수 있다.
- T 는 vector::value_type 으로 Alisaing 되어 있다.

 

* std::is_nothrow_move_constructible (URL)

https://cplusplus.com/reference/type_traits/is_nothrow_move_constructible/

 

2. Alloc

- allocator Object의 타입으로, Storage Allocation Model을 정의하는데 사용된다.

- 기본적으로, 가장 간단한 Memory Allocation Model 이 적용되어 있고,
  Value-Independent 한 allocator Class Template 이 사용된다.

- Alloc 은 vector::allocator_type 으로 Aliasing 되어 있다.

 

---

Member Types

 

1. value_type

- 첫 번째 템플릿 파라미터이다. (T)

 

2. allocator_type

- 두 번째 템플릿 파라미터이다. (Alloc)

- defaults to: allocator<value_type>

 

3. reference

- allocator_type::reference

- for the default allocator: value_type&

 

4. const_reference

- allocator_type::const_reference

- for the default allocator: const value_type&

 

5. pointer

- allocator_type::pointer

- for the default allocator: value_type*

 

6. const_pointer

- allocator_type::const_pointer

- for the default allocator: const value_type*

 

7. iterator

- a random access iterator to value_type

- convertible to const_iterator

 

8. const_iterator

- a random access iterator to const value_type

 

9. reverse_iterator

- reverse_iterator<iterator>

 

10. const_reverse_iterator

- reverse_iterator<const_iterator>

 

11. difference_type (ptrdiff_t)

- a signed integral type, identical to:
  iterator_traits<iterator>::difference_type

- usually the same as ptrdiff_t

 

12. size_type (size_t)

- Unsigned Integral Type 으로, 다른 Non-Negative Value를 표현할 수 있는 다른 타입으로 대체될 수 있다.

 

---

Member Functions : Constructors and Destructor

 

1. Constructor: Default

explicit vector(const allocator_type& alloc = allocator_type());

// Example
std::vector<int> first; // empty vector of ints

- Complexity : Constant

 

 

 

2. Constructor: Fill

explicit vector(size_type n);
vector(size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

// Example
std::vector<int> second (4,100); // four ints with value 100

- Complexity : Linear (Size of container)

 

 

 

3. Constructor: Range

template <class InputIterator>
vector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

// Examples
std::vector<int> third (second.begin(),second.end()); // iterating through second

// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

- Complexity : Linear (Size of container)

 

 

 

4. Constructor: Copy

vector(const vector& x);
vector(const vector& x, const allocator_type& alloc);

// Example
std::vector<int> fourth (third); // a copy of third

- Complexity : Linear (Size of container)

 

 

 

5. Constructor : Move

vector(vector&& x);
vector(vector&& x, const allocator_type& alloc);

- Complexity : Constant

 

 

 

6. Constructor: Initializer List

vector(initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

- Complexity : Linear (Size of container)

 

 

 

7. Destructor

- 벡터에 저장된 원소들 각각에 대하여 allocator_traits::destroy 를 호출한다.

- vector 의 allocater 를 통해 Storage Capacity를 Deallocate 한다.

- Complexity : Linear in vector::size

 

 

 

8. Assignment Operator : =

// copy (1)	
vector& operator= (const vector& x);

// move (2)	
vector& operator= (vector&& x);

// initializer list (3)	
vector& operator= (initializer_list<value_type> il);

- Complexity : Linear (Size of container)

 

---

Member Functions : Iterators

 

1. begin

iterator begin() noexcept;
const_iterator begin() const noexcept;

- 첫 번째 원소를 Pointing 하는 iterator 를 리턴한다.

 

 

2. end

iterator end() noexcept;
const_iterator end() const noexcept;

- Return iterator to end

 

3. rbegin

reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;

- Return reverse iterator to reverse beginning

 

4. rend

reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;

- Return reverse iterator to reverse end

 

5. cbegin

const_iterator cbegin() const noexcept;

- Return const_iterator to beginning

 

6. cend

const_iterator cend() const noexcept;

- Return const_iterator to end

 

7. crbegin

const_reverse_iterator crbegin() const noexcept;

- Return const_reverse_iterator to reverse beginning

 

8. crend

const_reverse_iterator crend() const noexcept;

- Return const_reverse_iterator to reverse end

 

---

Member Functions : Capacity

 

1. size

size_type size() const noexcept;

- Return size

 

2. max_size

size_type max_size() const noexcept;

- Return maximum size

 

3. resize

void resize (size_type n);
void resize (size_type n, const value_type& val);

- Change size

 

4. capacity

size_type capacity() const noexcept;

- Return size of allocated storage capacity

 

5. empty

bool empty() const noexcept;

- Test whether vector is empty

 

6. reserve

void reserve (size_type n);

- Request a change in capacity

 

7. shrink_to_fit

void shrink_to_fit();

- Shrink to fit

 

---

Member Functions : Element Access

 

1. operator : [ ]

reference operator[] (size_type n);
const_reference operator[] (size_type n) const;

- Access element

 

2. at

reference at (size_type n);
const_reference at (size_type n) const;

- Access element

 

3. front

reference front();
const_reference front() const;

- Access first element

 

4. back

reference back();
const_reference back() const;

- Access last element

 

5. data

value_type* data() noexcept;
const value_type* data() const noexcept;

- Access data

 

---

Member Functions : Modifiers

 

1. assign

// range (1)	
template <class InputIterator>
void assign (InputIterator first, InputIterator last);

// fill (2)	
void assign (size_type n, const value_type& val);

// initializer list (3)	
void assign (initializer_list<value_type> il);

- Assign vector content

 

2. push_back

void push_back (const value_type& val);
void push_back (value_type&& val);

- Add element at the end

 

3. pop_back

void pop_back();

- Delete last element

 

4. insert

// single element (1)	
iterator insert (const_iterator position, const value_type& val);

// fill (2)	
iterator insert (const_iterator position, size_type n, const value_type& val);

// range (3)	
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);

// move (4)	
iterator insert (const_iterator position, value_type&& val);

// initializer list (5)	
iterator insert (const_iterator position, initializer_list<value_type> il);

- Insert elements

 

5. erase

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

- Erase elements

 

6. swap

void swap (vector& x);

- Swap content

 

7. clear

void clear() noexcept;

- Clear content

 

8. emplace

template <class... Args>
iterator emplace (const_iterator position, Args&&... args);

- Construct and insert element

 

9. emplace_back

template <class... Args>
void emplace_back (Args&&... args);

- Construct and insert element at the end

 

---

Member Functions : Allocater

 

1. get_allocator

allocator_type get_allocator() const noexcept;

- Get allocator

 

---

Non-Member Function Overloads

 

1. relational operators

template <class T, class Alloc>
bool operator== (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	
template <class T, class Alloc>
bool operator!= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	
template <class T, class Alloc>
bool operator<  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	
template <class T, class Alloc>
bool operator<= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	
template <class T, class Alloc>
bool operator>  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	
template <class T, class Alloc>
bool operator>= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

- Relational operators for vector

 

 

 

2. swap

template <class T, class Alloc>
void swap (vector<T,Alloc>& x, vector<T,Alloc>& y);

- Exchange contents of vectors

---

Template Specializations

 

1. vector<bool>

template < class T, class Alloc = allocator<T> >
class vector;
// generic templatetemplate <class Alloc> class vector<bool,Alloc>;

- Vector of bool 

 

---

Vector Iteration

 

- <vector> 를 순회하는데에는 아래와 같은 방법들이 있다:

 

• Use a for loop and operator[] (for 반복문과 인덱싱을 통한 순회)
• Use an iterator (iterator 를 통한 순회)
• User the auto keyword (auto 키워드를 통한 순회)

 

 

 

Use a for loop and operator[] (for 반복문과 인덱싱을 통한 순회)

 

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  //decleration of int vector
  vector<int> vec = {1, 2, 3, 4, 5};
  
  // returns length of vector as unsigned int
  unsigned int vecSize = vec.size();

  // run for loop from 0 to vecSize
  for(unsigned int i = 0; i < vecSize; i++)
  {
    cout << vec[i] << " ";
  }
  cout << endl;

  return 0;
}

 

 

vec.at(i); // vec[i] 와 동일

- operator[] 대신, at(i) 함수를 통해 인덱싱을 할 수 있으며,
  at(i) 은 i가 범위를 벗어난 값인 경우, out_of_range Exception을 throw 한다.

 

 

 

Use an iterator (iterator 를 통한 순회)

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  //decleration of int vector
  vector<int> vec = {1, 2, 3, 4, 5};
  int vecSize = vec.size(); // returns length of vector

  //decleration of vector iterator
  vector<int>::iterator iter = vec.begin();

  cout << "Vector: ";
 
  // run for loop from 0 to vecSize
  for(iter; iter < vec.end(); iter++)
  {
    // access value in the memory to which the pointer
    // is referencing
    cout << *iter << " ";
  }
  cout << endl;

  return 0;
}

 

 

 

User the auto keyword (auto 키워드를 통한 순회)

#include <iostream>
#include <vector>
using namespace std;

int main() {
  //decleration of int vector
  vector<int> vec = {1, 2, 3, 4, 5};
  int vecSize = vec.size(); // returns length of vector

  cout << "Vector: ";

  for (auto & element : vec) 
  {
    cout << element << " ";
  }
  return 0;
}

 

---

Reference: Stephen Prata, C++ Primer Plus 6E, Pearson, 2012

 

Reference: cplusplus.com, Reference : <vector>, URL, 2023년 4월 10일 검색

 

Reference: educative, How to iterate through a vector in C++, URL, 2023년 6월 12일 검색