C++vector类的模拟实现

namespace my_vector
{
    template<class T>
    class vector
    {
    public:

        // Vector的迭代器是一个原生指针

        typedef T* iterator；
        typedef const T* const_iterator；

            iterator begin()；

            iterator end()；

            const_iterator cbegin()；

            const_iterator cend() const；



            // construct and destroy
            vector()；
            vector(int n, const T& value = T())；
            template<class InputIterator>

            vector(InputIterator first, InputIterator last)；

            vector(const vector<T>& v)；

            vector<T>& operator= (vector<T> v)；

            ~vector()；

            // capacity
            size_t size() const ；

            size_t capacity() const；

            void reserve(size_t n)；

            void resize(size_t n, const T& value = T())；



            ///access///

            T& operator[](size_t pos)；

            const T& operator[](size_t pos)const；



            ///modify/

            void push_back(const T& x)；

            void pop_back()；

            void swap(vector<T>& v)；

            iterator insert(iterator pos, const T& x)；

            iterator erase(Iterator pos)；

    private:
        iterator _start; // 指向数据块的开始
        iterator _finish; // 指向有效数据的尾
        iterator _endOfStorage; // 指向存储容量的尾
    };
}

1. vector的迭代器

  // Vector的迭代器是一个原生指针
  typedef T* iterator;
  typedef const T* const_iterator;

  iterator begin()
  {
      return _start;
  }

  iterator end()
  {
      return _finish;
  }

  const_iterator cbegin()const
  {
      return _start;
  }

  const_iterator cend() const
  {
      return _finish;
  }

iterator 和 const_iterator 分别是指向元素的普通指针和常量指针。begin() 和 end() 方法返回容器的起始和结束迭代器，允许遍历元素。而 cbegin() 和 cend() 方法提供了常量迭代器，适用于只读访问。整体上，这些方法提供了对容器元素的访问方式，便于使用标准迭代器模式进行遍历。

2. vector的构造和析构

2.1 构造函数:

vector() : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{}

vector(int n, const T& value = T())
    : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{
    reserve(n);
    while (n--)
    {
        push_back(value);
    }
}

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
    reserve(last - first);
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

vector(const vector<T>& v)
    : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{
    reserve(v.capacity());
    iterator it = begin();
    const_iterator vit = v.cbegin();
    while (vit != v.cend())
    {
        *it++ = *vit++;
    }
    _finish = _start + v.size();
    _endOfStorage = _start + v.capacity();

}

1. 默认构造函数 vector() :

        初始化三个指针 _start, _finish, 和 _endOfStorage 为 nullptr，表示一个空的容器。

2. 带大小和初始值的构造函数 vector(int n, const T& value = T()) :

            使用 reserve(n) 预留存储空间，以便存放 n 个元素。
            通过 push_back(value) 将 value 添加到容器中，重复 n 次以填充容器。

3. 范围构造函数 template<class InputIterator> vector(InputIterator first, InputIterator last) :

            计算输入迭代器之间的距离并调用 reserve。
            使用 push_back(*first) 逐个添加元素，直到 first 达到 last。

4. 拷贝构造函数 vector(const vector<T>& v) :

            先调用 reserve(v.capacity()) 为新容器分配与源容器相同的容量。
            使用迭代器逐个复制元素，从源容器的常量迭代器 vit 读取，并将其值赋给当前容器的迭代器 it。
            最后，更新 _finish 和 _endOfStorage 指针，确保它们正确指向新容器的结束和存储空间的边界。

2.2 赋值操作符重载

        vector<T>& operator= (vector<T> v)
        {
            swap(v);
            return *this;
        }

参数为值传递：

vector<T> v 会创建传入对象的一个副本。这一副本会通过拷贝构造函数生成，保证了原对象不受影响。

调用 swap(v)：

swap 函数交换当前对象(*this) 和副本 v 的内容。这种做法能够高效地处理资源管理，避免多次内存分配和释放，减少了潜在的异常风险。

返回* this：

最后，返回对当前对象的引用，使得赋值操作可以链式调用，例如 a = b = c。

2. 3 析构函数

        ~vector()
        {
            delete[] _start;
            _start = _finish = _endOfStorage = nullptr;
        }

1. 内存释放：delete[] _start;

这行代码释放了之前通过动态分配（通常是在 reserve 或其他构造函数中）分配的内存。由于 _start 指向的是一个动态数组，所以使用 delete[] 来确保正确地释放整个数组。
2. 指针重置：_start = _finish = _endOfStorage = nullptr;

这一行将三个指针重置为 nullptr，以防止悬挂指针。虽然析构函数会在对象销毁后自动调用，但将指针设为 nullptr 是一种良好的编程习惯，能够减少错误风险，尤其是在调试时。
3. 异常安全：

析构函数通常不应该抛出异常，因此在此处处理资源释放时采用了简单直接的方法，确保即使在异常情况下也能正常释放资源。

3. vector容量的操作

3.1 size

        size_t size() const
        {
            return _finish - _start;
        }

3.2 capcity

        size_t capacity() const
        {
            return _endOfStorage - _start;
        }

3.3 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];
                }
                _start = tmp;
                _finish = _start + oldSize;
                _endOfStorage = _start + n;

            }
        }

1. 容量检查：if(n > capacity())

        首先检查请求的容量 n 是否大于当前容量。如果不大于，则不需要重新分配内存，函数直接返回。
2. 保存旧大小：size_t oldSize = size();

        记录当前元素的数量，以便在新内存中复制元素。
3. 动态分配新内存：T* tmp = new T[n];

        分配一个新的数组 tmp，大小为 n。
4. 复制旧数据：

        如果 _start 指针不为 nullptr（表示当前有存储的元素），则使用循环将旧数组中的元素复制到新数组 tmp。
5. 更新指针：

        _start 被更新为指向新分配的数组 tmp。
        _finish 更新为 _start + oldSize，指向已复制的元素末尾。
        _endOfStorage 更新为 _start + n，表示新数组的容量边界。

3.4 resize

void resize(size_t n, const T& value = T())
{
    // 1.如果n小于当前的size，则数据个数缩小到n
    if (n <= size())
    {
        _finish = _start + n;
        return;
    }

    // 2.空间不够则增容
    if (n > capacity())
        reserve(n);
    // 3.将size扩大到n
    iterator it = _finish;
    iterator _finish = _start + n;
    while (it != _finish)
    {
        *it = value;
        ++it;
    }
}

1. 缩小大小：如果新的大小小于或等于当前大小，直接将结束指针 _finish 移动到新大小，丢弃多余的元素。

2. 增容：如果新大小大于当前容量，调用 reserve 来确保 vector 有足够的空间。

3. 扩展大小：将结束指针更新到新大小，并用指定的值初始化新添加的元素，直到达到新的结束指针。

关键点总结：
当缩小时，只调整指针而不调用析构函数。
在增容时，通过 reserve 确保内存足够。
在扩展时，初始化新元素以保持一致性。

4. vector的修改

4.1 push_back

        void push_back(const T& x)
        {
            insert(end(), x);
        }

4.2 pop_back

        void pop_back()
        {
            erase(--end());
        }

4.3 swap

        void swap(vector<T>& v)
        {
            swap(_start, v._start);
            swap(_finish, v._finish);
            swap(_endOfStorage, v._endOfStorage);
        }

1. 指针交换：通过 swap 函数交换 _start、_finish 和 _endOfStorage 三个指针。这意味着两个 vector 将交换它们的内部存储，实际上并没有复制数据，而是简单地交换指针。

2. 高效性：这个交换操作非常高效，因为它只涉及指针的交换，而不需要移动任何元素或重新分配内存。

3. 异常安全：swap 的实现是标准库提供的版本（通常是 noexcept），那么这个函数也具有异常安全性。

4. 状态一致性：通过交换指针，两个 vector 的状态完全对调，原有的内存管理也随之转移，确保了资源的正确管理。

4.4 insert

        iterator insert(iterator pos, const T& x)
        {
            assert(pos <= _finish);
            // 空间不够先进行增容
            if (_finish == _endOfStorage)
            {
                size_t len = pos - _start;
                size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
                reserve(newCapacity);
                // 如果发生了增容，需要重置pos
                pos = _start + len;
            }
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = x;
            ++_finish;
            return pos;
        }

1. 参数和前提条件
        参数：
                pos：插入位置的迭代器，指向希望插入新元素的地方。
                x：要插入的元素。
        前提条件：
                使用 assert 确保 pos 不超过 _finish，即插入位置在有效范围内。
2. 增容逻辑
        判断是否需要增容：
                检查 _finish 是否等于 _endOfStorage，即当前是否已满。
                如果已满，计算新的容量（当前容量的两倍，或初始为 1）。
                调用 reserve 函数来分配新的内存。
        调整插入位置：
                如果进行了增容，需要重新计算插入位置 pos，因为内存可能已改变，pos 应该重新定位。
3. 元素移动
        移动元素：
                从 _finish - 1 开始，向后移动元素，将每个元素向右移动一位，以腾出插入位置。
                通过循环将元素依次复制到它们的下一个位置，直到移动到 pos。
4. 插入元素
        在计算得出的 pos 位置插入新元素 x。
5. 更新结束指针
        增加 _finish 的值，表示 vector 的大小已增加。
6. 返回值
        返回插入位置的迭代器 pos，以便后续操作或链式调用。

4.5 erase

 // 返回删除数据的下一个数据
 // 方便解决:一边遍历一边删除的迭代器失效问题

 iterator erase(iterator pos)
 {
     // 挪动数据进行删除
     iterator begin = pos + 1;
     while (begin != _finish)
     {
         *(begin - 1) = *begin;
         ++begin;
     }
     --_finish;
     return pos;
 }

5. vector对象的访问

        T& operator[](size_t pos)
        {
            return _start[pos];
        }

        const T& operator[](size_t pos)const
        {
            return _start[pos];
        }

6. 测试模拟实现的vector

6.1 测试vector的构造

void Text_my_vector1()
{
my_vector::vector<int> ret1;
my_vector::vector<int> ret2(3, 666);
my_vector::vector<int> ret3(ret2);
my_vector::vector<int> ret4 = ret2;

for (auto ch : ret1)
cout << ch << endl;
cout << endl;

for (auto ch : ret2)
cout << ch << endl;
cout << endl;

for (auto ch : ret3)
cout << ch << endl;
cout << endl;

for (auto ch : ret4)
cout << ch << endl;
cout << endl;
}

6.2 测试vector的容量操作

void Text_my_vector2()
{
my_vector::vector<int> ret(100, 999);
cout << ret.size() << endl;
cout << ret.capacity() << endl;
cout << endl;

ret.push_back(666);
cout << ret.size() << endl;
cout << ret.capacity() << endl;
cout << endl;

ret.reserve(10);
cout << ret.capacity() << endl;
cout << endl;

ret.reserve(100);
cout << ret.capacity() << endl;
cout << endl;

ret.reserve(1000);
cout << ret.capacity() << endl;
cout << endl;

ret.resize(100, 1);
cout << ret.size() << endl;
cout << ret.capacity() << endl;
cout << endl;

ret.resize(10, 2);
cout << ret.size() << endl;
cout << ret.capacity() << endl;
cout << endl;

}

6.3 测试vector的修改

void Text_my_vector3()
{
my_vector::vector<int> ret1(10, 1);
my_vector::vector<int> ret2(6, 666);

//迭代器遍历
my_vector::vector<int>::iterator it = ret1.begin();
while (it < ret1.end())
{
cout << *it << " ";
it++;
}
cout << endl;

//for范围遍历
for (auto ch : ret2)
cout << ch << " ";
cout << endl;

ret1.push_back(666);
ret1.push_back(666);
ret1.push_back(666);

for (auto ch : ret1)
cout << ch << " ";
cout << endl;
for (auto ch : ret2)
cout << ch << " ";
cout << endl;


for (auto ch : ret1)
cout << ch << " ";
cout << endl;
for (auto ch : ret2)
cout << ch << " ";
cout << endl;

ret1.insert(ret1.begin() + 3, 888);
ret2.insert(ret1.begin() + 3, 888);

for (auto ch : ret1)
cout << ch << " ";
cout << endl;
for (auto ch : ret2)
cout << ch << " ";
cout << endl;

ret1.erase(ret1.end() - 9);
ret2.erase(ret1.end() - 9);

for (auto ch : ret1)
cout << ch << " ";
cout << endl;
for (auto ch : ret2)
cout << ch << " ";
cout << endl;
}

6.4 测试vector对象的访问

void Text_my_vector4()
{
my_vector::vector<int> ret(10, 888);
cout << ret[7] << endl;
ret.insert(ret.begin() + 7, 666);
cout << ret[7] << endl;
}

原文地址：https://blog.csdn.net/wer24_25/article/details/142425783

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：什么是反射，反射用途，spring哪些地方用到了反射，我们项目中哪些地方用到了反射
下一篇：穿越数字迷雾：探索IT领域的无限可能

【Android】使用Room数据库解决本地持久化
Android数据库的使用
阅读更多2024-09-24
MySQL篇（管理工具）
e 选项可以在MySQL客户端执行SQL语句，而不用连接到MySQL数据库再执行，对于一些批处理脚本，这种。执行上述指令，会出错，数据不能完成备份，原因是因为我们所指定的数据存放目录/root，MyS
阅读更多2024-09-24
丢失照片/消息/文件，当发现没有备份 Android 手机数据时急救方法
当人们发现他们没有备份 Android 手机数据时，通常为时已晚。但是，我们都不想永久丢失珍贵的照片，消息和其他文件。这就是为什么您应该检查遵循 5 大免费 Android 数据恢复工具和最佳替代
阅读更多2024-09-24
力扣 —— 删除有序数组中的重复项
两个指针，一个是游标的功能，负责遍历整个数组，一个是定位器的功能，如果有相等的则表示定位器目前指向的元素是重复的，定位器不动，等待游标往下找到不重复的数填充进来，因为游标会遍历整个数组且总是比定位器快
阅读更多2024-09-24
k8s服务发布
为某个节点添加标签 Label在 deployment 或其他控制器中指定将 Pod 部署到该节点该示例为 my-service:80 即可访问到具有 app=nginx 标签的 Pod 的80
阅读更多2024-09-24
Python 去掉文件后缀名
今天遇到了一个问题，去掉文件的后缀名，这里特来对这个问题记录一下。
阅读更多2024-09-24
C++二叉搜索树
二叉搜索树的概念二叉搜索树中可以⽀持插⼊相等的值，也可以不支持插入相等的值，具体看使用场景定义总得来说二叉搜索树他的左子树和根还有右子树的值形成一个阶梯状。
阅读更多2024-09-24
uniapp打包自动上传小程序后台
5、package.json中修改打包命令。3、将生成的密钥放置到项目根目录。6、打包运行，自动上传成功。
阅读更多2024-09-24
Ubuntu的基本用法与指令（为后面学习ROS打基础）
Ubuntu的基本用法与指令
阅读更多2024-09-24
数据结构与算法——Java实现 15.习题——判断回文链表
给你一个单链表的头节点head，请你判断该链表是否为回文链表如果是，返回true；否则，返回false。
阅读更多2024-09-24

C++vector类的模拟实现

前置说明

1. vector的迭代器

2. vector的构造和析构

2.1 构造函数:

2.2 赋值操作符重载

2. 3 析构函数

3. vector容量的操作

3.1 size

3.2 capcity

3.3 reserve

3.4 resize

4. vector的修改

4.1 push_back

4.2 pop_back

4.3 swap

4.4 insert

4.5 erase

5. vector对象的访问

6. 测试模拟实现的vector

6.1 测试vector的构造

6.2 测试vector的容量操作

6.3 测试vector的修改

6.4 测试vector对象的访问

相关文章