C++에서 벡터 구현

Jinku Hu 2023년10월12일
C++에서 벡터 구현

이 기사는 C++에서 std::vector와 유사한 클래스를 구현하는 방법을 보여줍니다.

mallocrealloc 함수를 사용하여 C++에서 사용자 정의 vector 클래스 구현

std::vector 컨테이너는 요소를 연속적으로 저장하는 동적 C 스타일 배열로 알려져 있습니다. 정확한 구현이 시행되지는 않지만 사양에 따라 컨테이너의 일부 기능이 필요합니다. 즉, vector는 순서가 지정된 데이터 구조여야 하며 해당 요소에 대한 임의 액세스를 제공해야 합니다. 다른 기능은 인터페이스로 노출되는 공용 멤버 함수로 표현할 수 있으며, 그 중 일부는 다음 예제에서 구현할 것입니다. 실제 std::vector 구현은 매우 광범위할 수 있으므로 독자가 더 많은 기능을 추가할 수 있는 시작점을 보여주고 있습니다.

먼저 MyVector 클래스를 모든 일반 유형을 저장할 수 있는 함수 템플릿으로 정의해야 합니다. 그런 다음 크기/용량을 적절하게 저장하기 위해 요소 배열 및 정수 개체에 대한 포인터와 같은 핵심 데이터 멤버를 포함할 수 있습니다. std::vector는 더 나은 성능을 위해 저장된 요소보다 더 큰 메모리 청크를 할당할 수 있음을 기억하십시오. 이 할당된 메모리 크기를 벡터의 용량이라고 하며 cap 데이터 멤버에 저장합니다. 새로운 MyVector 개체가 생성되고 현재 요소를 0으로 설정하면 고정된 양(20 개체)을 할당합니다.

최신 C++에서 유해한 것으로 간주될 수 있는 malloc 기능을 사용하지만 주의해서 사용하면 유연성과 우수한 성능을 제공합니다. 또한 malloc으로 할당된 메모리는 realloc 기능으로 확장할 수 있으며, 이는 어레이 크기 조정을 관리하는 데 필요합니다.

전체적으로 우리 클래스에는 동적 벡터의 기초를 형성하는 세 개의 멤버 함수와 [] 연산자가 포함되어 있습니다. 다음 예제 코드는 push_back, sizeoperator[] 함수 구현을 보여줍니다. 후자의 두 가지는 매우 직관적이고 이해하기 쉬운 반면 push_back은 약간의 설명이 필요할 수 있습니다.

요소 수가 용량을 초과할 때 객체가 구성되면 새 메모리 영역만 할당하면 됩니다. 따라서 push_back 함수의 각 시나리오에 대해 두 개의 별도 경로가 필요하며 그 중 하나는 realloc 함수를 호출하여 현재 메모리 블록을 확장합니다. realloc은 이전 메모리 영역에 대한 포인터와 바이트 단위의 새 영역 크기라는 두 가지 매개변수를 허용합니다. 호출이 성공하면 동일한 블록에서 충분한 메모리를 찾을 수 있는지 여부에 따라 이전 포인터와 같거나 새 포인터가 유효한 포인터가 반환됩니다. 그렇지 않으면 요청이 실패했음을 나타내기 위해 NULL 포인터가 반환됩니다.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

template <typename T>
class MyVector {
 public:
  MyVector() {
    cap = alloc;
    vector = (T *)malloc(sizeof(T) * alloc);
    elem_num = 0;
  };

  void push_back(const T &data);
  void pop_back();

  [[nodiscard]] bool empty() const;
  [[nodiscard]] size_t size() const;
  [[nodiscard]] size_t capacity() const;
  T &operator[](size_t pos);

  ~MyVector();

 private:
  T *vector = nullptr;
  size_t cap;
  size_t elem_num;
  const int alloc = 20;
};

template <typename T>
MyVector<T>::~MyVector() {
  free(vector);
}

template <typename T>
void MyVector<T>::push_back(const T &data) {
  if (elem_num < cap) {
    *(vector + elem_num) = data;
    elem_num++;
  } else {
    vector = (T *)realloc(vector, sizeof(T) * cap * 2);
    cap *= 2;

    if (vector) {
      *(vector + elem_num) = data;
      elem_num++;
    }
  }
}

template <typename T>
void MyVector<T>::pop_back() {
  if (empty()) return;
  elem_num--;
}

template <typename T>
T &MyVector<T>::operator[](size_t pos) {
  if (pos >= 0 && pos <= elems) return *(this->arr + pos);
  throw std::out_of_range("Out of bounds element access");
}

template <typename T>
size_t MyVector<T>::capacity() const {
  return cap;
}

template <typename T>
bool MyVector<T>::empty() const {
  return elem_num == 0;
}

template <typename T>
size_t MyVector<T>::size() const {
  return elem_num;
}

struct MyClass {
  int num;
  double num2;
};

int main() {
  MyVector<MyClass> m1;

  m1.push_back({1, 1.1});
  m1.push_back({1, 1.2});
  m1.push_back({1, 1.3});
  m1.push_back({1, 1.4});

  for (size_t i = 0; i < m1.size(); ++i) {
    cout << m1[i].num << ", " << m1[i].num2 << endl;
  }

  cout << "/ ------------------- /" << endl;
  m1.pop_back();
  m1.pop_back();

  for (size_t i = 0; i < m1.size(); ++i) {
    cout << m1[i].num << ", " << m1[i].num2 << endl;
  }

  return EXIT_SUCCESS;
}

출력:

1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2

MyVector 클래스를 테스트하기 위해 main 함수에 일부 드라이버 코드를 포함하고 요소로 저장할 MyClass 사용자 정의 개체를 정의합니다. 마지막으로 벡터 뒤에 있는 요소를 제거하는 pop_back 함수를 추가합니다. pop_back 기능은 요소 내용을 할당 해제하거나 삭제할 필요가 없습니다. 각 호출에서 elem_num 멤버를 하나씩 감소시킬 수 있으며 다음 push_back 호출은 폐기된 요소 위치를 다시 작성합니다. 객체가 범위를 벗어나면 메모리 블록을 할당 해제하는 것도 중요합니다. 따라서 클래스의 소멸자에 free 함수에 대한 호출을 포함해야 합니다.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

template <typename T>
class MyVector {
 public:
  MyVector() {
    arr = new T[default_capacity];
    cap = default_capacity;
    elems = 0;
  };

  void push_back(const T &data);
  void pop_back();

  [[nodiscard]] bool empty() const;
  [[nodiscard]] size_t size() const;
  [[nodiscard]] size_t capacity() const;
  T &operator[](size_t pos);

  ~MyVector();

 private:
  T *arr = nullptr;
  size_t cap;
  size_t elems;
  const int default_capacity = 20;
};

template <typename T>
MyVector<T>::~MyVector() {
  delete[] arr;
}

template <typename T>
void MyVector<T>::push_back(const T &data) {
  if (elems < cap) {
    *(arr + elems) = data;
    elems++;
  } else {
    auto tmp_arr = new T[cap * 2];
    cap *= 2;
    for (int i = 0; i < elems; i++) {
      tmp_arr[i] = arr[i];
    }
    delete[] arr;
    arr = tmp_arr;

    *(arr + elems) = data;
    elems++;
  }
}

template <typename T>
T &MyVector<T>::operator[](size_t pos) {
  if (pos >= 0 && pos <= elems) return *(this->arr + pos);
  throw std::out_of_range("Out of bounds element access");
}

template <typename T>
size_t MyVector<T>::size() const {
  return elems;
}

template <typename T>
size_t MyVector<T>::capacity() const {
  return cap;
}

template <typename T>
void MyVector<T>::pop_back() {
  if (empty()) return;
  elems--;
}

template <typename T>
bool MyVector<T>::empty() const {
  return elems == 0;
}

struct MyClass {
  string name;
  double num;
};

int main() {
  MyVector<MyClass> m1;

  m1.push_back({"one", 1.1});
  m1.push_back({"two", 1.2});
  m1.push_back({"three", 1.3});
  m1.push_back({"four", 1.4});

  for (size_t i = 0; i < m1.size(); ++i) {
    cout << m1[i].name << ", " << m1[i].num << endl;
  }

  cout << "/ ------------------- /" << endl;
  m1.pop_back();
  m1.pop_back();

  for (size_t i = 0; i < m1.size(); ++i) {
    cout << m1[i].name << ", " << m1[i].num << endl;
  }

  return EXIT_SUCCESS;
}

출력:

one, 1.1
two, 1.2
three, 1.3
four, 1.4
/ ------------------- /
one, 1.1
two, 1.2
작가: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

관련 문장 - C++ Vector