当前位置：首页 > news >正文

C++STL——容器-vector(含部分模拟实现，即地层实现原理）(含迭代器失效问题）

news 来源：原创 2025/5/9 3:08:10

容器——vector

1.构造

模拟实现

2.迭代器

模拟实现：

编辑

3.容量

模拟实现：

4.元素的访问

模拟实现

5.元素的增删查改

迭代器失效问题：

思考问题

【注】：这里的模拟实现所写的参数以及返回值，都是按照库里的来实现的。

大家都知道，万事开头难，但只要将开头做好，后面的就轻松多了。学习容器也是一样的，只要将第一个容器string学明白，底层实现了然于胸之后，再学习后面的容器之后，你会发现，换汤不换药，也就有一些不一样的地方而已。

那么今天咱们重点要讲迭代器的失效问题。废话少说，让咱们开始吧。

容器——vector

这里涉及到了一个东西——模板，这个东西博主会在后面进行讲解，大家只要记住这是一个泛型编程，即这里面的class T,这个T可以是任何的类型，而后面有个Alloc，这个叫内存管理器，咱们不用去管他，这个东西，编译器会自动进行内存管理的。所以这里只要关注第一个参数即可。vector就类似于顺序表。只不过这个顺序表，是有类似于指向开头的指针，指向有效个数下一个位置的指针，有指向容量结尾的指针。比如：咱们将整形int 存入一个vector中，即可这样写：vector<int>。

即可，vector<int>算是一种类吧。

1.构造

这里面的所有的const allocator_type& alloc = allocator_type()，不用去管，这只是一种内存管理器，编译器会自动处理的，并且写参数的时候也不需要去写。那么第一个是无参构造，第二个是构造并初始化n个val，第三个是使用迭代器进行初始化构造（这是一种范围式的构造），第四个是拷贝构造（这是重点，后面会讲它的模拟实现）。来上代码：

OK，那么通过以上的代码，博友们大概就已经知道它的构造方式了。这里需要强调的一点是：这里的auto后面加不加&,看的是你模板T是什么类型，因为范围for本质（就是不加&）是赋值拷贝，既然是拷贝，就有空间的消耗，要是int型还好，要是string型的呢？那你这个空间的消耗可谓是巨大。所以加上了&：传引用，对于一些开空间消耗较大的T来说，可谓是福音啊。所以，建议还是都加上&吧。（当然，你要是根据具体情况来，那也可以）。

模拟实现

第一个没啥，就是为空，就不看他的模拟实现了。

第二个：

vector(int n, const T& val = T())

{

        reserve(n);

        for (int i = 0; i < n; i++)

        {

                push_back(val);

        }

}

这里的T()的意思是T类型的默认构造。这里还需要强调一个问题，也是困扰博主的一个问题，不过还好博主将它解决了：后面的代码中你会看见vector<T>&v或者T&v。那么什么时候用第一个呢？第一个是当你准备用这一整个类型的时候(比如范围for，你是不是得用v去拷贝另一个对象，这个时候v是对象，那么这个时候，v的类型是vector<int>，所以才会用到第一个），参数才会写第一个。而第二个的v是T类型的值，比如int类型的值，并不是对象，所以说第二个主要应用于类似于插入值的时候。没事，慢慢的从后面的代码中体会。

就拿这一个举例，这一个是不是要尾插一个值，所以说，这里是T&val，后面的T(),相当于给val初始化了。

第三个：

template <class InputIterator>

vector(InputIterator first, InputIterator last)

{

        while (first != last)

        {

                push_back(*first);

                ++first;

        }

}

这里如果说push_back,扩容了，那么这里可能会涉及到迭代器失效的问题（下面将），但这里假定它没有扩容。

第四个：

vector(const vector<T>& v)

{

        reserve(v.capacity());

        for (auto& e : v)

        {

                push_back(e);

        }

}

这里是拷贝构造，是不是将咱们上面提到的两个问题全都涉及到了，即&问题与参数vector<T>&问题。

再来一个列表初始化的模拟实现：

vector(initializer_list<T> il)

{

        reserve(il.size());

        for (auto& e : il)

        {

        push_back(e);

        }

}

列表初始化本质就是通过push_back来尾插数据。

2.迭代器

由于vector不支持重载流插入流提取，所以不可以像string类一样直接输出，它只能一个元素一个元素的输出，也跟string类一样，三种方法：

1.下标+[]：

for (size_t i = 0; i < v.size(); i++)

{

cout << v[i] << " ";

}

cout << endl;

2.迭代器：

bit::vector<int>::iterator it = v.begin();

while (it != v.end())

{

        cout << *it << " ";

        ++it;

}

        cout << endl;

3.范围for：

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

这里vector的迭代器跟string的一样，因为都是迭代器嘛，但这里给上两个图，帮助大家理解：

模拟实现：

给定三个位置，_start,一开始的元素位置，_finish有效数据个数的下一个位置,end_of_storage，容量到头的那个位置。

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;

}

3.容量

这里跟string类差不多，都是一样的，但这里有两个重点的，咱们模拟实现一下：1.size():获取数据个数.2.capacity():获取容量大小3.empty():判断是否为空。4.resize():改变vector的size。5.reserve(): 改变vector的capacity。

我记得string里面并没有说capacity()的增长速度，那么在这咱们来讲一下：

std::vector<int>::size_type sz;std::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i=0; i<100; ++i) {foo.push_back(i);if (sz!=foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}std::vector<int> bar;sz = bar.capacity();bar.reserve(100);   // this is the only difference with foo abovestd::cout << "making bar grow:\n";for (int i=0; i<100; ++i) {bar.push_back(i);if (sz!=bar.capacity()) {sz = bar.capacity();std::cout << "capacity changed: " << sz << '\n';}}

这是我直接截取的官方库里的代码，咱们来看逻辑分析：先定义一个sz用来存储capacity()的变化情况。之后写一个for循环用来不断的尾插数据，再来判断容量等不等于之前的，再打印出容量，可以看出容量的变化方式，几乎是成2倍的速度增长的。再来看一下子扩容好100个空间的，那么这个可以看出容量几乎没什么变化，因为空间提前被开好了。虽然容量在g++上是按照2倍增长的，但是在vs上是按照1.5倍增长的，所以说为什么我在string这一篇文章中说，扩容多少是看编译器的，编译器不同，扩容的速率也是不同的。

ok，那么接下来看两个重点的，先来看第一个resize：

参数也是按照库里来写的。resize起到了对数据的判断是否要插入以及删除。以上就是resize的模拟实现。思路：如果说你要插入的数据个数n大于了这里的capacity，那么就需要扩容了，扩容之后，_start+n就是容量了（capacity），扩容马上讲。那么_finish不可以等于容量，且一定比容量小吧，之后在_finish这插入数据，之后++_finish。更新_finish的位置，直到n。如果说n比capacity小，说明要删除数据了。删除数据就直接让有效数据的下一个位置更新到你要保存的元素的个数即可（即_start+n）。

第二个：reserve

这儿的逻辑跟string的逻辑差不多，唯一的一个坑就是我在代码中注释的，所以为了解决这个问题，你直接用原来的size不就可以了吗，不用新的size，就可以避免_finish为0的问题。以上也是模拟实现。

模拟实现：

由于resize以及reserve的模拟实现咱们已经写过了，下面咱们写size的那几个：

size_t capacity() const

{

return _end_of_storage - _start;

}

size_t size() const

{

return _finish - _start;

}

4.元素的访问

这里其实跟string差不多，咱们只讲一个，

模拟实现

T& operator[](size_t i)

{

assert(i < size());

return _start[i];

}

5.元素的增删查改

在这也会讲到咱们最重要的部分：迭代器的失效问题。

1.尾插

来看它的模拟实现：

这里需要先确定一下是否需要扩容，如果说需要扩容，那么就先扩容，之后往_finish处插入数据，之后更新_finish的位置即可。

2.pop_back:尾删

跟push_back的差不多。

3.insert:在position之前插入val

来看它的模拟实现：

这儿有一个迭代器失效问题，待会讲完erase一块讲。这个代码的逻辑：先判断pos必须在_start与_finish之间。需要扩容的时候记得扩容。之后定义一个迭代器，让_finish赋给它，之后一直到pos的位置，往后挪一位，之后在pos这个地方插入数据，更新_finish。不知道大家发没发现一个规律：就是比如说我在pos插入元素，那么我一开始定义的地方一定是尾部，然后往后挪动数据，直到pos位置空出一个位置即可。而对于删除pos位置的元素，一般都是从pos位置开始定义，然后往前挪数据，直到有效数据的最后位置。

4.erase：删除position位置的数据

来看模拟实现：

这个代码逻辑也很简单，从pos位置开始定义，一直往前挪动一个数据，直到尾部为止，别忘了更新_finish。

迭代器失效问题：

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

如果继续使用已经失效的迭代器，程序可能会崩溃)。类似于野指针，指向了一块不存在空间。

1.扩容导致的迭代器失效：

看图，再看咱们模拟实现的 insert，假设空间不够了，但还要插入数据，是不是得扩容啊？扩容一般都是异地扩容，但是异地扩容，你的_start,_finish,enf_of_storge都更新过去了，但是迭代器it呢？它没有更新啊同志们，它还指向了一块已经被释放的空间，你说这迭代器能不失效吗？解决办法也很简单，记住原来it的位置，将它映射到新开的空间上即可。insert的模拟实现已经给出了答案。但你也可以，提前先reserve好足够的空间（在定义迭代器之前先开好空间），这样就完美的避开了这个问题。

2.由于删除元素导致的迭代器失效

假定咱们删除了一个元素2对吧，那么2后面的元素的3会往前1移动，代替2的位置，但是呢，你可以认为这个迭代器比较傻，它只认它一开始指向的那个元素，如果那个元素没有了，那么它会认为那个元素所在的空间被销毁了，那么这个迭代器也就失效了。比如上图中的it迭代器，就是这个原理。那么以此类推，it后面的元素是不是都要往前移动啊，那么如果说it后面还有迭代器，那么自然it后面的迭代器全部失效。解决办法也很简单，就是再重新将被删元素的下一个空间重新赋值给it，那么被删元素的下一个空间其实就是it所指向的空间，因为被删元素的下一个元素往前挪动了一格嘛，所以说，这个空间就是it所指向的空间，就是原被删元素的空间。

那么失效后的迭代器，都不可再对他们进行++，--等操作，当然，在vs上会强制检查，但在其他编译器上，可能还可以正常运行，这也是看编译器的。

那么insert的返回值是插入那个元素的空间位置。而erase的返回值是被删元素的下一个元素的空间，其实都是it这个位置。

思考问题

vector v{ 1, 2, 3, 4 };

auto it = v.begin();

while (it != v.end())

{

        if (*it % 2 == 0)

        {

                v.erase(it);

                  ++it;

        }



}

那么看上面这个代码，对吗？为什么不对？

肯定不对啊，1.首先是迭代器失效的问题，你erase后是不可以对迭代器进行加减操作的。

2.erase删除的迭代器如果是最后一个元素，删除之后it已经超过end，此时迭代器是无效的，++it导致程序崩溃。是因为进去循环的条件是it不等于_finish（这个循环式erase中的循环），而删除尾部元素的时候，it被定义为指向尾部的下一个元素，那么就可以进入循环，之后it会一直++，那这肯定不行，一直访问的是没有的空间。

3.就算你给erase重新赋值，但是又有一个问题：比如vector<int> v={1,2,2,3,4},有两个连续的偶数，你删除了第一个偶数之后，第二个偶数挪到了第一个偶数的位置，然后it++，会直接跳过第二个偶数，那这样第二个偶数就删不了了，不可以，所以，完美的解决办法就是，当它是偶数的时候，直接删，当它是奇数的时候，再++.即：

现在迭代器失效的问题，我已经全部讲清楚了，也讲的很透了。

5.swap

void swap(vector<T>& v)

{

        std::swap(_start, v._start);

        std::swap(_finish, v._finish);

        std::swap(_end_of_storage, v._end_of_storage);

}

那么现在咱们再来看一下现代写法的赋值有多精妙。

// v1 = v3

vector<T>& operator=(vector<T> v)

{

swap(v);

return *this;

}

首先，先对v3进行传值传参，需要调用拷贝构造，那么拷贝构造就是再次构造出一个与v3一样大的空间，完了之后，交换v1与v（v3），那么咱们v3是想要的，而v1是不想要的，通过交换正好拿到了v3，那么v1也给了v，而v是一个局部变量啊，出了作用域就销毁了。所以说，v出了函数就销毁了，反正也不要了，是不是很nice呀，哈哈哈哈哈，确实，我也这么想的，当年创造这个写法的人肯定也是这么想的。

OK，vector的内容就这些，由于咱们有了string的基础，所以学起来vector就是很简单了，除了一些特殊的坑外，其他的也没什么了。

以上内容均我个人理解，若有不对，还请各位大佬指出，谢谢啦！

本篇完...................

容器——vector

1.构造

模拟实现

2.迭代器

模拟实现：

3.容量

模拟实现：

4.元素的访问

模拟实现

5.元素的增删查改

迭代器失效问题：

思考问题

相关文章：