什么是vector？
在C++中，vector是一个非常有用的容器类，用于存储一组元素，类似于数组。它提供了动态大小的数组功能，使得在运行时可以轻松地添加、删除和访问元素。vector是C++标准模板库（STL）的一部分，因此只需包含头文件<vector>即可使用。
vector主要有以下几种作用：
动态大小: vector可以根据需要动态增长或缩小其大小。这意味着不需要在创建时指定其大小，而是可以在运行时根据需要添加或删除元素。
随机访问: 类似于数组可以使用索引来直接访问vector中的元素。
自动内存管理: vector会自动进行内存管理，我们也就不用担心内存分配和释放的细节。
元素操作: vector提供了许多用于操作元素的函数，例如在尾部添加元素（push_back()）、删除尾部元素（pop_back()）、插入元素（insert()）、删除指定位置元素（erase()）等等。
一个使用vector的简单示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <vector>
#include <iostream>
int main() {
std::vector<int> myVector;
myVector.push_back(10);
myVector.push_back(20);
myVector.push_back(30);
std::cout << "Vector size: " << myVector.size() << std::endl;
std::cout << "Vector capacity: " << myVector.capacity() << std::endl;
std::cout << "Elements: ";
for (int i = 0; i < myVector.size(); ++i) {
std::cout << myVector[i] << " ";
}
return 0;
}
|
以上代码会输出：
1
2
3
| Vector size: 3
Vector capacity: 4
Elements: 10 20 30
|
模拟实现
构造函数与迭代器
在C++中，vector是一个模板类（template class），它通过模板参数来指定所存储元素的类型。这意味着vector可以存放各种类型的值。
例如，如果想要存储整数类型的元素：
1
| std::vector<int> intVector;
|
如果想存储浮点数类型的元素：
1
| std::vector<float> floatVector;
|
简而言之，vector是通过模板参数生成不同类型的容器。
在上面的示例中，vector的行为是相同的，只是存储的元素类型不同。模板类让我们可以轻松创建存储不同类型元素的向量容器。
vector容器类通常使用两个指针来表示元素范围，start和finish，即有效元素的起始位置和结束位置。还使用一个指针来表示内存中可用于存储元素的结束位置，这个指针通常称为endofstorage，指向存储在内存中的元素数组的指针，指向当前 vector 对象的内存缓冲区的末尾位置。
start: 指向vector中的第一个有效元素的位置。通常，它指向存储在内存中的元素数组的首地址。
finish: 指向vector中最后一个有效元素的下一个位置。换句话说，它指向存储在内存中的元素数组中的下一个可用位置。
endofstorage: 指向可用存储空间的最后一个位置。
这三个指针共同定义了vector中存储元素的范围。有效的元素是从start指针开始，一直到finish指针之前的位置（即左闭右开区间）。因此，vector中的实际存储元素数量可以通过 finish - start 来计算。
当添加或删除元素时，指针会随之更新，以反映vector中元素的当前范围。如果 vector 的元素数量超过当前内存缓冲区的容量，vector 将会重新分配更大的内存空间，并更新 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
| namespace myclass
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
public:
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector(size_t n, const T& val = T())
{
resize(n, val);
}
vector()
{}
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
}
}
|
因为篇幅较长，所以拎出来单独解释一下这个函数：
1
| vector(size_t n, const T& val = T())
|
第一个参数是 size_t n，表示要创建的 vector 的大小，即其中包含的元素数量。第二个参数是 const T& val，表示要用来初始化 vector 中元素的值，它可以作为一个常量引用来接收内置类型的调用，同时也可以接收自己写的类，比如上一篇文章重写的string类。
当我们使用类似 vector myVector(10, 1); 这样的调用时，它是有效的，因为这其实是一个隐式的类型转换。
1 是一个整数常量，而不是 const int& 类型的常量引用。然而，C++ 允许进行隐式类型转换，可以将 1 转换为 const int& 类型的常量引用，以匹配构造函数的参数类型。当我们传递 1 作为第二个参数时，虽然 1 是一个临时的常量值，但它会被绑定到构造函数参数 const T& val 上的常量引用。这样做可以延长 1 的生命周期，确保它在 vector 的构造函数中被正确使用，即在 vector 对象创建过程中可以通过常量引用访问这个值。
一些其他常用的函数
其实和string类的模拟实现大差不差，就不单独一个一个的写了（懒）。
单独提一下insert和erase函数。
在 C++ STL 中，std::vector 的 insert 函数是用于在指定位置插入元素的成员函数。它返回一个迭代器（iterator），指向插入的元素。
1
| iterator insert(iterator pos, const T& value);
|
该函数的参数如下：
pos：一个迭代器，表示插入元素的位置。
value：要插入的元素的值。
insert 函数的作用是将新元素插入到指定位置，它会改变 vector 的大小和容量，可能导致内部的数据重新分配。为了方便使用者处理插入后的元素，函数返回一个指向插入元素的迭代器，这样用户就可以继续对新元素进行操作，或者在需要时获取其位置或修改其值。
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <iostream>
#include <vector>
int main() {
std::vector<int> myVector = {1, 2, 3, 4, 5};
auto insertPos = myVector.insert(myVector.begin() + 2, 100);
std::cout << "Inserted Element: " << *insertPos << std::endl;
return 0;
}
|
insert和erase
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
| 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;
}
*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;
}
|
在注释了我提到了迭代器失效。为什么迭代器会失效？
这里的迭代器失效指的是在向 vector 中插入新元素后，之前的迭代器可能会变得无效。
在 vector 中插入元素可能会导致内部数据重新分配，这涉及到扩容操作。如果扩容后，原先的内存块不够存放所有元素，vector 就会在新的内存地址上重新分配内存，并将原先的元素复制到新的位置。这样一来，原先指向vector 中元素的迭代器就会失效，因为它们指向了之前的内存地址，而这些地址现在已经不再有效。
为了解决这个问题，首先会检查插入新元素后是否需要扩容。如果需要扩容，就会重新分配更大的内存块，并将原先的元素复制到新的位置。然后，为了使原先的迭代器仍然有效，会将 pos 这个迭代器重新设置为插入元素后的位置，即 _start + len。这样一来，之前的迭代器 pos 就仍然指向正确的位置，不会失效。
其他的一些函数
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
| vector<T>& operator=(vector<T> v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
return *this;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
for (size_t 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& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
|
