写在前面
vector
是我们在STL
中最常用的容器,我们对它的各种操作也都了然于胸。然而我们在使用vector
的时候总会有一种很虚的感觉,因为我们不清楚接口内部是如何实现的。在我们眼里宛如一个黑箱,既危险又迷人。
为了打破这种顾虑,接下来我就带大家深入vector
底层,彻底弄懂vector
接口内部实现细节,打开这个黑箱。这样在使用vector
的时候我们也就不会慌了,做到真正的了然于胸。
vector 底层原理概述
vector
是动态空间,随着元素的增加,其内部机制会自行扩充空间来容纳新元素。
vector
动态增加大小时,并不是在原空间之后持续新空间(因为根本无法保证原空间之后尚有可供配置的空间),而是以原大小的两倍另外配置一块较大的空间,然后将内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间,
重点源码理解
1.迭代器内部型别
下面我们来看看STL
源码里面是如何来定义迭代器的吧。
template <class T, class Alloc = alloc>class vector {
public:
// vector 的嵌套型别定义
typedef T value_type;
typedef value_type* iterator; // 迭代器本身是一个模板类的对象
typedef value_type& reference;
...
};
如上面代码所示,迭代器iterator
本身是一个类类型,运算符*
被重载。迭代器iterator
指向vector
的内部元素,可以理解为iterator
与vector
的内部元素捆绑在一起,其行为类似指针,但是又不能把它当作指针。
灵魂拷问一:迭代器与指针有什么区别?
我们可以这样理解,迭代器本质上就是模板类产生的一个对象,而其运算符*
和->
都是经过运算符重载实现的。这个对象指向vector
的内部元素(元素又是迭代器的对象),所以当迭代器指向的元素被删除或者移动,迭代器与元素就断开链接,迭代器也就没有用了,也就是我们通常说的迭代器失效。迭代器的行为类似指针,但是又有所区别。
反观指针,指针与内存是联系在一起的。如果指针指向的内存地址存储的元素被删除或者移动,指针并不会因此失效,它依然指向了该地址。
根据上述定义,迭代器可以这样声明:
vector<int>::iterator ivite;
vector::iterator svite;
看完上面的源码,我们也就清楚为什么迭代器要这样声明了。
2.vector 的数据结构
vector
使用两个迭代器start
和finish
来表示已使用空间的范围,并以迭代器end_of_storage
指向分配空间的尾端。代码如下:
template <class T, class Alloc = alloc>class vector {
...
protected:
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾,即最后一个元素的下一个元素
iterator end_of_storage; // 表示目前分配的整个空间的尾
...
};
利用以上三个迭代器,我们能够封装vector
的各种成员函数。
template <class T, class Alloc = alloc>class vector {
...
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return size_type(end() - begin()); }
bool empty() const { return begin() == end(); }
reference front() { return *begin(); }
reference back() { return *(end() - 1); }
reference operator[](size_type n) { return *(begin() + n); }// 运算符[]重载,能够使用迭代器来访问元素
};
上面一些基础操作已经一目了然了,这里就不一一述说了。这里只提两点,第一,从上面代码可以看出operator[]()
对运算符[]
进行了重载,这样能够使迭代器像数组索引一样遍历vector
。
第二,迭代器finish
指向的是vector
最后一个元素的下一个元素,封装的end()
函数也如此。这也就是我们常常说的vector
的前闭后开特性。
灵魂拷问二:为什么容器要设计成前闭后开的特性?
这样做是为了在遍历容器元素时减少判断条件。因为STL
的核心是泛型编程,使得设计的接口是通用的。由于只有部分容器支持>
和<
运算符重载,而!=
则是全部容器都支持,所以遍历元素的时候优先使用!=
重载运算符。
如果将end()
指向容器最后一个元素的下一个,则遍历操作只需要写成:
vector<int> vec;
auto it = vec.begin();
while (it != vec.end()) {
...
++it;
}
但是如果end()
指向的是最后一个元素,上述代码会少遍历一个元素,这就需要在while
循环里增加额外的判断条件,并且这个判断条件可能因容器的不同要进行修改,而上述代码在任何顺序容器都能这样调用,减少了很多多余工作。
3.vector 的元素操作
vector 的构造函数
vector
的构造函数有多种形式,下面摘取源码中的部分代码:
// 构造函数,允许指定 vector 大小和初值
vector() : start(0), finish(0), end_of_storage(0) {}
vector(size_type n, const T& value) { fill_initialize(n, value); }
explicit vector(size_type n) { fill_initialize(n, T()); }
分别对应如下初始化:
vector<int> vec;
vector<int> vec(2,3);
vector<int> vec(2);
push_back() 与 pop_back()
当我们以push_back()
将新元素插入vector
尾端时,该函数首先检查是否还有备用空间,如果有就直接在备用空间上构造元素,并调整迭代器finish
。如果没有备用空间了,就扩充空间(重新配置、移动数据、释放原空间)。
void push_back(const T& x) {
if (finish != end_of_storage) { // 还有备用空间
construct(finish, x);
++finish;
}
else // 已无备用空间
insert_aux(end(), x); // 插入函数
}
插入函数原型为:
void insert_aux(iterator position, const T& x);
这个函数比较长,具体思路:在有备用空间情况下,在备用空间起始处构造一个元素,迭代器finish
自增一;在无备用空间情况下,重新配置两倍的原内存空间,将原vector
的内容拷贝到新vector
中,再释放掉原空间。
注:插入函数是将元素插入到对应位置,原先该位置以及后面的元素都向后移动一位。
删除vector
尾部元素操作pop_back()
更加简单。
void pop_back() {
--finish;
destroy(finish);
}
直接将尾部迭代器finish
向前移动一位,然后释放掉。由于尾部迭代器finish
指向的是最后一个元素的下一位,所以减一后正好是原来的最后一个元素。
erase() 与 clear()
erase()
表示删除vector
的某一个元素或者某一区间内的所有元素。
// 删除 vector 的某一个位置的元素
iterator erase(iterator position) {
if (position + 1 != end())
copy(position + 1, finish, position);
--finish;
destroy(finish);
return position;
}
// 删除 vector 的某一个区间的元素
iterator erase(iterator first, iterator last) {
iterator i = copy(last, finish, first);
destroy(i, finish);
finish = finish - (last - first);
return first;
}
如果不对erase()
函数谨慎使用,可能会出现迭代器失效的问题。
灵魂拷问三:在什么情况下使用`erase()`函数迭代器会失效?
通常我们写出这样的代码迭代器会失效。
for(auto it = vec.begin();it != vec.end();++it) {
if(/* 删除某元素的判断条件 */) {
vec.erase(it);
}
}
由灵魂拷问一可知,删除元素后由于被删除元素后面的数据都会发生移动,所以后面的迭代器都会失效。故上述代码在删除了某个迭代器后,后面的++it
遍历已经失去意义,不会得到正确的结果。
那应该如何更改呢?由前面删除vector
的某一个位置的元素的源代码可知,erase()
返回的是一个迭代器,这个迭代器实际上是被删除元素的下一个元素绑定的迭代器,这个迭代器是数据移动后新的有效的迭代器。也可以说是更新了迭代器。
正确的写法为:
for(auto it = vec.begin();it != vec.end();) {
if(/* 删除某元素的判断条件 */) {
it = vec.erase(it); // 更新了迭代器
}
else {
++it;
}
}
clear()
表示清空vector
上的所有元素。
void clear() { erase(begin(), end()); }