C++ Vector 구현하기

in Dev. Log on Algorithm, Data Structure

Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다. 나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

Documents

FunctionDescription
operator[]Returns a reference to the element at position n in the vector container.
begin()Return iterator to beginning.
end()Return iterator to end.
front()Returns a reference to the first element in the vector.
back()Returns a reference to the last element in the vector.
push_back(T&)Adds a new element at the end of the vector, after its current last element.
pop_back()Removes the last element in the vector.
resize(size_t n)Resizes the container so that it contains n elements.
If n is smaller than the current container size, the content is reduced to its first n elements.
If n is greater than the current container size, the content is expanded by inserting at the end as many elements as needed to reach a size of n.
swap(Vector& x)Exchanges the content of the container by the content of x, which is another vector object of the same type. Sizes may differ.
capacity()Returns the size of the storage space currently allocated for the vector.
size()Returns the number of elements in the vector.
empty()Returns whether the vector is empty (i.e. whether its size is 0).
clear()Removes all elements from the vector. (capacity does NOT change.)

잡담

C++ container의 꽃 vector입니다.
막상 보면 구현이 어렵지는 않지만 없으면 세상 불편하고 직접 구현하자니 귀찮은 친구입니다.
Iterator를 구현하지 못한 점이 아쉽습니다만, 이외에 자주 사용하는 함수들은 대부분 구현되어 있습니다.

구현

#include <cstddef>
#include <utility>

template <typename T>
class  Vector {
private:
  static constexpr size_t DEFAULT_CAP = 32;
  T* arr;
  size_t m_size;
  size_t m_capacity;

public:
  Vector(size_t cap = DEFAULT_CAP) : arr(new T[cap]), m_size(0), m_capacity(cap) {}
  Vector(const Vector& v) : arr(new T[v.m_capacity]), m_size(v.m_size), m_capacity(v.m_capacity) {
    for (size_t i = 0; i < m_size; i++)
      arr[i] = v[i];
  }
  Vector(Vector&& v) : arr(std::move(v.arr)), m_size(std::move(v.m_size)), m_capacity(std::move(v.m_capacity)) {
    v.arr = nullptr;
    v.m_size = 0;
    v.m_capacity = 0;
  }

  ~Vector() { delete[] arr; }

  Vector& operator=(const Vector& other) {
    if (this != &other) {
      if (m_capacity < other.m_capacity) {
        delete[] arr;
        m_capacity = other.m_capacity;
        arr = new T[m_capacity];
      }
      m_size = other.m_size;
      for (size_t i = 0; i < m_size; i++)
        arr[i] = other.arr[i];
    }
    return *this;
  }
  Vector& operator=(Vector&& other) {
    std::swap(arr, other.arr);
    std::swap(m_size, other.m_size);
    std::swap(m_capacity, other.m_capacity);
    other.m_size = 0;
    return *this;
  }

  T* begin() const { return arr; }

  T* end() const { return arr + m_size; }

  T& front() { return arr[0]; }
  const T& front() const { return arr[0]; }

  T& back() { return arr[m_size - 1]; }
  const T& back() const { return arr[m_size - 1]; }

  T& operator[](size_t idx) { return arr[idx]; }
  const T& operator[](size_t idx) const { return arr[idx]; }

  void push_back(const T& val) {
    if (m_size >= m_capacity) {
      if (m_capacity < DEFAULT_CAP)
        m_capacity = DEFAULT_CAP;
      else
        m_capacity *= 2;
      T *t_arr = new T[m_capacity];
      for (size_t i = 0; i < m_size; i++)
        t_arr[i] = arr[i];
      delete[] arr;
      arr = t_arr;
    }
    arr[m_size++] = val;
  }
  void push_back(T&& val) {
    if (m_size >= m_capacity) {
      if (m_capacity < DEFAULT_CAP)
        m_capacity = DEFAULT_CAP;
      else
        m_capacity *= 2;
      T *t_arr = new T[m_capacity];
      for (size_t i = 0; i < m_size; i++)
        t_arr[i] = arr[i];
      delete[] arr;
      arr = t_arr;
    }
    arr[m_size++] = std::move(val);
  }

  void pop_back() { m_size = m_size > 0 ? m_size - 1 : 0; }

  void resize(size_t n, T val = T()) {
    T *t_arr = new T[n];
    m_size = m_size < n ? m_size : n;
    m_capacity = n;
    for (size_t i = 0; i < m_size; i++)
      t_arr[i] = arr[i];
    for (size_t i = m_size; i < m_capacity; i++)
      t_arr[i] = val;
    delete[] arr;
    arr = t_arr;
    m_size = n;
  }

  void reserve(size_t n) {
    if (n <= m_capacity)
      return;
    T *t_arr = new T[n];
    for (size_t i = 0; i < m_size; i++)
      t_arr[i] = arr[i];
    delete[] arr;
    arr = t_arr;
    m_capacity = n;
  }

  void swap(Vector& other) {
    std::swap(arr, other.arr);
    std::swap(m_size, other.m_size);
    std::swap(m_capacity, other.m_capacity);
  }

  size_t capacity() const { return m_capacity; }
  size_t size() const { return m_size; }
  bool empty() const { return m_size == 0; }
  void clear() { m_size = 0; }

  bool operator==(const Vector& other) const {
    if (m_size != other.m_size)
      return false;
    for (size_t i = 0; i < m_size; i++)
      if (arr[i] != other[i])
        return false;
    return true;
  }
  bool operator!=(const Vector& other) const { return !(*this == other); }
  bool operator< (const Vector& other) const {
    bool is_all_same = true;
    size_t min_size = m_size < other.m_size ? m_size : other.m_size;
    size_t idx = 0;
    for (; idx < min_size; idx++) {
      if (arr[idx] != other[idx]) {
        is_all_same = false;
        break;
      }
    }

    if (is_all_same) {
      if (m_size < other.m_size)
        return true;
    } else {
      if (arr[idx] < other[idx])
        return true;
    }
    return false;
  }
  bool operator<=(const Vector& other) const { return !(other < *this); }
  bool operator> (const Vector& other) const { return (other < *this); }
  bool operator>=(const Vector& other) const { return !(*this < other); }
};
  • relational operators를 잘보면 ==과 < 두개만 실제로 구현해 두고 나머지는 그 두개를 호출하는 형식으로 구현되어 있습니다.
    이러한 방식을 통해 에러가 날 가능성이 줄어들고 유지보수가 간편해집니다.
  • vector 생성시 기본 capacity는 32 입니다. DEFAULT_CAP으로 해당 값을 수정할 수 있습니다.