C++STL——vector类与模拟实现

vector

vector是表示可变大小数组的序列容器,就像数组一样，采用连续存储空间来存储元素，功能和数组类似，但是vector可以管理动态内存，并且在vector中的元素可以是自定义类型。
vector的文档介绍：


arr与str中已经存放进了我们初始化的数据。

常用接口介绍

这里很多都和string的接口相似，就不一一介绍了

初始化

vector (const allocator_type& alloc = allocator_type());//无参构造函数
参数：是库里面写的空间配置器组件
vector (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());//构造并且初始化n个val
参数：第一个是数据数量，第二个是数据本身，第三个是空间配置器组件
template
vector (InputIterator first, InputIterator last，const allocator_type& alloc = allocator_type());//使用迭代器进行初始化构造
参数：第一个是头第二个是尾，第三个是空间配置器组件
vector (const vector& x);//拷贝构造

#include 
#include 
using namespace std;

int main()
{
	vector<int>arr;
	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i];
	}
	cout << endl;
	vector<int>arr1 = { 1,2 };
	for (int i = 0; i < arr1.size(); i++)
	{
		cout << arr1[i];
	}
	cout << endl;
	vector<int>arr2(5, 2);
	for (int i = 0; i < arr2.size(); i++)
	{
		cout << arr2[i];
	}
	cout << endl;

	vector<int>arr3(arr1);
	for (int i = 0; i < arr3.size(); i++)
	{
		cout << arr3[i];
	}
	cout << endl;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	vector<int>arr4(arr.begin(), arr.end());
	for (auto e : arr4)
	{
		cout << e;
	}
	cout << endl;
	return 0;
}
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

reserve与resize

的
这个和string的类似，都是先开辟一处指定空间大小，但是不会缩容：

#include 
#include 
using namespace std;

int main()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	cout << arr.capacity() << endl;
	arr.reserve(10);//size并不会变大
	cout << arr.capacity() << endl;
	arr.reserve(3);
	cout << arr.capacity() << endl;//不缩容
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里要注意一下，val这个参数是一个模板，缺省值是一个匿名的模板的对象，因为传过来的不一定就是内置类型，很有可能是自定义类型。

#include 
#include 
using namespace std;

int main()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);

	arr.resize(8);//空位补0
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl << arr.capacity() << endl;
	arr.resize(15, 1);//空位补1
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl << arr.capacity() << endl;

	arr.resize(3);//减小长度但不缩容
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl << arr.capacity() << endl;
	return 0;
}
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

assign

#include 
#include 
using namespace std;

int main()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	for (auto e : arr)
	{
		cout << e << ' ';
	}
	cout << endl;
	arr.assign(10, 1);
	for (auto e : arr)
	{
		cout << e << ' ';
	}
	cout << endl;
	vector<int>arr1;
	arr1.push_back(4);
	arr1.push_back(5);
	arr1.push_back(6);
	arr1.push_back(7);
	arr.assign(arr1.begin(), arr1.end());
	for (auto e : arr)
	{
		cout << e << ' ';
	}
	cout << endl;
	string str("hello world");
	arr.assign(str.begin(), str.end());
	for (auto e : arr)
	{
		cout << e << ' ';
	}
	cout << endl;
	return 0;
}
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

缩容接口

最好不要缩容，因为vector设计理念就是不动空间，空间换时间，代价很大。

和原来一样，需要开辟一块新空间，然后释放掉原来的空间，再进行拷贝，此函数是为了节省空间。

#include 
#include 
using namespace std;

int main()
{
	vector<int>arr;
	arr.push_back(0);
	arr.push_back(0);
	arr.push_back(0);
	arr.reserve(10);
	cout << arr.capacity() << endl;
	arr.shrink_to_fit();
	cout << arr.capacity() << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

算法库中的find

查看文档发现vector中并没有查找的函数，是但是算法库为STL中提供了一个查找的函数，不然每一个容器都要写查找岂不是很麻烦？

模板是类模板，函数的参数使用类模板与迭代器实现的。

#include 
#include 
#include 
using namespace std;

int main()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);

	vector<int>::iterator p = find(arr.begin(), arr.end(), 3);
	if(p != arr.end())
		arr.insert(p, 10);//在3的位置进行头插
	for (auto e : arr)
	{
		cout << e << ' ';
	}
	cout << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

vector的底层小部分框架

在模拟实现string的时候，成员变量有三个，存储字符串的空间位置，此对象的字符串有效长度大小和有效空间大小。
如果去看库中实现的vector源码，我们会发现成员变量最主要的有三个：

一是start，指向了这组数的开头。
二是finish，指向有效数据的最后一个位置的下一个位置，这样与start相减就是有效数据的长度了。
三是end_of_storage，指向了有效空间的末尾。
类型是* iterator。

模拟实现vectot

模拟vector的整体代码

#include 
#include 
#include 
using namespace std;
namespace baiye
{
    template<class T>
    class vector
    {
    public:

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

        typedef T* iterator;
        typedef const T* const_iterator;

        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }
        
        // construct and destroy

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

        vector(size_t n, const T& value = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                push_back(value);
            }
        }
        vector(int n, const T& value = T())//这里有一个参数n为int类型是防止传参是两个整形，如果是size_t需要隐式类型转换
            : _start(nullptr)              //这会导致调用的不是这个构造函数而是带有模板的构造函数了
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                push_back(value);
            }
        }

        template<class InputIterator>
        vector(InputIterator first, InputIterator last)//模板的优先级大于隐式类型转换
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        vector(const vector<T>& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            vector<T>gcc(v.begin(), v.end());
            swap(gcc);
        }

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

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

        // capacity

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

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

        void reserve(size_t n)
        {
            if (n > capacity())
            {
                T* p = new T[n];
                int a = size();
                if (_start)
                {
                    for (int i = 0; i < a; i++)
                    {
                        p[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = p;
                _finish = _start + a;
                _endOfStorage = _start + n;
            }
        }

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

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

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

        ///modify/

        void push_back(const T& x)
        {
            if (_finish == _endOfStorage)
            {
                int sum = capacity() == 0 ? 4 : 2 * capacity();
                reserve(sum);
            }
            *_finish = x;
            _finish++;
        }
        bool empty() const
        {
            return  !(_finish - _start);
        }
        void pop_back()
        {
            assert(!empty());
            _finish--;
        }

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

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

        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos < _finish);
            iterator p = pos + 1;
            while (p < _finish)
            {
                *(p - 1) = *p;
                p++;
            }
            _finish--;
            return pos;
        }
        void clear()
        {
            _finish = _start;
        }
    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
242
243
244
245

不过，在模拟vector的过程中，最致命的问题有两个。

迭代器失效问题

在实现到vector的接口insert时，我写的代码是这样的。

iterator insert(iterator pos, const T& x)
{
    assert(pos <= _finish);
    assert(pos > _start);
    if (_finish == _endOfStorage)
    {
        int sum = capacity() == 0 ? 4 : 2 * capacity();
        reserve(sum);
    }
    iterator p1 = _finish;
    while (p1 > pos)
    {
        *p1 = *(p1 - 1);
        p1--;
    }
    *pos = x;
    ++_finish;
    return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在测试的时候发现结果是这样的：

然后我进行了调试发现：

上面是最初的位置。
然后向下走，需要扩容。

当扩容之后我们发现，vector的成员变量地址都变了，但是pos指向的还是原来的位置，导致pos指向的内容也就变成了我们上面看到的随机值。
这就是扩容需要重新开辟一块空间并且释放掉原来的空间导致的迭代器失效问题。
我们传过来的参数pos是没有重新分配空间的地址，那么在扩容时失效应该如何避免呢？
这里只需要记录原来pos与_start的距离，然后重新让pos指向有效位置即可。

iterator insert(iterator pos, const T& x)
{
    assert(pos <= _finish);
    assert(pos > _start);
    if (_finish == _endOfStorage)
    {
    	int n = pos - _start;
        int sum = capacity() == 0 ? 4 : 2 * capacity();
        reserve(sum);
        pos = _start + n;
    }
    iterator p1 = _finish;
    while (p1 > pos)
    {
        *p1 = *(p1 - 1);
        p1--;
    }
    *pos = x;
    ++_finish;
    return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

迭代器失效归根结底就是野指针的问题。
那么再来看这一段代码：

int main()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl;
	vector<int>::iterator p = find(arr.begin(), arr.end(), 3);
	if (p != arr.end())
		arr.insert(p, 5);//这里会发生扩容
	p++;//这里再次对于p进行改动会怎么样？
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里也是野指针的问题，所以这里记得利用返回值。

int main()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl;
	vector<int>::iterator p = find(arr.begin(), arr.end(), 3);
	if (p != arr.end())
		p = arr.insert(p, 5);
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl;

	(*p)++;//这里再次对于p进行改动会怎么样？
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl;
	return 0;
}
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

至于为什么insert这个接口的函数pos参数为什么不是引用，这是因为如果是引用就要考虑传值时候的权限放大与缩小的问题了。
现在来看看第二种迭代器失效的问题：
在实现erase接口的时候代码是这样写的：

iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);
    iterator p = pos + 1;
    while (p < _finish)
    {
        *(p - 1) = *p;
        p++;
    }
    _finish--;
    return pos；
}
1
2
3
4
5
6
7
8
9
10
11
12
13

测试了一下没什么问题：

那么如果这样呢（这里先用库里面的vector来测试）

int main()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl;
	vector<int>::iterator p = find(arr.begin(), arr.end(), 3);
	arr.erase(p);
	for (auto e : arr)
	{
		cout << e;
	}
	cout << endl;
	p++;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

那么这里也是野指针的问题。
这是为什么呢？我们的这个对象并没有重新分配地址啊。
在g++下这里是并没有报错的，而VS这里报错说明底层的实现原理是不同的。
这里失效时更好一点的，如果是尾删的话就是失效了。

所以按照库里面来返回删除元素的下一个元素的位置就好了。

深层深浅拷贝问题

注意我的操作：

int main()
{
	baiye::vector<baiye::vector<int>>arr;
	baiye::vector<int>cpp(10, 1);
	arr.push_back(cpp);
	arr.push_back(cpp);
	arr.push_back(cpp);
	arr.push_back(cpp);

	for (int i = 0; i < arr.size(); i++)
	{
		for (int j = 0; j < cpp.size(); j++)
		{
			cout << arr[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

OK，暂时没问题，再尾插一个cpp呢？

没让你失望，他崩了。
为什么4个不崩5个崩呢？
因为这也和重新开辟空间有关，我们来调试看看：
我直接快进到第五次尾插cpp

这里看好他们的地址：

这里地址p的成员地址和this指针中的成员地址相同了，这是为何？
图解：

这里是压入前四个的cpp的状态，此时并没有发生扩容。
当压入第五个cpp的时候发生扩容，我们看到代码是运行到memcpy的地方出问题的。
我们都知道memcpy拷贝是一个字节一个字节进行拷贝的，这里拷贝的是对标类型为vector类型的_start进行开辟空间的p，那么拷贝的就是_start和p所指向位置的所有内容。
但是他们的成员都是指针，拷贝的都是地址编号，这就导致了新开辟的空间的前四个内容的成员指针指向了旧空间的成员指向的内容。

那么，下一步就是释放掉原来的旧空间了，释放的位置是_start指向的位置，这也就导致p空间中的前四个类型指向的空间也同样被释放掉了。
这就是整个问题的所在之处，解决问题方法就是不让他一个字节一个字节拷贝，可以用赋值来避免自定义类型的这种情况，如下：

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* p = new T[n];
        int a = size();
        if (_start)
        {
            for (int i = 0; i < a; i++)
            {
                p[i] = _start[i];//这里改成赋值，就是调用拷贝构造去了
            }
            delete[] _start;
        }
        _start = p;
        _finish = _start + a;
        _endOfStorage = _start + n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19