• vector的模拟实现

    vector的模拟实现

    一、整体框架

    1、代码

    namespace snow
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
    private:
    	iterator _start = nullptr;
    	iterator _finish = nullptr;
    	iterator _endOfStorage = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    2、实现原理

    • 使用命名空间的方式，避免模拟实现的vector类与C++库里面的vector冲突。
    • 使用模板的方式定义vector类，使vector作为模本能实例化出不同类型的类。
    • 使用typedef将指针名重定义，在下方作为迭代器使用。
    • 使用三个成员变量记录vector中数据的位置，_start 指向数据块的开始，_finish 指向有效数据的尾部，_endOfStorage 指向存储容量的尾部。将这三个成员变量用缺省值的方式使它们在初始化列表时进行初始化，这样在下面的构造函数中就不用自己写把它们初始化为空指针的代码了。

    3、注意

    • typedef定义的结尾需要加“;”否则下一条语句将会定义错误。

    二、迭代器操作函数

    1、代码

    iterator begin()
{
    return _start;
}

iterator end()
{
    return _finish;
}

const_iterator cbegin() const
{
    return _start;
}

const_iterator cend() const
{
    return _finish;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    2、实现原理

    • 因为_start 指向数据块的开始，_finish 指向有效数据的尾部，类型是用指针实现的迭代器，所以直接返回对应的变量即可。
    • 因为vector对象可能是被const修饰的，这时它如果要调用上面的迭代器函数，是权限的放大，即无法调用。所以，需要重载一个this指针被const修饰，返回类型也被const修饰的重载函数。

    三、容量函数

    1、代码

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    2、实现原理

    • 因为两个指针相减得到的结果是两个指针之间元素的个数，所以在上方的两个函数中，用对应的变量相减即可。
    • 因为调用那两个函数的对象可能是用const修饰的，如果上方的两个函数没有加const，则被const修饰的对象将无法调用它们。所以，上面两个函数都加上const，这样，不管对象有没有被const修饰都能调用它们。

    四、reserve函数

    1、代码

    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    2、实现原理

    • 当传入的参数n大于capacity()时，说明是扩容，才进行操作，否则不进行。
    • 用变量oldSize记录实际存储的元素数量，方便下面更新_finish，当对象有数据时，即_start不为空时，将数据拷贝出来，否则直接更新三个成员变量的值。

    3、注意

    • oldSize需要赋值为size()，而不是capacity()。
    • 拷贝数据时，需要对元素一一赋值而不能用memcpy进行拷贝，因为如果用memcpy拷贝的话，是值拷贝，如果元素是自定义类型时，拷贝的是原来的空间，而tmp是新开辟出来的空间，而自定义类型对象的成员变量也需要新开辟空间，即用memcpy进行拷贝将会有浅拷贝的情况发生。
    • _finish不能用_start + size()赋值，因为size()是_finish - _start，即最终_finish会赋值为_finish，使_finish赋值错误。

    五、resize函数

    1、代码

    void resize(size_t n, const T& value = T())
{ 
    if (n <= size())
    {
        _finish = _start + n;
        return;
    }
    if (n > capacity())
        reserve(n);
    /*for (size_t i = size(); i < n; ++i)
    {
        *_finish = value;
        ++_finish;
    }*/

    iterator it = _finish;
    _finish = _start + n;
    while (it != _finish)
    {
        *it = value;
        ++it;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    2、实现原理

    • 形参value 的缺省值为T()，如果是自定义类型则直接调用它的构造函数构造变量。
    • 当n小于或等于size()时，说明需要删除数据，直接将_finish 修改就行。
    • 当n大于capacity()说明需要扩容，复用reserve函数进行扩容。
    • 如果执行到下边的代码，说明已经扩容了，所以需要对多出来的空间进行赋值，可以使用迭代器进行赋值，也可以采用循环的方式，即代码中被注释掉的部分。

    3、注意

    • 形参value 的缺省值不能是0，而应该用T()，当value为自定义类型时，编译器会调用它的构造函数创建变量，而如果是内置类型的话，也算是调用它的构造函数。虽然C++中没有规定内置类型的构造函数，但此处是采用模板的方式，即可以使用。

    六、insert函数

    1、代码

    iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);
    if (_finish == _endOfStorage)
    {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2;);
        pos = _start + len;
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    2、实现原理

    • 使用assert对pos进行断言，当它的位置非法时，不执行下面的操作。
    • 当_finish等于_endOfStorage时，进行扩容，然后移动数据和插入数据。

    3、注意

    • 扩容传参数时，不能传capacity() * 2，因为capacity()可能为0，而如果capacity()为0，则扩容操作将会出错。
    • 需用len保存pos与_start的相对位置，因为下面的扩容操作会使迭代器失效，而pos可能还在没扩容之前的位置，而三个成员变量的值已经被修改了，这时下面的循环操作将出错。
    • 循环判断条件中，end可以等于pos，因为它们都是迭代器，这里用的是指针，所以不会有size_t类型变量为0时减一变为整型最大值而导致程序出错的情况发生。

    七、erase函数

    1、代码

    iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    /*for (iterator it = pos; it < _finish - 1; ++it)
    {
        *it = *(it + 1);
    }
    --_finish;
    return pos;*/

    iterator start = pos + 1;
    while (start != _finish)
    {
        *(start - 1) = *start;
        ++start;
    }
    --_finish;
    return pos;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    2、实现原理

    • 使用assert对pos进行断言，当它的位置非法时，不执行下面的操作。
    • 然后是移动数据，上方被注释的代码和下边代码的效果是差不多的，只不过被注释的代码比较容易理解。

    八、构造函数

    1、代码

    vector()
{}

vector(int n, const T& value = T())
{
    reserve(n);
    /*for (size_t i = 0; i < n; ++i)
    {
        *_finish = value;
        ++_finish;
    }*/

    while (n--)
    {
        push_back(value);
    }
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    2、实现原理

    • 第一个构造函数的作用是作为无参构造函数，即不传参数也能构造对象。
    • 第二个构造函数是构造一个数据为n个value值的对象，此处value的缺省值也需用T()，作用和上方说过的T()一致。
    • 对元素的初始化可以用循环，也可以直接复用push_back函数进行尾插，只不过循环赋值比较麻烦一点，代码中被注释的部分就是用循环进行赋值的。
    • 第三个构造函数是用迭代器构造对象，操作和前一个构造函数差不多，只不过迭代器的判断条件得是first != last。注释掉的代码的效果也是相同的，只不过复用push_back直接进行尾插比较方便，这样就无需自己对_finish进行修改，并且代码更加简洁。

    3、注意

    • 第一个构造函数中不用写代码是因为成员变量的声明中已经给了缺省参数，而插入元素之类的函数可以自己调用扩容函数。
    • 第二个构造函数可以重载多个不同类型的形参n，因为编译器会默认选择最合适的函数去调用，如果n不是int类型而是别的类型的，则编译器可能会用第三个构造函数模板去实例化出一个构造函数，而在实例化出来的函数中，对内置类型（如整型之类）的变量进行解引用是错误的。
    • 第三个构造函数模板中的InputIterator和本类中的iterator没有多大的关系，InputIterator只是一个模板参数，但不能用iterator替代InputIterator。InputIterator的存在是为了使第三个构造函数成为模板，即它的迭代器形参可以用其他自定义类型的迭代器进行传参。

    九、swap函数和赋值运算符重载函数

    1、代码

    void swap(vector<T>& v)
{
    ::swap(_start, v._start);
    ::swap(_finish, v._finish);
    ::swap(_endOfStorage, v._endOfStorage);
}
vector<T>& operator= (vector<T> v)
{
    swap(v);
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    2、实现原理

    • 实现一个swap交换函数，方便后续两个vector对象的交换。
    • 使用std::swap或::swap的意思是使用C++库里面的swap函数，因为交换的是内置类型的变量，所以调用库里面的swap函数进行交换会比较方便。
    • 赋值运算符重载函数中，形参用传值的方式，这样，在赋值的时候就会构造一个对象，然后将这个对象和本对象直接交换，等到函数结束，形参的变量（即本对象之前的内容）将自动调用析构函数对空间进行释放。

    十、拷贝构造函数

    1、代码

    vector(const vector<T>& v)
{
    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    2、实现原理

    • 本函数是为了用一个已存在的对象创建一个“相同”的对象，所以开辟的空间和被拷贝的对象的空间是一样大的，而下面将对本对象的成员变量进行修改。
    • 接着就是拷贝数据和修改本对象的成员变量。

    3、注意

    • 拷贝数据时，元素需要一个一个地拷贝，不能用memcpy之类的进行拷贝，因为对象的类型，即对象的元素可能是自定义类型的，如果用memcpy之类的进行拷贝，那拷贝出来的对象可能只有外层是深拷贝，而内层还是浅拷贝。这样，在析构的时候编译器会奔溃。
    • 用等号进行赋值时，需要类里面有赋值运算符的重载函数与深拷贝的拷贝构造函数，否则，在编译器进行调用时，会一直调用被拷贝对象的拷贝构造函数直到最后一层，而本类如果没有赋值运算符的重载函数和深拷贝的拷贝构造函数，编译器就会报错和调用自动生成的，调用自动生成的拷贝构造函数会将数据采用值拷贝的方式进行拷贝，即浅拷贝。

    十一、析构函数

    1、代码

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

    • 1
    • 2
    • 3
    • 4
    • 5

    2、实现原理

    • 因为开辟空间时是用new[]进行开辟的，所以析构时也要使用对应的delete[]对空间进行释放。
    • 最后为了安全，将三个成员变量都置为空。

    十二、模拟实现vector与测试的代码

    #pragma once
#include
#include
using namespace std;

namespace snow
{
    template<class T>
    class vector
    {
    public:
        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;
        }

        vector()
        {}

        vector(int n, const T& value = T())
        {
            reserve(n);
            /*for (size_t i = 0; i < n; ++i)
            {
                *_finish = value;
                ++_finish;
            }*/

            while (n--)
            {
                push_back(value);
            }
        }

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

            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        vector(const vector<T>& v)
        {
            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();
        }

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

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

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

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

        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;
            }
        }

        void resize(size_t n, const T& value = T())
        { 
            if (n <= size())
            {
                _finish = _start + n;
                return;
            }
            if (n > capacity())
                reserve(n);
            /*for (size_t i = size(); i < n; ++i)
            {
                *_finish = value;
                ++_finish;
            }*/

            iterator it = _finish;
            _finish = _start + n;

            while (it != _finish)
            {
                *it = value;
                ++it;
            }
        }

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

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

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

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

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

        iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start && pos <= _finish);
            if (_finish == _endOfStorage)
            {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2;);
                pos = _start + len;
            }
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = x;
            ++_finish;
            return pos;
        }

        iterator erase(iterator pos)
        {
        	assert(pos >= _start && pos < _finish);
            /*for (iterator it = pos; it < _finish - 1; ++it)
            {
                *it = *(it + 1);
            }
            --_finish;
            return pos;*/

            iterator start = pos + 1;
            while (start != _finish)
            {
                *(start - 1) = *start;
                ++start;
            }
            --_finish;
            return pos;
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _endOfStorage = nullptr;
    };

    
    void Test_vector1()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);

        cout << v.size() << endl;
        cout << v.capacity() << endl;
        
        v.push_back(5);

        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        cout << v.size() << endl;
        cout << v.capacity() << endl;
    }
    void Test_vector2()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);

        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

        v.pop_back();
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        cout << v.size() << endl;
        cout << v.capacity() << endl;

        cout << v[1] << endl;

        vector<int> v2(5, 10);
        for (auto e : v2)
        {
            cout << e << " ";
        }
        cout << endl;

        v2.swap(v);
        for (auto e : v2)
        {
            cout << e << " ";
        }
        cout << endl;

        
    }
    void Test_vector3()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);

        const vector<int> v2(v);
        vector<int>::const_iterator it = v2.cbegin();
        while (it != v2.cend())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;

        const vector<int> v3(v2);
        it = v2.cbegin();
        while (it != v2.cend())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        it = v3.cbegin();
        while (it != v3.cend())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    void Test_vector4()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);

        vector<int>::iterator it = v.begin();
        it = v.insert(++it, 20);
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        cout << *it << endl;

        it = v.erase(it);
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        cout << *it << endl;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 本文只是对vector的一些常用与常见的函数模拟实现与讲解，一些比较简单的函数没有讲解但在上方的代码中都有模拟实现的代码。

    本文到这里就结束了，如有错误或者不清楚的地方欢迎评论或者私信
    创作不易，如果觉得博主写得不错，请务必点赞、收藏加关注💕💕💕

  • 相关阅读:
    PIL库的crop函数（图片裁剪操作）
    Elasticsearch的介绍与安装
    全局变量和静态变量的初始化
    【NIPS 2017】PointNet++：度量空间中点集的深层次特征学习
    挑战10个最难的Java面试题（附答案）【上】
    L1-030 一帮一(Java语言)-天梯赛
    webpack升级，3升5
    小程序生命周期函数
    Playwright官方文档要点记录(java)
    PTA：数据结构实验 一 链队列
  • 原文地址：https://blog.csdn.net/Snow_Dragon_L/article/details/133957764