文章目录
- 一、什么是 vector？
- 二、bit::vector 的设计思路
- 三、bit::vector 的类定义
- 四、构造函数与析构函数
- 五、push_back 和内存管理
- 六、插入操作 (insert)
- 七、删除操作 (erase)
- 八、resize 和 reserve 的实现
- 九、拷贝与赋值操作
- 十、容量管理
- 十一、迭代器的实现
- 总结
前言：在这篇博客中，我们将深入探讨如何通过C++模板编程实现一个 vector 容器。我们将对C++标准库中的 std::vector
进行模拟，实现其中的主要功能，包括内存管理、动态扩容、插入、删除等操作。
一、什么是 vector？
vector 是C++标准模板库（STL）中最常用的数据结构之一，作为一种动态数组，具有如下特点：
动态扩展：vector 能够根据需要动态扩展其容量，用户不必担心数组长度的限制。
随机访问：vector 支持通过下标随机访问元素，时间复杂度为常数O(1)。
内存连续：vector 在内存中分配的空间是连续的，因此它能够和普通数组一样高效地使用缓存机制。
由于这些优点，vector 经常被用作替代传统数组的工具。
接下来，我们将模拟实现一个类似 std::vector 的容器，命名为 bit::vector，并详细分析其中的每个关键部分。
二、bit::vector 的设计思路
bit::vector 的基本设计思路遵循以下原则：
- 内存管理：我们需要自己管理内存，包括动态分配和释放内存。尤其是当需要存储的元素超出当前分配空间时，容器需要能够自动扩展。
- 容量与大小：容量(capacity) 和大小(size) 的概念需要分离。容量指的是容器在当前分配内存中可以容纳的最大元素数量，而大小则是容器当前实际存储的元素数量。
- 异常安全：我们需要保证在各种边界情况（如插入和删除操作时）不发生内存泄漏或崩溃。
- 迭代器支持：为了支持STL风格的算法，我们的 bit::vector 也需要实现 begin() 和 end() 函数，返回相应的迭代器。
三、bit::vector 的类定义
bit::vector 类的实现从类模板开始。我们定义了模板类 bit::vector，其中 T 代表存储的元素类型。这个类包含以下几个重要的数据成员：
_start：指向数据的起始位置。
_finish：指向当前有效数据的末尾位置。
_endofstorage：指向当前分配的内存空间的末尾，即容量的终点。
这些指针变量帮助我们管理存储元素的内存区域。
namespace bit
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
接下来，我们将详细分析各个成员函数的实现。
四、构造函数与析构函数
vector 的构造函数是定义一个容器的起点。我们提供了几种不同的构造函数，用以支持不同的使用场景，包括：
默认构造函数：构造一个空的 vector，此时不分配任何内存。
区间构造函数：从两个迭代器构造一个 vector，用于从已有的数据范围初始化 vector。
填充构造函数：构造一个指定大小，并用指定值填充的 vector。
初始化列表构造函数：使用C++11的初始化列表语法，允许用户通过 {} 方式来初始化 vector。
1. 默认构造函数
默认构造函数用于构造一个空的 vector，我们直接让所有指针初始化为空即可。此时，_start、_finish、_endofstorage 均为 nullptr。
vector()
{}
2. 区间构造函数
区间构造函数用于从迭代器 first 到迭代器 last 之间的元素初始化 vector。它的实现是一个模板函数，支持泛型输入。
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
该构造函数通过遍历输入区间，逐个将元素插入到 vector 中。
3. 填充构造函数
填充构造函数可以根据用户传入的大小 n，以及指定的值 val 来初始化 vector。它的实现分为两种，一种是使用整数类型的构造函数，另一种是使用 size_t 类型的构造函数。
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
上面这个构造函数先通过 reserve(n) 方法为 vector 预留出 n 个存储空间，随后使用 push_back(val) 方法将 n 个 val 插入到 vector 中。
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
与上一个版本类似，区别在于使用了 size_t 类型，以支持更大的容器大小。
4. 初始化列表构造函数
C++11 引入了初始化列表，我们可以使用 initializer_list 来为 vector 初始化元素。
vector(initializer_list<T> il)
{
reserve(il.size());
for (auto&e : il)
{
push_back(e);
}
}
通过 initializer_list，用户可以通过花括号的形式来直接初始化 vector，例如 bit::vector v = {1, 2, 3, 4};。
5. 拷贝构造函数
当我们需要通过另一个 vector 对当前对象进行初始化时，需要使用拷贝构造函数。其实现如下：
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
这里，我们为当前对象预留了与源对象 v 相同的容量，随后将 v 中的所有元素逐个插入到当前对象中。
6. 析构函数
析构函数的作用是释放已分配的内存空间，避免内存泄漏。在我们的实现中，由于使用了指针管理内存，因此需要手动释放。
~vector()
{
if (_start)
{
_start = _finish = _endofstorage = nullptr;
}
}
需要注意的是，delete 操作可以由其他函数处理，而在析构函数中，我们仅将指针重置为 nullptr。
五、push_back 和内存管理
push_back 是 vector 中的核心方法，用于在容器末尾添加元素。其内部涉及到内存的管理与扩展操作。
首先，我们需要实现 reserve 函数，用于为 vector 预留一定的存储空间。reserve 函数的逻辑是，如果当前容量不够，则分配更大的内存并将已有数据搬移过去。
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
这个函数首先检查新容量 n 是否比当前容量大，如果大，则分配一块大小为 n 的新内存，并将原有数据复制到新内存中。之后释放原来的内存。
接着，我们实现 push_back，其内部会调用 reserve 来确保有足够的空间来存储新元素。
void push_back(const T& x)
{
insert(_finish, x);
}
六、插入操作 (insert)
insert 方法的功能是在指定位置插入一个新元素。由于 vector 是一个动态数组，插入元素后需要移动后面的元素以腾出空间。因此，该方法的实现需要特别注意如何高效地移动数据并扩展内存。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
// 判断是否需要扩容
if (_finish == _endofstorage)
{
size_t len = pos - _start; // 计算插入位置的偏移量
reserve(capacity() == 0 ? 4 : 2 * capacity()); // 如果容量不足，则扩展两倍
pos = _start + len; // 重新计算插入位置
}
// 从末尾开始，向后移动元素
iterator i = _finish - 1;
while (i >= pos)
{
*(i + 1) = *i;
--i;
}
*pos = x; // 在指定位置插入新元素
++_finish; // 更新元素的结束位置
return pos;
}
这段代码首先确保 pos 是一个有效的插入位置，接着检查 vector 是否需要扩容，如果需要，则调用 reserve 来分配新的内存。扩容完成后，它会调整插入位置的 pos，以防止指针失效。
之后，从 _finish - 1 开始，向后移动每个元素，给插入位置腾出空间，最后将新元素 x 插入到 pos 位置。
这种方式保证了插入操作的时间复杂度为 O(n)，其中 n 是插入位置后面元素的数量。虽然在最坏情况下插入元素的操作较为耗时，但这是动态数组的固有特性。
七、删除操作 (erase)
erase 方法用于删除 vector 中的某个元素。其基本思路是删除指定位置的元素后，将后续的元素前移，以填补空缺。删除的元素不需要释放内存，只是修改指针 _finish。
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator i = pos + 1;
while (i < _finish)
{
*(i - 1) = *i; // 将后面的元素向前移动
++i;
}
--_finish; // 更新结束位置
return pos;
}
该方法通过逐个前移元素，覆盖要删除的元素，最后将 _finish 向前移动一位。这一操作也需要注意时间复杂度为 O(n)，其中 n 是删除位置后面的元素数量。
八、resize 和 reserve 的实现
resize 和 reserve 是 vector 中两个与内存管理密切相关的方法。
1. resize 方法
resize 方法用于调整 vector 的大小。如果新大小小于当前大小，它会截断多余的元素；如果新大小大于当前大小，它会扩展 vector 并用给定的值填充新空间。
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n; // 截断到新的大小
}
else
{
reserve(n); // 如果需要增加大小，则确保容量足够
while (_finish < _start + n)
{
*_finish = val; // 填充新的元素
_finish++;
}
}
}
在这个函数中，首先检查 n 是否小于当前大小。如果是，则直接修改 _finish，使其指向新的位置。否则，需要调用 reserve 来扩展内存并将新元素添加到 vector 中。
2. reserve 方法
reserve 的功能是为 vector 预留至少 n 个元素的存储空间。如果 n 大于当前容量，则分配新的内存并将已有的元素复制过去。
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i]; // 将原来的元素复制到新内存
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
这里首先检查 n 是否大于当前容量，如果是，则分配一块新的内存。然后，复制已有元素到新内存中，最后释放旧的内存，并更新 _start、_finish 和 _endofstorage 指针。
九、拷贝与赋值操作
在现代 C++ 编程中，拷贝构造函数和赋值运算符的实现是容器类设计的重要环节，涉及到深拷贝和内存管理。
1. 拷贝构造函数
当我们使用 vector 的拷贝构造函数时，必须将原对象的数据拷贝到新对象中，同时避免共享同一块内存。
vector(const vector<T>& v)
{
reserve(v.capacity()); // 为新对象预留足够的空间
for (auto& e : v)
{
push_back(e); // 逐个拷贝原对象的元素
}
}
这里首先调用 reserve 函数为新对象分配与原对象相同的容量，随后通过 push_back 方法逐个复制原对象的元素。
2. 赋值运算符
赋值运算符用于将一个 vector 赋值给另一个 vector。为了防止内存泄漏，赋值操作通常采用“拷贝并交换”技术。该技术通过先创建一个临时对象，最后交换临时对象和当前对象的资源，保证赋值操作的异常安全性。
vector<T>& operator= (vector<T> v)
{
swap(v); // 通过交换完成赋值
return *this;
}
这里，我们首先创建一个临时对象 v，通过传值方式创建该对象可以确保临时对象的内存安全。随后，使用 swap 函数交换当前对象和临时对象的指针，保证内存安全和赋值操作的正确性。
十、容量管理
vector 容器中有两个重要的概念：size 和 capacity。size 表示当前存储的元素个数，而 capacity 表示已分配的存储空间。
1. size 方法
size 方法返回当前容器中存储的元素个数。其实现非常简单：
size_t size() const
{
return _finish - _start; // 当前大小为结束指针和起始指针的差
}
2. capacity 方法
capacity 方法返回当前分配的存储空间，可以存储的最大元素个数。
size_t capacity() const
{
return _endofstorage - _start; // 容量为存储空间的结束指针和起始指针的差
}
十一、迭代器的实现
为了支持 STL 算法，vector 必须实现迭代器。我们定义了 begin 和 end 方法，分别返回起始位置和结束位置的迭代器。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
begin 返回指向第一个元素的指针，而 end 返回指向最后一个元素之后的指针。
总结
通过本文，我们详细探讨了如何从头开始模拟实现一个类似 std::vector 的容器 bit::vector。这个实现虽然简化了许多复杂的细节，但涵盖了 vector 容器的核心功能，如内存管理、动态扩容、插入与删除操作、迭代器支持等。
内存管理 是 vector 的核心，我们通过实现 reserve 和 resize 等方法，来动态管理容器的容量。
拷贝与赋值操作 使用了“拷贝并交换”技术，确保了异常安全性。
插入与删除 操作通过移动元素实现，虽然效率在最坏情况下较低，但在大多数场景下仍然能够满足需求。
同时，我们还探讨了一些潜在的优化方向，如使用 allocator 进行更加高效的内存管理，支持移动语义和批量操作，以及通过扩展 STL 接口让 bit::vector 更加灵活和强大。
尽管如此，我们的实现还不是一个完整的容器类。要达到真正工业级别的质量，还需要更加深入的优化和完善。这包括多线程安全、异常处理、性能调优，以及对更多高级特性的支持。
在实际开发中，std::vector 是一个非常成熟且经过高度优化的容器，因此在大多数情况下使用它是最佳的选择。然而，通过实现 bit::vector，我们能够深入理解 std::vector 的设计思想和背后的技术细节。这种底层知识不仅可以帮助我们更好地使用标准库中的容器，也能在特定场景下开发出更适合自己需求的自定义容器。
标签：size,容器,finish,start,vector,内存,构造函数,一览无余 From： https://blog.csdn.net/ZWW_zhangww/article/details/142989413