C++에서 벡터 구현
이 기사는 C++에서 std::vector
와 유사한 클래스를 구현하는 방법을 보여줍니다.
malloc
및 realloc
함수를 사용하여 C++에서 사용자 정의 vector
클래스 구현
std::vector
컨테이너는 요소를 연속적으로 저장하는 동적 C 스타일 배열로 알려져 있습니다. 정확한 구현이 시행되지는 않지만 사양에 따라 컨테이너의 일부 기능이 필요합니다. 즉, vector
는 순서가 지정된 데이터 구조여야 하며 해당 요소에 대한 임의 액세스를 제공해야 합니다. 다른 기능은 인터페이스로 노출되는 공용 멤버 함수로 표현할 수 있으며, 그 중 일부는 다음 예제에서 구현할 것입니다. 실제 std::vector
구현은 매우 광범위할 수 있으므로 독자가 더 많은 기능을 추가할 수 있는 시작점을 보여주고 있습니다.
먼저 MyVector
클래스를 모든 일반 유형을 저장할 수 있는 함수 템플릿으로 정의해야 합니다. 그런 다음 크기/용량을 적절하게 저장하기 위해 요소 배열 및 정수 개체에 대한 포인터와 같은 핵심 데이터 멤버를 포함할 수 있습니다. std::vector
는 더 나은 성능을 위해 저장된 요소보다 더 큰 메모리 청크를 할당할 수 있음을 기억하십시오. 이 할당된 메모리 크기를 벡터의 용량이라고 하며 cap
데이터 멤버에 저장합니다. 새로운 MyVector
개체가 생성되고 현재 요소를 0으로 설정하면 고정된 양(20
개체)을 할당합니다.
최신 C++에서 유해한 것으로 간주될 수 있는 malloc
기능을 사용하지만 주의해서 사용하면 유연성과 우수한 성능을 제공합니다. 또한 malloc
으로 할당된 메모리는 realloc
기능으로 확장할 수 있으며, 이는 어레이 크기 조정을 관리하는 데 필요합니다.
전체적으로 우리 클래스에는 동적 벡터의 기초를 형성하는 세 개의 멤버 함수와 []
연산자가 포함되어 있습니다. 다음 예제 코드는 push_back
, size
및 operator[]
함수 구현을 보여줍니다. 후자의 두 가지는 매우 직관적이고 이해하기 쉬운 반면 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
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