Array는 가장 기본적인 자료구조이다.

1. 장점 및 특징

논리적 저장 순서 == 물리적 저장 순서 가 특징이다. 따라서 index로 원소(element)에 접근할 수 있다. 따라서 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access가 가능하다는 장점이있다.

2. 단점

하지만 삭제, 삽입을 할 때는 해당 원소에 접근한 뒤(O(1)) 추가적으로 작업을 해줘야 하기 때문에 시간이 더 걸린다. 만약 배열의 원소 중 어떤 원소를 삭제했다고 하면, 배열의 연속적인 특징이 깨진다. 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 왼쪽으로(낮은 인덱스 값으로) shift 해줘야 하는 비용(cost)이 발생한다. 이 경우 시간 복잡도는 O(n)이 된다. 따라서 Array 자료구조에서 삭제 기능에 대한 time complexity의 worst case는 O(n)이 된다.

삽입도 마찬가지인데, 얘도 예를 들어 첫 번째 자리에 새로운 원소를 추가하면 그 뒤에 있는 모든 원소들의 인덱스를 큰 값으로 1씩 shift 해줘야 하므로 이 경우도 O(n)의 시간이 걸린다.

시간복잡도

배열 연산의 시간복잡도를 계산하면 다음과 같다.

1. 검색 : O(1) - 주소 값을 모르더라도 인덱스로 바로 접근할 수 있다.
2. 갱신 : O(1)
3. 삽입 : O(n)
4. 삭제 : O(n)

c++에서의 array

array에는

1. 고정 배열(fixed array) / 정적 배열
2. 동적 배열(dynamic array)

가 있다. 이 두 배열 모두 C++에 내장되어 있지만, 포인터로 형변환이 되었을 때 배열 길이 정보가 손실되고, 동적 배열은 지저분한 할당 해제 문제가 있다.

이런 문제를 해결하기 위해 C++ 표준라이브러리에서는 배열 관리를 쉽게 해주는 std::array와 std::vector가 있다.

std::array

std:array는 함수에 전달할 때 포인터로 형 변환되지 않는 고정 길이 배열이다. std::array는 <array> 헤더의 std 네임 스페이스 내부에 정의되어 있다.

변수 선언은 다음과 같이 하면 된다.

#include <array>

std::array<int, 3> arr; //길이 3짜리의 정수형 배열 선언

정적 배열 선언처럼 array의 길이는 컴파일 타임에 설정해야 한다. std::array는 초기화 리스트(initializer list) 또는 유니폼 초기화(uniform initialization)을 사용해서 초기화 할 수 있다.

std::array<int, 5> arr = {1,2,3,4}; //초기화 리스트
std::array<int, 5> arr1 {1,2,3,4}; //유니폼 초기화

내장된 고정 배열과 다르게, std::array에서는 배열 길이를 생략할 수 없다.

std::array<int, > arr {1,2,3,4} // 불가

초기화 리스트를 사용해서 배열에 값을 할당할 수 있다.

std::array<int, 5> arr;
arr = {1,2,3,4,5} //ok
arr = {1,2,3} // 4, 5번째 원소는 0이 될 것이다.
arr = {1,2,3,4,5,6} // 원소의 개수가 담을 수 있는 원소의 개수보다 많기 때문에 안된다.

일반 배열처럼 첨자 연산자([])를 사용해서 배열의 요소 값에 접근할 수 있다.

std::cout << arr[1];
arr[2] = 6;

또한 첨자 연산자는 유효 범위 검사를 하지 않으므로 잘못된 index가 주어지면 나쁜 일이 발생한다. 하지만 std::array는 유효 범위 검사를 수행하는 배열 요소에 접근하는 방법 at() 함수를 지원한다.

std::array<int, 5> arr {1,2,3,4,5};
arr.at(1) = 6;
arr.at(7) = 10; // throws error

array.at(9)를 호출하면 9는 배열의 범위를 벗어나는 인덱스 값으로 검사되어 array.at(9)는 실패한다. 이때 참조를 반환하는 대신 예외를 throw한다. (std::out_of_range)

at()함수는 유효 범위 검사를 하므로 operator[] 보다는 느리지만, 안전하다.

Size와 sorting

size()함수를 사용해서 배열의 길이를 알 수 있다.

std::array<double, 5> arr {1.0, 7.2, 4.5, 1.2, 1.9};
std::cout << "length: " << arr.size();

참고로 일반적인 정적 배열을 선언하고 나서 이 배열의 길이를 구하는 법은 c++에서는

int arr[] = new int[5];
int size = sizeof(arr) / sizeof(arr[0]) //4byte * 5 / 4byte = 5

c#에서는

int arr[] = new int[5];
int size = arr.Length;

참고로 자바에서 배열 길이는 arr.length로, 문자열의 길이는 str.length()였다.

std::array는 함수에 전달될 때 포인터로 형 변환이 되지 않기 때문에 size()함수는 함수 내에서 호출하더라도 정상적으로 작동한다.

#include <iostream>
#include <array>

void printLength(const std::array<double, 5>& arr) {
  std::cout << "length: " << arr.size(); 
}

int main() {
  std::array<double, 5> arr {1.0, 1.2, 1.4, 1.6, 1.8};
  
  printLength(arr);
  
  return 0;
}

표준 라이브러리에서 “size”라는 용어는 배열 길이를 의미하기 때문에 sizeof() 와 혼동하기 쉽다. (sizeof()의 결과는 배열 요소 자료형의 크기 * 배열 길이이다.)

위의 예제에서 printLength() 함수에서는 매개 변수로 std::array를 참조형(reference)로 받고 있다. 이는 std::array가 함수로 전달될 때 (성능상의 이유)로 컴파일러가 배열의 복사본을 만드는 것을 방지하기 위해서이다. 따라서 std::array는 무조건 참조로 전달해야 한다.

std::array의 길이는 알려져 이기 때문에 range-base for 루프와 함께 사용할 수 있다.

std::array<int, 5> arr {1,2,3,4,5};

for (auto &element : arr) {
  std::cout << element << '';
}

<algorithm>헤더에 있는 std::sort를 사용해서 std::array를 정렬할 수 있다.

#include <iostream>
#include <array>
#include <algorithm>

int main() {
  std::array<int, 5> arr {1,2,3,4,5};
  std::sort(arr.begin(), arr.end());
}

이 sort() 함수는 이터레이터(iterator)를 사용한다.