【C++模拟实现】vector的模拟实现

【C++模拟实现】vector的模拟实现

---

作者：爱写代码的刚子

时间：2023.9.1

前言：模拟实现系列好久没更了，前来补更。

vector模拟实现的标准代码

namespace test
{
    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()
        {
            return _start;
        }
        const_iterator cend() const
        {
            return _finish;
        }

        vector()
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endOfStorage(nullptr)
        {}
        vector(int n, const T& value = T())
        {
            resize(n,value);
        }
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endOfStorage(nullptr)
        {
            //存疑，是否要reserve
            while(
                    first!=last)
            {
                push_back(*first);
                ++first;
            }
        }
        vector(const vector<T>& v)//这里是引用
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endOfStorage(nullptr)
        {
            reserve(v.capacity());
            for(auto e:v)
            {
                push_back(e);
            }
        }
        vector<T>& operator= (vector<T> v)
        {
            swap(v);
            return *this;
        }
        ~vector()
        {
            delete[] _start;
            _start = nullptr;
            _finish = nullptr;
            _endOfStorage = nullptr;
        }

        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _endOfStorage - _start;
        }
        void reserve(size_t n)
        {
            if(n>capacity()) {
                iterator tmp = new T[n];
                //拷贝数据(手动)
                int sz = size();
                if(_start) {
                    for (int i = 0; i < sz; i++) {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;//一定要记得
                }

                _start = tmp;
                _finish = _start + sz;
                _endOfStorage = _start + n;
            }

        }
        void resize(size_t n, const T& value = T())
        {
            if(n<capacity())
            {
                _finish=_start + n;
            }
            else
            {
                reserve(n);
                while(_finish!=_start+n)
                {
                    *_finish=value;
                    ++_finish;
                }

            }
        }


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


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

        }
        void pop_back()
        {
            erase(--end());//注意是--end(),end()指向的是数据的下一个位置
        }
        void swap(vector<T>& v)
        {
            std::swap(v._start,_start);
            std::swap(v._finish,_finish);
            std::swap(v._endOfStorage,_endOfStorage);

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

        }
        template<class U>
        bool compare(const U& a,const U& b) const
        {
            return a<=b;
        }

        template<>
        bool compare<string>(const string& a,const string& b) const
        {
            int n=min(a.size(),b.size());
            int i=0;
            while(i<n)
            {
                if(a[i]>b[i])
                {
                    return false;
                }
                else if(a[i]<b[i])
                {
                    return true;
                }
                ++i;
            }
            if(a.size()<b.size())
            {
                return true;
            }

            return false;
        }


        bool operator<(const vector<T>& v) const
        {
            int n=min(size(),v.size());
            int i=0;
            while(i<n)
            {
                if(!compare<T>(_start[i],v[i])&&_start[i]!=v[i]) //a=b return false;
                {
                    return false;
                }
                else if(compare<T>(_start[i],v[i])&&_start[i]!=v[i])
                {
                    return true;
                }
                ++i;
            }
            if(v.size()>size())
            {
                return true;
            }

            return false;
        }

    private:
        iterator _start; // 指向数据块的开始
        iterator _finish; // 指向有效数据的尾
        iterator _endOfStorage; // 指向存储容量的尾
    };
}
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

vector模拟实现中的要点

insert和erase会涉及到迭代器失效的问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装，比如:vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。

有关迭代器失效的几种做法

• 对于vector可能会导致其迭代器失效的操作有:

  1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如:resize、reserve、insert、assign、 push_back等。

     出错原因:以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉， 而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

     解决方式:在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。

  2. 指定位置元素的删除操作–erase

     erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是:如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。(但Linux下g++可能不一样，因为迭代器使用了原生指针，没有像vs一样进行封装)

​

**迭代器失效解决办法:在使用前，对迭代器重新赋值即可。 **

涉及到底层空间改变时，需要考虑重置迭代器

vector深度剖析

关于模版template< class InputIterator >

为什么不使用自己之前定义的iterator？

• 若使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器
• 重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器

使用memcpy拷贝问题

为什么在reserve接口中不能直接使用memcpy进行拷贝？

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，memcpy的拷贝实际是浅拷贝。

所以在模版模拟实现中慎用memcpy！！！

结论:如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

---

【附】：范围for是C++11的