ToB企服应用市场:ToB评测及商务社交产业平台

标题: 11.vector的介绍及模仿实现 [打印本页]

---

作者: 雁过留声    时间: 前天 15:25
标题: 11.vector的介绍及模仿实现
1.vector的介绍

记得之前我们用C语言实现过顺序表，vector本质上也是顺序表，一个能够动态增长的数组。
vector 的底层实现机制
 
- 动态数组：vector 的底层实现是动态数组。它在内存中连续存储元素，就像一个可以自动调整大小的数组。
- 内存分配策略：
- 当向 vector 中添加元素导致容量不足时，vector 会重新分配一块更大的内存空间，将原有元素复制到新空间中，然后释放旧空间。这个过程大概会比力耗时，尤其是当 vector 中存储的元素数量较大时。
- 初始时，vector 通常会分配一定大小的内存空间，随着元素的不绝添加，渐渐扩大容量。
- 迭代器失效：在举行插入、删除等操作时，大概会导致指向 vector 中元素的迭代器失效。这是由于这些操作大概会引起内存的重新分配和元素的移动。
迭代器失效背面模仿实现会详细讲解
其实vector的常用接口和string大部分相似，但是也有差别，那有什么差别呢？
一、存储内容差别
 
- vector：可以存储各种类型的数据，如整数、浮点数、结构体等。比方，可以存储一组整数 vector<int> v = {1, 2, 3} 。
- string：专门用于存储字符序列，即字符串。比方 string s = "hello" 。
 
二、操作差别
 
- vector：
- 支持随机访问，可以通过下标快速访问元素。比方 v[2] 可以快速访问 vector 中的第三个元素。
- 可以动态添加和删除元素，使用 push_back 添加元素， pop_back 删除最后一个元素。
- string：
- 提供了丰富的字符串操作函数，如查找、更换、拼接等。比方 s.find("ll") 可以查找字符串中“ll”的位置。
- 可以直接使用 + 举行字符串拼接。
 
三、性能特点差别
 
- vector：
- 在内存中连续存储元素，有利于进步访问速率，但在插入和删除元素时大概需要移动大量元素，效率较低。
- 可以预先分配一定的空间，避免频繁的内存分配和释放。
- string：
- 通常会举行一些优化，如小字符串优化等，以进步性能。
- 字符串的长度可以动态厘革，但在举行大量修改操作时大概会有一定的性能开销。
2.vector的使用

2.1vector的初始化

无参构造：

1. vector<int> v1;

复制代码

构造并初始化：用n个value初始化

1. vector<int> v2(10, 1);//10个1

复制代码

迭代器区间初始化：

1. vector<int> v3(v2.begin(), v2.end());

复制代码

拷贝构造：

1. vector<int> v4(v2);

复制代码

2.2vector iterator 的使用

iterator 的使用	接口说明
begin + end	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

2.3 vector 空间

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变vector的size
reserve	改变vector的capacity

   1.capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2     倍增长的。这个问题经常会观察，不要固化的以为，vector增容都是2倍，具体增长多少是     根据具体的需求界说的。vs是PJ版本STL，g++是SGI版本STL。      2.reserve只负责开辟空间，假如确定知道需要用多少空间，reserve可以缓解vector增容的代     价缺陷问题。      3.resize在开空间的同时还会举行初始化，影响size     这些接口和string是类似的，就不一一调用介绍了     2.4 vector 增删查改

  

vrector增删查改	接口说明
push_back	尾插
pop_back	尾删
find （#include <algorithm>）	查找。（留意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入value
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[]	像数组一样访问

在 C++中，vector 并非没有实现 find 接口，只是没有像一些容器（如关联容器）那样有专门的成员函数 find。
 
原因如下：
 
1. 效率考虑：对于顺序容器（如 vector），线性查找的效率相对较低，通常可以使用更高效的算法如二分查找等，而不是直接调用 find 成员函数。
2. 设计理念：C++标准库的设计尽量保持差别容器的特性和用途明白，vector 主要用于存储连续的元素，更夸大随机访问和高效的插入/删除尾部元素等操作，而不是查找。
 
可以通过标准算法中的  find  函数来在 vector 中举行查找。比方： 
auto it = std::find(vector.begin(), vector.end(), target); 。

对于其他增删查改接口和string同样是类似的，就不详细介绍了，但是insert和erase这两个接口是差别的，这两个接口需要配合迭代器使用，但是配合迭代器使用这里就会有一个迭代器失效的问题
2.5 vector 迭代器失效问题。（重点）

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

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. int main()
5. {
6.     int a[] = { 1, 2, 3, 4 };
7.     vector<int> v(a, a + sizeof(a) / sizeof(int));
8.     // 使用find查找3所在位置的iterator
9.     vector<int>::iterator pos = find(v.begin(), v.end(), 3);
10.     // 删除pos位置的数据，导致pos迭代器失效。
11.     v.erase(pos);
12.     cout << *pos << endl; // 此处会导致非法访问
13.     return 0;
14. }

复制代码

  erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理     论上讲迭代器不应该会失效，但是：假如pos刚好是最后一个元素，删完之后pos刚好是end     的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素     时，vs就以为该位置迭代器失效了。  
   迭代器失效办理办法：在使用前，对迭代器重新赋值即可。   3.vector的模仿实现

3.1结构的界说

这里我们参考STL源码剖析实现一个简易版本的vector
成员变量的界说：

1. #include <iostream>
2. #include <assert.h>
3. using namespace std;
4. namespace Ro
5. {
6.         template<class T>
7.         class vector
8.         {
9.         public:
10.                 typedef T* iterator;
12.         private:
13.                 iterator _start;
14.                 iterator _finish;
15.                 iterator _end_of_storage;
17.         };
18. }

复制代码

这里各人大概会发现和模仿实现string的写法怎么不一样？
其实这就是参考STL的写法，虽然写法差别，但其实效果是大差不差的。
如图：

我们可以通过指针减指针的做法得到size和capacity。
这里同样和模仿实现string一样使用命名空间来和库中的vector区分开来，而且这里使用类模板是为了存储差别类型的数据，
这里顺带直接将size()和capacity()的接口实现出来，同时给成员变量加一个缺省值给初始化列表用

1. namespace Ro
2. {
3.         template<class T>
4.         class vector
5.         {
6.         public:
7.                 typedef T* iterator;
8.                 size_t size() const
9.                 {
10.                         return _finish - _start;
11.                 }
12.                 size_t capacity() const
13.                 {
14.                         return _end_of_storage - _start;
15.                 }
16.         private:
17.                 iterator _start = nullptr;
18.                 iterator _finish = nullptr;
19.                 iterator _end_of_storage = nullptr;
21.         };
22. }

复制代码

3.2构造函数和析构函数

构造：

1. vector(){}

复制代码

这里初始化列表不写也会走，通过给的缺省值来初始化
析构函数：

1. ~vector()
2. {
3.         if (_start)
4.         {
5.                 delete[] _start;
6.                 _start = _finish = _end_of_storage = nullptr;
7.         }
8. }

复制代码

3.3reverse()

由于背面大部分函数接口都需要扩容，所以为了背面方便，我们先实现reverse

1. void reverse(size_t n)
2. {
3.         if (n > capacity())
4.         {
5.                 if (_finish == _end_of_storage)
6.                 {
7.                         size_t old_size = size();
8.                         T* tmp = new[n];
9.                         if (_start)
10.                         {
11.                                 memcpy(tmp, _start, sizeof(T) * old_size);
12.                                 delete[] _start;
13.                         }
14.                         _start = tmp;
15.                         _finish = tmp + old_size;
16.                         _end_of_storage = tmp + n;
17.                 }
18.         }
19. }

复制代码

这里我们要先将size()存下来，不然在给_finish更新时，会出现野指针。如图：

一般环境下都不会举行缩容的，所以我们在实现的时候不考虑缩容。另外，这里还会有一个坑，背面出错时我们再办理并说明
3.4push_back()和operator[]

为了让我们的vector能够跑起来，先来实现一下push_back接口

1. void push_back(const T& val)
2. {
3.         if (_finish == _end_of_storage)
4.         {
5.                 reverse(capacity() == 0 ? 4 : capacity() * 2);
6.         }
7.         *_finish = val;
8.         _finish++;
9. }

复制代码

先检查容量有没有满，满了就扩容，这里我们扩容就扩2倍，然后再插入数据，_finish指针++,指向下一个位置。
为了接下来方便测试我们先来实现 下标+[] 来访问数据
operator[]:
T&: T是我们不知道数据的类型，加&是为了减少拷贝

1. T& operator[](size_t i)
2. {
3.         assert(i < size());
4.         return _start[i];
5. }
6. const T& operator[](size_t i) const
7. {
8.         assert(i < size());
9.         return _start[i];
10. }

复制代码

测试一下：

1. void test_vector1()
2. {
3.         vector<int> v;
4.         v.push_back(1);
5.         v.push_back(2);
6.         v.push_back(3);
7.         v.push_back(4);
8.         //v.push_back(5);
9.         for (int i = 0; i < v.size(); i++)
10.         {
11.                 cout << v[i] << ' ';
12.         }
13.         cout << endl;
14. }

复制代码

先测试一下扩容前的1 2 3 4，然后再测试一下扩容后的1 2 3 4 5

没有问题
3.5迭代器的实现

这里我们来实现一下普通迭代器和const迭代器

1. typedef T* iterator;
2. typedef const T* const_iterator;
3. iterator begin()
4. {
5.         return _start;
6. }
7. iterator end()
8. {
9.         return _finish;
10. }
11. const_iterator begin() const
12. {
13.         return _start;
14. }
15. const_iterator end() const
16. {
17.         return _finish;
18. }

复制代码

普通迭代器可读可写，const迭代器可读但是不可写。
测试一下迭代器遍历，同样范围for也可以使用了：

1. void test_vector2()
2. {
3.         vector<int> v;
4.         v.push_back(1);
5.         v.push_back(2);
6.         v.push_back(3);
7.         v.push_back(4);
8.         v.push_back(5);
9.         vector<int>::iterator it = v.begin();
10.         while (it != v.end())
11.         {
12.                 cout << *it << ' ';
13.                 it++;
14.         }
15.         cout << endl;
16.         for (int e : v)
17.         {
18.                 cout << e << ' ';
19.         }
20.         cout << endl;
21. }

复制代码

普通迭代器可写

1. void test_vector2()
2. {
3.         vector<int> v;
4.         v.push_back(1);
5.         v.push_back(2);
6.         v.push_back(3);
7.         v.push_back(4);
8.         v.push_back(5);
9.         vector<int>::iterator it = v.begin();
10.         while (it != v.end())
11.         {
12.                 *it *= 2;
13.         it++;
14.         }
15.         for (int e : v)
16.         {
17.                 cout << e << ' ';
18.         }
19.         cout << endl;
20. }

复制代码

const迭代器不可写

所以迭代器要正确匹配使用。
3.6深拷贝

前面我们提到过，扩容时另有一个坑没说，其实就是memcpy浅拷贝的问题。
假如我们vector存的是string这种自界说类型会发生什么？

1. void test_vector3()
2. {
3.         vector<string> v;
4.         v.push_back("111111111111111111111111");
5.     v.push_back("111111111111111111111111");
6.     v.push_back("111111111111111111111111");
7.     v.push_back("111111111111111111111111");
8.     //v.push_back("111111111111111111111111");
9.         for (string& s : v)
10.         {
11.                 cout << s << ' ';
12.         }
13.         cout << endl;
14. }

复制代码

我们来看看扩容前和扩容后：
扩容前：

扩容前没有问题。那扩容后呢？
扩容后：

扩容后出问题了，运行崩溃，且打印效果错了，这是为什么？
其实就是memcpy由于浅拷贝导致的,如图：

那么整个时候就应该要深拷贝，tmp创建自己的空间存放拷贝的数据

1. void reverse(size_t n)
2. {
3.         if (n > capacity())
4.         {
5.                 if (_finish == _end_of_storage)
6.                 {
7.                         size_t old_size = size();
8.                         T* tmp = new T[n];
9.                         if (_start)
10.                         {
11.                                 //memcpy(tmp, _start, sizeof(T) * old_size);
12.                                 for (int i = 0; i < old_size; i++)
13.                                 {
14.                                         tmp[i] = _start[i];//T会调用自己的深拷贝
15.                                 }
16.                                 delete[] _start;
17.                         }
18.                         _start = tmp;
19.                         _finish = tmp + old_size;
20.                         _end_of_storage = tmp + n;
21.                 }
22.         }
23. }

复制代码

这里我们可以直接赋值，假如T是内置类型，一个一个拷贝没有问题，假如是自界说类型，就让T自己去调用它自己的深拷贝，也没有问题。
测试一下：

现在就不会出错了。
3.7resize()

假如n小于size，有效数据就会变为n个，容量稳定
大于size小于capacity就会将数据扩大到n个，且会把size到n之间的数据初始化为val
大于capacity的话就会先扩容，再初始化。

1. void resize(size_t n, const T& val = T())
2. {
3.         if (n < size())
4.         {
5.                 _finish = _start + n;
6.         }
7.         else
8.         {
9.                 reverse(n);
10.                 while (_finish != _start + n)
11.                 {
12.                         *_finish = val;
13.                         _finish++;
14.                 }
15.         }
16. }

复制代码

这里缺省值我们不能直接给0或者其他，由于存储的数据类型我们不知道，这里可以用T()匿名对象作为缺省值，让T调用自己的构造去初始化。
留意：匿名对象的生命周期只在那一行，所以要使用const引用匿名对象，目的就是延长匿名对象的生命周期。
测试一下:

1. void test_vector4()
2. {
3.         vector<int> v;
4.         v.push_back(1);
5.         v.push_back(2);
6.         v.push_back(3);
7.         v.push_back(4);
8.         for (int e : v)
9.         {
10.                 cout << e << ' ';
11.         }
12.         cout << endl;
13.         v.resize(10, 1);
14.         for (int e : v)
15.         {
16.                 cout << e << ' ';
17.         }
18.         cout << endl;
19. }

复制代码

3.8pop_back()和empty()

当没有数据时，即为空时不能尾删
所以先来实现判空：

1. bool empty() const
2. {
3.         return _start == _finish;
4. }

复制代码

尾删：

1. void pop_back()
2. {
3.         assert(!empty());
4.         _finish--;
5. }

复制代码

比力简单就不测试了。
3.9insert()

在pos前插入val，先将pos后元素全部向后移动一格，在将val插入pos位置

1. void insert(iterator pos, const T& val)
2. {
3.         assert(pos <= _finish && pos >= _start);
4.         if (_finish == _end_of_storage)
5.         {
6.                 reverse(capacity() == 0 ? 4 : capacity() * 2);
7.         }
8.         iterator end = _finish - 1;
9.         while (end >= pos)
10.         {
11.                 *(end + 1) = *end;
12.                 end--;
13.         }
14.         *pos = val;
15.         _finish++;
16. }

复制代码

分别测试一下扩容前和扩容后：

1. void test_vector5()
2. {
3.         vector<int> v;
4.         v.push_back(1);
5.         v.push_back(2);
6.         v.push_back(3);
7.         //v.push_back(4);
8.         for (int e : v)
9.         {
10.                 cout << e << ' ';
11.         }
12.         cout << endl;
13.         vector<int>::iterator pos = find(v.begin(), v.end(), 2);
14.         v.insert(pos, 10);
15.         for (int e : v)
16.         {
17.                 cout << e << ' ';
18.         }
19.         cout << endl;
20. }

复制代码

扩容前：

扩容后：

这里效果出错了，为什么呢？
其实就是由于我们前面提到的迭代器失效问题。
由于扩容之后，pos还是指向旧空间的2，但是我们现在要在新空间的2前面插入10，所以我们应该在扩容后更新pos指针。

1. void insert(iterator pos, const T& val)
2. {
3.         assert(pos <= _finish && pos >= _start);
4.         if (_finish == _end_of_storage)
5.         {
6.         size_t len = pos - _start;
7.                 reverse(capacity() == 0 ? 4 : capacity() * 2);
8.         pos = _start + len;
9.         }
10.         iterator end = _finish - 1;
11.         while (end >= pos)
12.         {
13.                 *(end + 1) = *end;
14.                 end--;
15.         }
16.         *pos = val;
17.         _finish++;
18. }

复制代码

现在再测试一下：

现在就没有问题了。
但是需要留意的是，在insert中我们虽然更新了形参pos，但是外貌的实参pos并没有改变，形参是实参的临时拷贝，所以形参改变不会影响形参。
那怎么办？引用形参可以吗？这里我们给出办理办法，不推荐引用，可以通过返回值来返回更新之后的pos。
不采用引用形参的原因
- 避免意外修改：
- 假如 insert 函数通过引用形参返回插入位置，这大概会导致意外的修改。由于引用本身可以被重新赋值，函数调用者大概会不小心修改这个引用，从而改变了本来应该表现插入位置的信息。
- 语义不符：
- 从语义角度看， insert 操作主要是向容器中添加元素，重点在于插入操作本身和插入后的元素位置。返回一个表现插入位置的迭代器更符合这个操作的语义，而通过引用形参返回位置不太符合这种直观的明白。引用形参更多地用于在函数内部修改外部变量的值，而 insert 的主要目的不是修改外部传入的表现位置的变量，而是告知调用者新元素的位置。

1. iterator insert(iterator pos, const T& val)
2. {
3.         assert(pos <= _finish && pos >= _start);
4.         if (_finish == _end_of_storage)
5.         {
6.                 size_t len = pos - _start;
7.                 reverse(capacity() == 0 ? 4 : capacity() * 2);
8.                 pos = _start + len;
9.         }
10.         iterator end = _finish - 1;
11.         while (end >= pos)
12.         {
13.                 *(end + 1) = *end;
14.                 end--;
15.         }
16.         *pos = val;
17.         _finish++;
18.         return pos;
19. }

复制代码

4.0erase()

同样erase也会有迭代器失效的问题，所以我们也可以和insert一样通过返回值来更新一下pos

1. iterator erase(iterator pos)
2. {
3.         assert(pos >= _start && pos < _finish);
4.     //挪动数据
5.         iterator end = pos + 1;
6.         while (end < _finish)
7.         {
8.                 *(end - 1) = *end;
9.                 end++;
10.         }
11.         _finish--;
12.         return pos;
13. }

复制代码

测试一下：

1. void test_vector6()
2. {
3.         vector<int> v;
4.         v.push_back(1);
5.         v.push_back(2);
6.         v.push_back(3);
7.         v.push_back(4);
8.         v.push_back(5);
9.         for (int e : v)
10.         {
11.                 cout << e << ' ';
12.         }
13.         cout << endl;
14.         vector<int>::iterator pos = find(v.begin(), v.end(), 2);
15.         v.erase(pos);
16.         for (int e : v)
17.         {
18.                 cout << e << ' ';
19.         }
20.         cout << endl;
21. }

复制代码

假如我们要删除全部的偶数呢？

1. void test_vector6()
2. {
3.         vector<int> v;
4.         v.push_back(1);
5.         v.push_back(2);
6.         v.push_back(3);
7.         v.push_back(4);
8.         v.push_back(5);
9.         for (int e : v)
10.         {
11.                 cout << e << ' ';
12.         }
13.         cout << endl;
14.         vector<int>::iterator it = v.begin();
15.         while (it != v.end())
16.         {
17.                 if (*it % 2 == 0) it = v.erase(it);
18.                 else it++;
19.         }
20.         /*vector<int>::iterator pos = find(v.begin(), v.end(), 2);
21.         v.erase(pos);*/
22.         for (int e : v)
23.         {
24.                 cout << e << ' ';
25.         }
26.         cout << endl;
27. }

复制代码

4.1拷贝构造

拷贝构造可以使用传统写法，也可以使用现代写法，这里我们直接干

1. vector(const vector<T>& v)
2. {
3.         reverse(v.size());
4.         for (auto& e : v)
5.         {
6.                 push_back(e);
7.         }
8. }

复制代码

测试一下：

1. void test_vector7(){        vector<int> v1;        v1.push_back(1);        v1.push_back(2);        v1.push_back(3);        v1.push_back(4);        v1.push_back(5);        for (int e : v1)        {                cout << e << ' ';        }        cout << endl;        vector<int> v2 = v1;        for (int e : v1)        {                cout << e << ' ';        }        cout << endl;}

复制代码

4.2赋值重载

赋值重载我们用现代写法来写：

1. void Swap(vector<T>& v)
2. {
3.         swap(_start, v._start);
4.         swap(_finish, v._finish);
5.         swap(_end_of_storage, v._end_of_storage);
6. }
7. vector<T>& operator=(vector<T> v)
8. {
9.         Swap(v);
10.         return *this;
11. }

复制代码

测试一下：

1. void test_vector8(){        vector<int> v1;        v1.push_back(1);        v1.push_back(2);        v1.push_back(3);        v1.push_back(4);        cout << "v1：";        for (int e : v1)        {                cout << e << ' ';        }        cout << endl;        vector<int> v2;        v2.push_back(10);        v2.push_back(20);        v2.push_back(30);        cout << "v2赋值前：";        for (int e : v2)        {                cout << e << ' ';        }        cout << endl;        v2 = v1;        cout << "v2赋值后：";        for (int e : v2)        {                cout << e << ' ';        }        cout << endl;}

复制代码

4.3迭代器区间构造

1. template<class InputIterator>
2. vector(InputIterator first, InputIterator last)
3. {
4.         while (first != last)
5.         {
6.                 push_back(*first);
7.                 first++;
8.         }
9. }

复制代码

一个类模板的成员函数，还可以是一个函数模板
这里InputIterator就是函数模板，可以自动实例化出差别类型的迭代器。
来测试一下：

1.         void test_vector9()        {                vector<int> v1;                v1.push_back(1);                v1.push_back(2);                v1.push_back(3);                v1.push_back(4);                cout << "v1：";                for (int e : v1)                {                        cout << e << ' ';                }                cout << endl;                vector<int> v2(v1.begin(), v1.end());                cout << "v2：";                for (int e : v2)                {                        cout << e << ' ';                }                cout << endl;        }

复制代码

OK，这次vector的认识就到这里了。
欢迎指正和补充。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4