[Rust 자료구조] 배열(Vec<T>)

본 글은 Vec를 공부하며 작성한 글입니다. 오역 및 오류가 있을 수 있습니다. 이에 대해서는 댓글로 남겨주시면 감사하겠습니다.
https://doc.rust-lang.org/nomicon/vec.html

모든 소스코드와 테스트 결과는 아래의 링크에서 확인하실 수 있습니다. https://github.com/DonghyungKo/til/blob/master/rust/data-structures/vec/src/vec.rs

Vec<T>의 특징

Unique<T>에 이어서 Vec<T> 구현을 계속하여 진행하도록 하겠습니다. Vec<T>의 가장 유용한 특성 중 하나는 런타임에 동적으로 힙 영역에 메모리를 할당한다는 점입니다. 프로그램을 작성하다보면, 컴파일 타임에 그 크기를 알 수 없는 데이터가 존재합니다. Vec<T>는 이러한 배열 형태의 데이터를 다루는데 최적화된 데이터 타입입니다.

Vec<T>의 원리

Vec<T>는 내부적으로 현재 가지고 있는 데이터보다 더 많은 데이터가 저장될 수 있는 고정된 크기의 메모리 공간을 소유하고 있습니다. Vec<T>는 할당받은 메모리 공간의 시작 주소에 대한 포인터(ptr)와 할당받은 공간의 크기(capacity)를 통해, Layout에 대한 정보를 저장합니다. 또한, Vec<T>는 시작 주소에 대한 offset 연산을 통해 원하는 데이터에 접근할 수 있습니다.

https://www.geeksforgeeks.org/how-do-dynamic-arrays-work/

만약, 데이터가 추가되어 공간이 부족하게 되면 데이터를 추가적으로 요청하여 메모리 공간을 확장합니다. Vec<T>가 메모리를 확장하는 방식은 C/C++과 매우 유사합니다. Vec<T>는 추가적인 메모리가 필요할 때, 매번 이전에 요청했던 크기의 2배만큼의 메모리를 요청하고, 이에 대한 포인터(ptr)와 크기(cap)를 업데이트합니다.

https://www.geeksforgeeks.org/how-do-dynamic-arrays-work/

Vec<T>의 구조

Vec<T>는 내부적으로 다음과 같은 구조를 가지고 있습니다.

/// Vec<T>
/// Vec<T> is a Heap-allocated dynamically sized array.
/// This is done by dynamically growing memory allocation of Vec<T> by double
/// as the numober of elements in Vec<T> increases.
pub struct Vec<T> {
    inner: RawVec<T>,
    len: usize,
}

RawVec<T>

Vec<T>를 구성하는 RawVec<T>는 저장하고 있는 데이터가 증가함에 따라 새로운 메모리 영역을 요청하고, Vec<T>가 제거되는 시점에 요청한 메모리를 해제하는 역할을 담당하고 있습니다.

/// RawVec<T>
/// RawVec<T> is a Heap-allocated dynamically sized array.
/// RawVec<T> if responsible for specifing buffer and freeing its memory in Vec<T> and IntoIter<T>
/// so that, wrapper of RawVec<T> doesn't need to care about these jobs.
pub struct RawVec<T> {
    ptr: Unique<T>,
    cap: usize,
}
impl<T> RawVec<T> {
    /// Allocate memory for Vec<T> as it grows
    #[inline]
    fn allocate(&mut self) {
        unsafe {
            let (new_cap, result) = if self.cap == 0 {
                // Allocate memory for Vec<T> for the first time
                let new_cap = 1;
                let result =
                    std::alloc::Global.allocate(std::alloc::Layout::array::<T>(new_cap).unwrap());

                (new_cap, result)
            } else {
                // Reallocate memory for Vec<T> as it grows
                // }
                let new_cap = self.cap * 2; // capacity doubles

                // check that the new allocation doesn't exceed `usize::MAX` at all
                // regardless of the actual size of the capacity
                assert!(
                    new_cap * self.elem_size() <= usize::MAX,
                    "capacity overflow"
                );

                let result = std::alloc::Global.grow(
                    self.ptr.as_nonnull().cast(),
                    Layout::array::<T>(self.cap).unwrap(),
                    Layout::array::<T>(new_cap).unwrap(),
                );

                (new_cap, result)
            };

            // Out-of-Memory
            if result.is_err() {
                std::alloc::handle_alloc_error(Layout::from_size_align_unchecked(
                    new_cap * self.elem_size(),
                    std::mem::align_of::<T>(),
                ))
            }

            self.ptr = Unique::new_unchecked(result.unwrap().as_ptr().cast());
            self.cap = new_cap;
        }
    }

Vec<T> 구현

Vec<T>의 가장 기본적인 기능은 배열에 데이터를 추가/제거하는 기능입니다. Vec<T>는 배열의 맨 끝에 데이터를 추가하는 push() 메서드와 배열의 맨 끝 데이터를 제거하는 pop() 메서드를 가지고 있습니다.

impl<T> Vec<T> {
    /// Append element at the back of Vec<T>
    /// If the capacity lacks, Vec<T> will re-allocate more memory.
    pub fn push(&mut self, elem: T) {
        if self.len == self.inner.cap {
            self.inner.allocate()
        }

        unsafe {
            let offset = self.inner.ptr.as_ptr().offset(self.len as isize);
            std::ptr::write(offset, elem);
        }

        self.len += 1;
    }

    /// Pop element from the back of Vec<T> or return `None` if Vec<T> is empty
    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }

        self.len -= 1;
        unsafe {
            Some(std::ptr::read(
                self.inner.ptr.as_ptr().offset(self.len as isize),
            ))
        }
    }
}

Vec<T>는 또한 배열의 중간에 데이터를 추가하는 insert() 메서드와 배열의 중간에 위치한 데이터를 제거하는 remove() 메서드를 가지고 있습니다. 이 메서드들은 배열의 중간의 데이터를 추가/제거하기 때문에, 배열에서 해당 인덱스 뒤에 위치한 데이터들을 우측(혹은 좌측)으로 한 칸씩 이동해주어야 한다는 특징이 있습니다.

impl<T> Vec<T> {
    /// Insert an element to given index by moving all the other elements to the right
    /// by one
    pub fn insert(&mut self, index: usize, elem: T) {
        // assert!(index <= self.len, "index out of bounds");
        if self.inner.cap == self.len() {
            self.inner.allocate()
        }

        unsafe {
            if index < self.len {
                std::ptr::copy(
                    self.inner.ptr.as_ptr().offset(index as isize),
                    self.inner.ptr.as_ptr().offset(index as isize + 1),
                    self.len - index,
                )
            }

            std::ptr::write(self.inner.ptr.as_ptr().offset(index as isize), elem);
            self.len += 1;
        }
    }

    /// Remove an element from Vec<T> and move other elements to the left by one
    pub fn remove(&mut self, index: usize) -> T {
        // assert!(index < self.len, "index out of bounds");
        unsafe {
            self.len -= 1;
            let result = std::ptr::read(self.inner.ptr.as_ptr().offset(index as isize));
            std::ptr::copy(
                self.inner.ptr.as_ptr().offset(index as isize + 1),
                self.inner.ptr.as_ptr().offset(index as isize),
                self.len - index,
            );
            result
        }
    }
}

지금까지 Vec<T>의 기본적인 기능인 데이터의 추가/제거를 구현하였습니다. 감사합니다.

이 밖에도 Vec와 관련된 추가적인 구현 (ex, IntoIter<T>, Drop, Deref) 등이 궁금하시다면 아래의 링크를 통해 확인하실 수 있습니다. 감사합니다.
https://github.com/DonghyungKo/til/blob/master/rust/data-structures/src/vec.rs