动手写一个Vector
本文是对《最好的C++教程》的动手写数据结构部分的一个整理,主要包含91p动手写Array数组和92p动手写Vector数组的内容。
自己动手来写这些数据结构是学习C++的绝佳方法,并且可以更加深刻的理解标准库中Vector和Array的实现和用法。
Array数组主要包含的知识点有:模板,constexpr,const成员函数
Vector数组主要包含的知识点有:动态扩容,placement new,move semantics,emplace_back
原作者视频链接:https://youtu.be/TzB5ZeKQIHM ,https://youtu.be/ryRf4Jh_YC0
文中代码github链接:https://github.com/zhangyi1357/Little-stuff
Array数组
在大多数情况下,当我们需要一个数组时,我们都会优先使用vector
,因为vector
可以动态扩容,效率也足够高,非常好用。
但是你需要array
数组的情况在于很多时候只需要一个静态大小的数组,而这种情况下vector
的堆内存分配相较于array
数组直接在栈上分配内存的效率就比较低了。
实际上一个Array
数组的实现非常简单,如果你对模板比较熟悉的话,基本上就是给一个数组写一个模板然后给用户几个接口。
Array数组API
首先我们来看看其最终的API,这里我们直接以其一个使用的示例来看我们需要完成哪些功能
- 最基础的创建一个指定类型和大小的
array
- 能用
[]
运算符来索引,可以读取也可以写入 Size
方法返回其大小,其中Size
需要在编译期确定- 支持
Data
方法返回其数据地址,可以利用memset
批量设置其值
int main() {
constexpr int size = 5;
Array<int, size> data;
static_assert(data.Size() < 10, "Size is too large");
data[0] = 2;
data[1] = 3;
data[2] = 5;
for (size_t i = 0; i < data.Size(); ++i)
std::cout << data[i] << std::endl;
std::cout << "-----------------" << std::endl;
memset(data.Data(), 0, data.Size() * sizeof(int));
for (size_t i = 0; i < data.Size(); ++i)
std::cout << data[i] << std::endl;
std::cout << "-----------------" << std::endl;
Array<std::string, size> data2;
data2[0] = "Cherno";
data2[1] = "C++";
for (size_t i = 0; i < data2.Size(); ++i)
std::cout << data2[i] << std::endl;
return 0;
}
其输出为
2
3
5
0
336165216
-----------------
0
0
0
0
0
-----------------
Cherno
C++
这里有一个小点需要注意,我们可以看到未经初始化的Array在其类型为int
和std::string
时有不同的表现,int
类型其值是未定义的,所以可能输出任意值,例如上面的336165216
,而std::string
类型会自动初始化为一个空串。
Array数组实现
根据以上API,可以给出如下简洁代码实现
template <typename T, size_t S>
class Array {
public:
constexpr int Size() const { return S; }
T& operator[](size_t index) { return m_Data[index]; }
const T& operator[](size_t index) const { return m_Data[index]; }
T* Data() { return m_Data; }
const T* Data() const { return m_Data; }
private:
T m_Data[S];
};
const成员函数
注意到对[]
运算符的重载和Data
方法都给出了两个版本,一个const
一个非const
版本。
const
版本的函数性质和返回值都是const
,这主要是为了兼容const Array<T, S>
的用法,因为一个const Array<T, S>
类型的对象是不能调用非const
成员函数的,而显然我们也不希望这样一个类型的返回值是非const
的,因为我们不想通过该成员函数来改变其值。
constexpr
注意到前面的main
函数中有如下一条语句
static_assert(data.Size() < 10, "Size is too large");
这条语句用于编译期检查,那么我们的Size
方法一定也要能在编译器确定其值,这一点是完全可以做到的,因为我们要求的模板参数S
需要在编译期就能确定其值,所以我们只需要在Size
方法的返回值前面加上一个constexpr
表示该值可以在编译期求取即可。
Vector数组
Vector数组相较于Array的最大特点就在于动态扩容,我们不用指定其初始容量,而在使用过程中可以不断地以O(1)的时间复杂度向其尾部插入元素或读取任意位置的元素。
后文我们将先阐述动态扩容策略,并在此策略上完成基础版本的实现,然后在此基础上逐步优化性能添加功能。
动态扩容策略
首先我们需要在O(1)的时间复杂度内读取任意位置的元素,所以肯定需要连续存储的内存空间,不考虑使用链表等数据结构。
其次需要O(1)的时间复杂度在尾部进行插入,Array
数组其实可以满足这点,但是其容量有限,那么很直观的一个思路就是先分配一个有限容量的数组,如果满了还需要插入就重新分配一个更大的数组。
而动态扩容的trick就在此处,每次重新分配之后我们都需要将数组完整地挪到新的内存地址去,这一过程是非常耗时的,对于一个长度为n的数组来说其时间复杂度为O(n)。
我们解决的办法是每次分配数组的时候直接多分配一些空间,这样很多次插入操作才会有一个扩容操作,于是扩容的高消耗就被均摊到了每次的插入操作上,达到总体的O(1)时间复杂度。
那么具体多分配多少空间呢,我们要保证一次扩容操作被分摊到O(n)次插入操作上才行,所以扩大的容量必须要是O(n)这个数量级的。
实际中不同的编译器的处理方式不尽相同,MSVC中以1.5倍扩容,GCC中以2倍扩容。本文采取2倍扩容的方式。
基础版本
基础版本API
基础版本只需要实现以下的简单API即可,拆解开来我们需要完成
- 动态扩容
PushBack
方法- 重载[]运算符
Size
方法
template<typename T>
void PrintVector(const Vector<T>& vector) {
for (size_t i = 0; i < vector.Size(); ++i)
std::cout << vector[i] << std::endl;
std::cout << "---------------------------" << std::endl;
}
int main() {
Vector<std::string> vector;
vector.PushBack("Cherno");
vector.PushBack("C++");
vector.PushBack("Vector");
PrintVector(vector);
return 0;
}
基础版本实现
该实现较为简单,直接给出,各部分都有详细注释。注意我们的初始化策略是分配分配两个元素的空间。
template <typename T>
class Vector {
public:
Vector() { ReAlloc(2); }
void PushBack(const T& value) {
// check the space
if (m_Size >= m_Capacity)
ReAlloc(m_Size + m_Size);
// push the value back and update the size
m_Data[m_Size++] = value;
}
T& operator[](size_t index) { return m_Data[index]; }
const T& operator[](size_t index) const { return m_Data[index]; }
size_t Size() const { return m_Size; }
private:
void ReAlloc(size_t newCapacity) {
// allocate space for new block
T* newBlock = new T[newCapacity];
// ensure no overflow
if (newCapacity < m_Size)
m_Size = newCapacity;
// move all the elements to the new block
for (int i = 0; i < m_Size; ++i)
newBlock[i] = m_Data[i];
// delete the old space and update old members
delete[] m_Data;
m_Data = newBlock;
m_Capacity = newCapacity;
}
private:
T* m_Data = nullptr;
size_t m_Size = 0;
size_t m_Capacity = 0;
};
move版本
以上的基础版本可以实现基本的功能,但是其效率却太低,存在许多复制。我们可以自己写一个class测试一下。
move版本API
class Vector3 {
public:
Vector3() {}
Vector3(float scalar)
: x(scalar), y(scalar), z(scalar) {}
Vector3(float x, float y, float z)
: x(x), y(y), z(z) {}
Vector3(const Vector3& other)
: x(other.x), y(other.y), z(other.z) {
std::cout << "Copy" << std::endl;
}
Vector3(const Vector3&& other)
: x(other.x), y(other.y), z(other.z) {
std::cout << "Move" << std::endl;
}
~Vector3() {
std::cout << "Destroy" << std::endl;
}
Vector3& operator=(const Vector3& other) {
std::cout << "Copy" << std::endl;
x = other.x;
y = other.y;
z = other.z;
return *this;
}
Vector3& operator=(Vector3&& other) {
std::cout << "Move" << std::endl;
x = other.x;
y = other.y;
z = other.z;
return *this;
}
friend std::ostream& operator<<(std::ostream&, const Vector3&);
private:
float x = 0.0f, y = 0.0f, z = 0.0f;
};
std::ostream& operator<<(std::ostream& os, const Vector3& vec) {
os << vec.x << ", " << vec.y << ", " << vec.z;
return os;
}
int main() {
Vector<Vector3> vec;
vec.PushBack(Vector3());
vec.PushBack(Vector3(1.0f));
vec.PushBack(Vector3(1.0f, 2.0f, 3.0f));
PrintVector(vec);
return 0;
}
对于基础版本的API其输出为
Copy
Destroy
Copy
Destroy
Copy
Copy
Destroy
Destroy
Copy
Destroy
0, 0, 0
1, 1, 1
1, 2, 3
---------------------------
中间连着两个Copy和两个Destroy是扩容过程。除此之外的都是PushBack
时产生的。
实际上我们并不需要这么多复制,在PushBack
的时候可以将原来的内容直接移动到新的位置,扩容过程也是一样。这就要用到C++11的移动语义的特性了。
move版本实现
消除以上的Copy其实很简单,只需要重载一个接受右值的PushBack
并在其中进行move即可,另外要注意扩容过程也需要改成move的。
// new PushBack Method
void PushBack(T&& value) {
// check the space
if (m_Size >= m_Capacity)
ReAlloc(m_Size + m_Size);
// push the value back and update the size
m_Data[m_Size++] = std::move(value);
}
// in ReAlloc
for (int i = 0; i < m_Size; ++i)
newBlock[i] = std::move(m_Data[i]);
可以看到以下结果
Move
Destroy
Move
Destroy
Move
Move
Destroy
Destroy
Move
Destroy
0, 0, 0
1, 1, 1
1, 2, 3
---------------------------
可以看到现在全都是Move,没有Copy,效率提高!
EmplaceBack & Placement new
好了,现在我们有很高效的PushBack
实现,但是我们发现每一次PushBack仍然在外面构造好一个变量然后移动到Vector
里面。
那么有没有这样一种可能,直接把构造需要的参数给到Vector
,然后直接在给定的地址空间进行对象的构造。
实际上这一节介绍的EmplaceBack
和Placement New
就可以做到这一点。
原地构造 API
可以看到这里给EmplaceBack的直接是构造Vector3所需的参数而不是Vector3。
int main() {
Vector<Vector3> vec;
vec.EmplaceBack();
vec.EmplaceBack(1.0f);
vec.EmplaceBack(1.0f, 2.0f, 3.0f);
PrintVector(vec);
return 0;
}
原地构造实现
首先是EmplaceBack
的实现,实现依赖于模板参数展开,这里不做详细讨论,仅给出其实现。
注意到实现中的new
运算符,不同于一般的new
运算符,这里给出了一个参数作为需要new
的位置的地址,这样就可以直接在原地构造而不需要移来移去。
为了更好地理解placement new
,有必要讲一下new
运算符的机制,new
运算符实际上会做两件事情
- 分配内存
- 调用构造函数
而这里相当于内存分配已经提前做好了,我们只需要在相应的位置调用构造函数即可。
template<typename... Args>
T& EmplaceBack(Args&&... args) {
// check the space
if (m_Size >= m_Capacity)
ReAlloc(m_Size + m_Size);
// Placement new
new (&m_Data[m_Size]) T(std::forward<Args>(args)...);
return m_Data[m_Size++];
}
测试结果为
Move
Move
Destroy
Destroy
0, 0, 0
1, 1, 1
1, 2, 3
---------------------------
Amazing! 我们只在扩容的时候进行了两次Move,所有的对象都是在原地直接进行构造的。
关于new和delete的疑问
前面说了new
运算符会干两件事,分配内存和调用构造函数,那么在ReAlloc
中我们就使用了new
,同时做了分配内存和调用构造函数两件事,后面又将原来的值挪到新分配的地方,那构造函数的调用不就浪费了?
是的!实际上这个问题同样会反映在delete
运算符上,对于new
来说只是效率降低了,但对delete
来说可能会造成严重的bug。
不过不要着急后面会解决这个问题。
PopBack和析构函数
前面的过程中为了输出简单省略了析构函数,实际上析构函数不可或缺,否则会有内存泄漏。
同时我们增加PopBack
的功能。而这二者组合起来会造成一个非常严重的问题。
PopBack和析构函数 API
int main() {
Vector<Vector3> vec;
vec.EmplaceBack();
vec.EmplaceBack(1.0f);
vec.EmplaceBack(1.0f, 2.0f, 3.0f);
PrintVector(vec);
vec.PopBack();
vec.PopBack();
PrintVector(vec);
return 0;
}
PopBack和析构函数实现
其实现非常简单
void PopBack() {
if (m_Size > 0) {
--m_Size;
m_Data[m_Size].~T();
}
}
~Vector() { delete[] m_Data; }
输出也正常:
Move
Move
Destroy
Destroy
0, 0, 0
1, 1, 1
1, 2, 3
---------------------------
Destroy
Destroy
0, 0, 0
---------------------------
Destroy
Destroy
Destroy
Destroy
但是暗藏玄机的是,如果我们的Vector3
类中有指针指向某一片内存空间的话,那么PopBack
中会调用一次Vector3
的析构函数,然后析构函数中的delete
还会对该地址空间调用一次析构函数,那么该内存空间将被delete
两次!
接下来我们着手解决该问题。
::operator new/delete
我们解决的办法即本小节标题::operator new/delete
。首先给出测试的API。
析构API
class Vector3 {
public:
Vector3() {
m_MemoryBlock = new int[5];
}
Vector3(float scalar)
: x(scalar), y(scalar), z(scalar) {
m_MemoryBlock = new int[5];
}
Vector3(float x, float y, float z)
: x(x), y(y), z(z) {
m_MemoryBlock = new int[5];
}
Vector3(const Vector3& other) = delete;
Vector3(Vector3&& other)
: x(other.x), y(other.y), z(other.z) {
std::cout << "Move" << std::endl;
m_MemoryBlock = other.m_MemoryBlock;
other.m_MemoryBlock = nullptr;
}
~Vector3() {
std::cout << "Destroy" << std::endl;
delete[] m_MemoryBlock;
}
Vector3& operator=(const Vector3& other) {
std::cout << "Copy" << std::endl;
x = other.x;
y = other.y;
z = other.z;
return *this;
}
Vector3& operator=(Vector3&& other) {
std::cout << "Move" << std::endl;
x = other.x;
y = other.y;
z = other.z;
return *this;
}
friend std::ostream& operator<<(std::ostream&, const Vector3&);
private:
float x = 0.0f, y = 0.0f, z = 0.0f;
int* m_MemoryBlock = nullptr;
};
std::ostream& operator<<(std::ostream& os, const Vector3& vec) {
os << vec.x << ", " << vec.y << ", " << vec.z;
return os;
}
int main() {
{
Vector<Vector3> vec;
vec.EmplaceBack();
vec.EmplaceBack(1.0f);
vec.EmplaceBack(1.0f, 2.0f, 3.0f);
PrintVector(vec);
vec.PopBack();
vec.PopBack();
PrintVector(vec);
}
std::cout << "hello" << std::endl;
return 0;
}
对于此此前程序给出的输出为
Move
Move
Destroy
Destroy
0, 0, 0
1, 1, 1
1, 2, 3
---------------------------
Destroy
Destroy
0, 0, 0
---------------------------
Destroy
Destroy
可以看到并没有输出hello,应该是程序异常退出了,给程序打个断点在gdb下调试看看结果
正确内存管理实现
我们使用的办法就是将new
和delete
的两阶段分开,其中分配和回收的过程则调用::operator new
和::operator delete
。
具体实现如下:
~Vector() {
Clear();
::operator delete(m_Data, m_Capacity * sizeof(T));
}
void Clear() {
for (int i = 0; i < m_Size; ++i)
m_Data[i].~T();
m_Size = 0;
}
void ReAlloc(size_t newCapacity) {
// allocate space for new block
T* newBlock = (T*)::operator new(newCapacity * sizeof(T));
// ensure no overflow
if (newCapacity < m_Size)
m_Size = newCapacity;
// move all the elements to the new block
for (int i = 0; i < m_Size; ++i)
new(&newBlock[i]) T(std::move(m_Data[i]));
// delete the old space and update old members
Clear();
::operator delete(m_Data, m_Capacity * sizeof(T));
m_Data = newBlock;
m_Capacity = newCapacity;
}
可以看到主要就是将析构函数的调用挪到了Clear
函数里,只析构有元素的位置,然后删除和分配空间用::operater new/delete
。
注意::operator delete
的该重载函数直到C++14才得到支持,所以以上代码需要编译命令-std=c++14
或更高。
其输出结果为
Move
Move
Destroy
Destroy
1, 2, 3
---------------------------
Destroy
---------------------------
hello
没有问题!NICE!
总结
以上的Vector
模板类已经实现了动态扩容和高效的空间管理,但是仍有许多尚未完成的部分,例如迭代器,erase
方法等,有能力的小伙伴可以尝试实现更多。后续我也会继续完善。