C++ 中的向量实现
本文将演示如何在 C++ 中实现一个类似于 std::vector
的类。
使用 malloc
和 realloc
函数在 C++ 中实现自定义 vector
类
std::vector
容器被称为动态 C 样式数组,它连续存储其元素。尽管没有强制执行确切的实现,但规范要求容器的某些功能。也就是说,向量应该是一个有序的数据结构,并提供对其元素的随机访问。其他功能可以表示为作为接口公开的公共成员函数,其中一些我们将在以下示例中实现。请注意,实际的 std::vector
实现可能会非常广泛,因此我们只是展示了读者可能会添加更多功能的起点。
首先,我们需要定义一个 MyVector
类作为可以存储任何泛型类型的函数模板。然后我们可以包含核心数据成员,如指向元素数组的指针和整数对象,以相应地存储大小/容量。请记住,为了获得更好的性能,std::vector
可能会分配比存储元素更大的内存块。分配的内存大小称为向量的容量,我们将其存储在 cap
数据成员中。一旦构建了新的 MyVector
对象并将当前元素设置为零,我们将分配固定数量(20
个对象)。
请注意,我们使用了 malloc
函数,这在当代 C++ 中可能被认为是有害的,但如果谨慎使用,它会提供灵活性和良好的性能。此外,使用 malloc
分配的内存可以使用 realloc
函数进行扩展,我们将需要它来管理数组的大小调整。
总的来说,我们的类包含三个成员函数和 []
运算符,它们构成了动态向量的基础。以下示例代码演示了 push_back
、size
和 operator[]
函数实现。后两者非常直观且易于理解,而 push_back
可能需要一些解释。
请注意,当元素数量超过容量时,我们只需要在构造对象后分配新的内存区域。因此,对于 push_back
函数中的每个场景,我们需要两个单独的路径,其中一个将调用 realloc
函数来扩展当前内存块。realloc
接受两个参数:指向前一个内存区域的指针和新区域的大小(以字节为单位)。如果调用成功,则返回一个有效指针,与前一个指针相同或一个新指针,具体取决于在同一块中是否可以找到足够的内存。否则,返回 NULL
指针以表示请求失败。
#include <iostream>
#include <string>
using std::cout; using std::cin;
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::cout; using std::cin;
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