C++ STL [array]

→ 정의 : 같은 타입의 원소를 고정적이고, 연속적인 메모리에 관리하는 STL컨테이너.

→ 구성 : <array>의 array 클래스를 보면, 내부 멤버 변수로 T Elem[Size]로 되어있는 걸 볼 수 있다.(template<typename T, size_t Size> 로 타입과 배열 크기 결정) 즉, array는 C스타일의 배열을 한 번 감싼 Wrapper 클래스인 것이다. C스타일에서 배열을 선언할 때, 포인터로 암시적 변환되어 크기 정보 유실같은 불편함들이 있다. array는 이를 해결해주는 여러 가지의 interface를 제공한다.

→ 특성 : 크기가 고정된 메모리 공간에 데이터를 저장하므로 ‘재할당’이란 개념이 없다. 즉, 한 번 할당 받게 되면, 메모리 공간을 늘리거나 줄일 수 없다. 그렇기에 이것을 ‘고정 크기 배열‘이라 부른다.

→ 메모리 할당 : STL의 동적 컨테이너(vector, deque 등)는 컨테이너 객체랑 원소 공간이 분리되어 있는 경우가 많다. 예를 들어, STL vector는 객체 내부에 3개의 포인터로 이뤄져 있는데, 이 포인터들은 vector선언 위치에 따르고, 원소는 힙 영역에 생성이 된다. 하지만 array는 객체 내부에서 배열 자체를 포함하다 보니, 객체랑 원소가 같은 영역에 위치하게 된다. 즉, array의 할당 방식은 지역 변수라면 스택에, 멤버 변수는 객체가 할당된 영역에 위치하게 된다.

※ 생성자 (+초기화)

#include <array>
// 기본 생성자
std::array<int, 5> arr;  // { 쓰레기 값, 쓰레기 값, 쓰레기 값 ...}
std::array<int, 5> arr = { 1, 2, 3, 4, 5 };
std::array<int, 5> arr{1, 2, 3, 4, 5}; // since C++11 (유니폼 초기화)
std::array<int, 5> arr = {};     // 전부 0으로 초기화
std::array<int, 5> arr = { 0 };  // 전부 0으로 초기화
std::array<int, 5> arr = {1, 2, 3};  // { 1, 2, 3, 0, 0 }

// 복사 생성자
std::array<int, 5> Copy = {1, 2, 3};
std::array<int, 5> arr(Copy); // ~ 각 원소 복사

// 이동 생성자
std::array<int, 5> moved(std::move(Copy)); // ~ 이동 연산

// C++20 to_array
int CArray[] = { 10, 20, 30, 40, 50 };
std::array<int, 5> arr = std::to_array(CArray); 
// C스타일 배열에서 std:array로 변환 가능. auto로 추론도 가능.

@ 이동 생성자 - move 주의 → array의 이동 연산은 O(N) 시간 복잡도 인데, O(1)인 vector와의 차이가 있다. vector는 포인터를 변경해서 소유권만 넘겨주면 되므로 O(1) 시간 복잡도이다. 하지만 array는 배열 자체가 내부 데이터로 존재하기 때문에, 소유권을 넘길 수가 없어 원소를 개별적으로 한 개씩 옮겨야 한다. 이 과정으로 인해 O(N) 시간 복잡도를 가진다.

---

Method

※ 접근자

• ref at(size_type pos) - 특정 원소 접근/수정, pos의 범위 검사를 포함하는 접근자.
• ref operator[size_type pos] - 특정 원소 접근/수정.
• ref front() / back() - 제일 처음/끝 원소 접근/수정
• T* data() - array의 메모리 블럭 반환. 즉, 첫 번째 요소의 포인터 반환.

※ 반복자

• iterator begin() / cbegin() / end() / cend() - array의 시작 / 끝 iterator 반환 (begin & end - iterator // cbegin & cend - const_iterator)
• iterator rbegin / rend / crbegin / crend - r이 붙으면 역전된(reverse) iterator 반환. (시작 = array의 끝 원소, 끝 = array의 시작 원소)

※ 용량 확인

• bool empty() - 원소가 비어있는지 확인. ( 원소가 없다면 true )
• size_type size() - 현재 원소의 갯수 확인.

※ 부가 기능

• fill(const T& _value) - 배열의 모든 원소를 _value로 채워 넣음. 순회하면서 대입하는 방식으로 O(N) 시간 복잡도.
• swap(array& other) - 다른 array와 원소를 교환. 순회하면서 swap하는 방식으로 O(N) 시간 복잡도.

※ 외부 기능

• to_array(ARR) - C스타일 배열의 각 원소를 복사/이동하여 array를 생성하므로 O(N) 시간 복잡도.

---

vector & array 성능 비교

→ array는 필요없다? : vector는 원소를 계속 저장할 수 있고, 메모리 공간을 가변적으로 조절이 가능하다는 강력한 장점을 가지고 있다. array는 넣을 수 있는 원소 수가 제한되어 있기도 하고, 메모리 공간이 불변하기에, 연속적인 메모리를 다루기 위해선, 아마 vector를 많이 선택할 것이다. 하지만, 최적화를 고민해본다면, 경우에 따라 array를 사용하는 것도 좋은 선택이 될 수 있다.

→ 메모리 할당 비용 : 위에서 언급했듯이, STL의 동적 컨테이너는 컨테이너와 원소의 메모리 영역이 분리되어 있는 경우가 많다. 보통 본체는 스택 영역, 원소는 힙 영역. 그렇기 때문에, ‘처음 vector를 만드는 생성자 부분(초기에 크기를 확보하는 경우)’, ‘새로운 동적 메모리를 할당하는 부분’. 에서 오버헤드가 발생한다. 반면에 array는 할당된 영역에서 모든 것을 처리한다. 또한 ‘재할당’이란 개념도 없어, 메모리 할당에서 오버헤드가 발생하는 경우가 대게 없다고 봐도 무방하다.

→ 컴파일러 최적화 : array는 컴파일 타임 시점에 크기가 결정되고, vector는 런타임 시점에 결정된다. 그렇기 때문에, array는 이후에 컴파일러에게 더 많은 정보를 주어, 컴파일 타임에 판단하거나 최적화할 수 있는 기회를 더 많이 제공할 수 있기에, 런타임의 오버헤드를 줄일 수 있게 된다. vector도 C++20에서 컴파일 타임에 평가를 할 수 있게 개선이 되었지만, 컴파일러에 제공하는 정보는 아직 array가 우위라고 할 수 있다.

→ 상황에 따른 선택 : array를 사용하는 경우는 주로 지역 변수거나 클래스의 멤버 변수일 것이다. 지역 변수는 스택 영역에 저장되는데, 이때 알아둬야 하는 점은, 기본적으로 컴퓨터는 스택 영역이 크지 않다는 것이다. (OS에 종속적, Windows는 일반적으로 1MB) 반면에 힙 영역은 일반적으로 스택보다 훨씬 크다. 그렇기에 array를 쓴다면, 지역 변수 인 경우와, 멤버 변수인 경우를 나누어 데이터 크기와 저장 위치를 생각해볼 필요가 있다. 본인은 밑과 같이 생각한다.

1. array가 지역 변수 → 일반적으로 스택 영역.
   1. 최대 원소 갯수가 컴파일 타임에 정해질 수 있는가? →
      1. 가능한 경우 : array가 효율적이지만, 데이터 량(원소 갯수 * 원소 크기)이 매우 크다면 vector가 안전. (또는, array 자체를 힙 영역에 할당.)
      2. 불가능한 경우 : 일반적으로 vector가 적합하지만, 원소 갯수의 최대와 최소를 예측할 수 있고, 그 오차가 너무 크지 않은 경우. (+ 데이터 량 고려) array가 낭비는 조금 있지만, 동적 할당/재할당을 피하면서 효율을 챙길 수 있음.
2. array가 동적 할당 된 객체의 멤버 변수 → 일반적으로 힙 영역.
   1. 최대 원소 갯수가 컴파일 타임에 정해질 수 있다면, array가 적합하지만, array는 데이터 량이 곧 객체의 크기가 되므로, 객체의 복사나 이동도 한 번 고려해야 한다.
   2. 원소 갯수의 최대와 최소를 예측할 수 있고, 그 오차가 너무 크지 않은 경우. array가 효율적이고, 오차가 크다면, vector가 더 적합하다. (효율성을 계산할 필요가 있다.)