【C++】vector模拟实现

🔥个人主页： Forcible Bug Maker

🔥专栏： STL || C++

目录

• 前言
• 🔥vector需要实现的接口函数
• 🔥vector的模拟实现
• • ==swap交换==
  • ==默认成员函数==
  • ==迭代器接口==
  • ==reserve和resize==
  • ==size和capacity==
  • ==operator[ ]下标获取==
  • ==push_back和pop_back==
  • ==插入（insert）和删除（erase）==
  • 结语

    前言

    本篇博客主要内容：STL库中vector的模拟实现。

    在之前完成string以及学习了vector一些接口函数的基础上，这个vector的实现相当于是一个奖励内容，并不困难。不过我们这里vector底层实现和上次string的有所不同，是通过三个指针_start，_finish和_end_of_storage来维护这个模板类的。相信在看完今天vector的实现之后，能对C++的迭代器有更深的了解。

    🔥vector需要实现的接口函数

    由于涉及到了模板的内容，我们这次不会将vector实现的声明和定义分离。在后期模板进阶的阶段会进一步解答此问题，盲目将模板类的声明定义分离是很容易出错的（在对模板这部分内容不熟练的情况下）。

    看看需要实现的接口函数：

    #pragma once
    #include
    #include
    #include
    using namespace std;
    namespace ForcibleBugMaker
    {
        template
        class vector
        {
        public:
            // 这里vector的迭代器是一个原生指针
            typedef T* iterator;
            typedef const T* const_iterator;
            //迭代器获取接口
            iterator begin();
            iterator end()
            const_iterator cbegin()const;
            const_iterator cend() const;
             // 交换vector对象
            void swap(vector& v);
            // 构造函数，析构函数以及赋值运算符重载
            vector();
            vector(int n, const T& value = T());
            template
            vector(InputIterator first, InputIterator last);
        
            vector(const vector& v);
            vector& operator=(vector v);
            ~vector();
            // 容量获取和调整接口
            size_t size() const;
            size_t capacity() const;
            void reserve(size_t n);
            void resize(size_t n, const T& value = T());
            // 元素获取
            T& operator[](size_t pos);
            const T& operator[](size_t pos)const;
            // 插入和删除元素
            void push_back(const T& x);
            void pop_back();
            iterator insert(iterator pos, const T& x);
            iterator erase(iterator pos);
        private:
            iterator _start = nullptr; // 指向数据块的开始
            iterator _finish = nullptr; // 指向有效数据的尾
            iterator _end_of_storage = nullptr; // 指向存储容量的尾
        };
    }
    

    本篇建议在string类实现的基础上进行，不然有些概念可能不太好理解。C++中包含交换函数swap，在命名空间std中，可以直接使用。在vector的实现中，你可能发现与string不同，接口函数大多使用迭代器（指针）来实现，传入和传出的参数基本上也都是迭代器。这么做是为了给后面一系列的STL容器打一个基础，大家要逐渐习惯这样的实现方式。

    🔥vector的模拟实现

    接下来进入主要内容，按照上面的接口列表逐一实现。

    本篇都是直接在vector模板类内部实现，不用手动圈定命名空间。

    swap交换

    既然是用三个指针维护的，那么交换这三个指针即可完成交换。

    void swap(vector& v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_end_of_storage, v._end_of_storage);
    }
    

    默认成员函数

    构造函数：

    这里我们提供了三种重载，分别是：

    // 无参构造
    vector()
    {}
    // 构造包含n个value的vector对象
    vector(int n, const T& value = T())
    {
        reserve(n);
        for (int i = 0; i push_back(value);
        }
    }
    // 通过迭代器区间构造vector对象
    template
    vector(InputIterator first, InputIterator last)
    {
        InputIterator it = first;
        while (it != last) {
            this->push_back(*it);
            ++it;
        }
    }
    

    学习过vector的使用，应该也能看懂。其中有几个还待实现的接口函数，如push_back，reserve等。

    对于第一个无参构造，其实编译器默认实现的也有相同的效果，但是一旦你实现了下面两个构造，那么编译器就不会生成默认的了。C++提供了一种语法，可以无视你的重载构造，强制生成一个编译器默认构造，所以，下面这样写也是正确的的。

     // 强制编译器生成默认无参构造
     vector() = default;
     vector(int n, const T& value = T())
     {
         reserve(n);
         for (int i = 0; i push_back(value);
         }
     }
     template
     vector(InputIterator first, InputIterator last)
     {
         InputIterator it = first;
         while (it != last) {
             this->push_back(*it);
             ++it;
         }
     }
    

    第二个构造中缺省参数T()表示的是构造一个T类型的对象，赋值给value。在C++中不但T()可以用于表示自定义类型变量的无参构造，也同样可以表示内置类型的无参构造（C语言中并不支持这样做）。

    如下：

    int a = int();
    int b = int(3);
    cout 
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }
    
        reserve(v.capacity());
        int size = v.size();
        for (int i = 0; i  
    插入（insert）和删除（erase）
     
    这两个函数需要传入的参数都为迭代器，从vector中间部分插入和删除元素。
     
    插入：会将我们传入的元素插入到迭代器指向的对象之前；如果迭代器指向end()，则功能等同于尾插。
    删除：将传入迭代器指向的元素删除。
     
    iterator insert(iterator pos, const T& x)
    {
        assert(_start 
            int gap = pos - _start;
            reserve(size() == 0 ? 4 : size() * 2);
            pos = _start + gap;
        }
        iterator it = _finish;
        while (it  pos) {
            *it = *(it - 1);
            --it;
        }
        *it = x;
        ++_finish;
        return it + 1;
    }
    iterator erase(iterator pos)
    {
        assert(_start 
            *(itCur - 1) = *itCur;
            ++itCur;
        }
        --_finish;
        return _start + size;
    }