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的初始化
无参构造:
构造并初始化:用n个value初始化
- vector<int> v2(10, 1);//10个1
复制代码 迭代器区间初始化:
- vector<int> v3(v2.begin(), v2.end());
复制代码 拷贝构造:
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* 。因此迭代器失效,现实就是迭代器 底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是步伐崩溃(即 假如继续使用已经失效的迭代器,步伐大概会崩溃)。 - #include <iostream>
- #include <vector>
- using namespace std;
- int main()
- {
- int a[] = { 1, 2, 3, 4 };
- vector<int> v(a, a + sizeof(a) / sizeof(int));
- // 使用find查找3所在位置的iterator
- vector<int>::iterator pos = find(v.begin(), v.end(), 3);
- // 删除pos位置的数据,导致pos迭代器失效。
- v.erase(pos);
- cout << *pos << endl; // 此处会导致非法访问
- return 0;
- }
复制代码 erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理 论上讲迭代器不应该会失效,但是:假如pos刚好是最后一个元素,删完之后pos刚好是end 的位置,而end位置是没有元素的,那么pos就失效了。因此删除vector中任意位置上元素 时,vs就以为该位置迭代器失效了。
迭代器失效办理办法:在使用前,对迭代器重新赋值即可。 3.vector的模仿实现
3.1结构的界说
这里我们参考STL源码剖析实现一个简易版本的vector
成员变量的界说:
- #include <iostream>
- #include <assert.h>
- using namespace std;
- namespace Ro
- {
- template<class T>
- class vector
- {
- public:
- typedef T* iterator;
- private:
- iterator _start;
- iterator _finish;
- iterator _end_of_storage;
- };
- }
复制代码 这里各人大概会发现和模仿实现string的写法怎么不一样?
其实这就是参考STL的写法,虽然写法差别,但其实效果是大差不差的。
如图:
我们可以通过指针减指针的做法得到size和capacity。
这里同样和模仿实现string一样使用命名空间来和库中的vector区分开来,而且这里使用类模板是为了存储差别类型的数据,
这里顺带直接将size()和capacity()的接口实现出来,同时给成员变量加一个缺省值给初始化列表用
- namespace Ro
- {
- template<class T>
- class vector
- {
- public:
- typedef T* iterator;
- size_t size() const
- {
- return _finish - _start;
- }
- size_t capacity() const
- {
- return _end_of_storage - _start;
- }
- private:
- iterator _start = nullptr;
- iterator _finish = nullptr;
- iterator _end_of_storage = nullptr;
- };
- }
复制代码 3.2构造函数和析构函数
构造:
这里初始化列表不写也会走,通过给的缺省值来初始化
析构函数:
- ~vector()
- {
- if (_start)
- {
- delete[] _start;
- _start = _finish = _end_of_storage = nullptr;
- }
- }
复制代码 3.3reverse()
由于背面大部分函数接口都需要扩容,所以为了背面方便,我们先实现reverse
- void reverse(size_t n)
- {
- if (n > capacity())
- {
- if (_finish == _end_of_storage)
- {
- size_t old_size = size();
- T* tmp = new[n];
- if (_start)
- {
- memcpy(tmp, _start, sizeof(T) * old_size);
- delete[] _start;
- }
- _start = tmp;
- _finish = tmp + old_size;
- _end_of_storage = tmp + n;
- }
- }
- }
复制代码 这里我们要先将size()存下来,不然在给_finish更新时,会出现野指针。如图:
一般环境下都不会举行缩容的,所以我们在实现的时候不考虑缩容。另外,这里还会有一个坑,背面出错时我们再办理并说明
3.4push_back()和operator[]
为了让我们的vector能够跑起来,先来实现一下push_back接口
- void push_back(const T& val)
- {
- if (_finish == _end_of_storage)
- {
- reverse(capacity() == 0 ? 4 : capacity() * 2);
- }
- *_finish = val;
- _finish++;
- }
复制代码 先检查容量有没有满,满了就扩容,这里我们扩容就扩2倍,然后再插入数据,_finish指针++,指向下一个位置。
为了接下来方便测试我们先来实现 下标+[] 来访问数据
operator[]:
T&: T是我们不知道数据的类型,加&是为了减少拷贝
- T& operator[](size_t i)
- {
- assert(i < size());
- return _start[i];
- }
- const T& operator[](size_t i) const
- {
- assert(i < size());
- return _start[i];
- }
复制代码 测试一下:
- void test_vector1()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- //v.push_back(5);
- for (int i = 0; i < v.size(); i++)
- {
- cout << v[i] << ' ';
- }
- cout << endl;
- }
复制代码 先测试一下扩容前的1 2 3 4,然后再测试一下扩容后的1 2 3 4 5
没有问题
3.5迭代器的实现
这里我们来实现一下普通迭代器和const迭代器
- 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;
- }
复制代码 普通迭代器可读可写,const迭代器可读但是不可写。
测试一下迭代器遍历,同样范围for也可以使用了:
- void test_vector2()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- v.push_back(5);
- vector<int>::iterator it = v.begin();
- while (it != v.end())
- {
- cout << *it << ' ';
- it++;
- }
- cout << endl;
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- }
复制代码
普通迭代器可写
- void test_vector2()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- v.push_back(5);
- vector<int>::iterator it = v.begin();
- while (it != v.end())
- {
- *it *= 2;
- it++;
- }
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- }
复制代码
const迭代器不可写
所以迭代器要正确匹配使用。
3.6深拷贝
前面我们提到过,扩容时另有一个坑没说,其实就是memcpy浅拷贝的问题。
假如我们vector存的是string这种自界说类型会发生什么?
- void test_vector3()
- {
- vector<string> v;
- v.push_back("111111111111111111111111");
- v.push_back("111111111111111111111111");
- v.push_back("111111111111111111111111");
- v.push_back("111111111111111111111111");
- //v.push_back("111111111111111111111111");
- for (string& s : v)
- {
- cout << s << ' ';
- }
- cout << endl;
- }
复制代码 我们来看看扩容前和扩容后:
扩容前:
扩容前没有问题。那扩容后呢?
扩容后:
扩容后出问题了,运行崩溃,且打印效果错了,这是为什么?
其实就是memcpy由于浅拷贝导致的,如图:
那么整个时候就应该要深拷贝,tmp创建自己的空间存放拷贝的数据
- void reverse(size_t n)
- {
- if (n > capacity())
- {
- if (_finish == _end_of_storage)
- {
- size_t old_size = size();
- T* tmp = new T[n];
- if (_start)
- {
- //memcpy(tmp, _start, sizeof(T) * old_size);
- for (int i = 0; i < old_size; i++)
- {
- tmp[i] = _start[i];//T会调用自己的深拷贝
- }
- delete[] _start;
- }
- _start = tmp;
- _finish = tmp + old_size;
- _end_of_storage = tmp + n;
- }
- }
- }
复制代码 这里我们可以直接赋值,假如T是内置类型,一个一个拷贝没有问题,假如是自界说类型,就让T自己去调用它自己的深拷贝,也没有问题。
测试一下:
现在就不会出错了。
3.7resize()
假如n小于size,有效数据就会变为n个,容量稳定
大于size小于capacity就会将数据扩大到n个,且会把size到n之间的数据初始化为val
大于capacity的话就会先扩容,再初始化。
- void resize(size_t n, const T& val = T())
- {
- if (n < size())
- {
- _finish = _start + n;
- }
- else
- {
- reverse(n);
- while (_finish != _start + n)
- {
- *_finish = val;
- _finish++;
- }
- }
- }
复制代码 这里缺省值我们不能直接给0或者其他,由于存储的数据类型我们不知道,这里可以用T()匿名对象作为缺省值,让T调用自己的构造去初始化。
留意:匿名对象的生命周期只在那一行,所以要使用const引用匿名对象,目的就是延长匿名对象的生命周期。
测试一下:
- void test_vector4()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- v.resize(10, 1);
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- }
复制代码
3.8pop_back()和empty()
当没有数据时,即为空时不能尾删
所以先来实现判空:
- bool empty() const
- {
- return _start == _finish;
- }
复制代码 尾删:
- void pop_back()
- {
- assert(!empty());
- _finish--;
- }
复制代码 比力简单就不测试了。
3.9insert()
在pos前插入val,先将pos后元素全部向后移动一格,在将val插入pos位置
- void insert(iterator pos, const T& val)
- {
- assert(pos <= _finish && pos >= _start);
- if (_finish == _end_of_storage)
- {
- reverse(capacity() == 0 ? 4 : capacity() * 2);
- }
- iterator end = _finish - 1;
- while (end >= pos)
- {
- *(end + 1) = *end;
- end--;
- }
- *pos = val;
- _finish++;
- }
复制代码 分别测试一下扩容前和扩容后:
- void test_vector5()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- //v.push_back(4);
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- vector<int>::iterator pos = find(v.begin(), v.end(), 2);
- v.insert(pos, 10);
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- }
复制代码 扩容前:
扩容后:
这里效果出错了,为什么呢?
其实就是由于我们前面提到的迭代器失效问题。
由于扩容之后,pos还是指向旧空间的2,但是我们现在要在新空间的2前面插入10,所以我们应该在扩容后更新pos指针。
- void insert(iterator pos, const T& val)
- {
- assert(pos <= _finish && pos >= _start);
- if (_finish == _end_of_storage)
- {
- size_t len = pos - _start;
- reverse(capacity() == 0 ? 4 : capacity() * 2);
- pos = _start + len;
- }
- iterator end = _finish - 1;
- while (end >= pos)
- {
- *(end + 1) = *end;
- end--;
- }
- *pos = val;
- _finish++;
- }
复制代码 现在再测试一下:
现在就没有问题了。
但是需要留意的是,在insert中我们虽然更新了形参pos,但是外貌的实参pos并没有改变,形参是实参的临时拷贝,所以形参改变不会影响形参。
那怎么办?引用形参可以吗?这里我们给出办理办法,不推荐引用,可以通过返回值来返回更新之后的pos。
不采用引用形参的原因
- 避免意外修改:
- 假如 insert 函数通过引用形参返回插入位置,这大概会导致意外的修改。由于引用本身可以被重新赋值,函数调用者大概会不小心修改这个引用,从而改变了本来应该表现插入位置的信息。
- 语义不符:
- 从语义角度看, insert 操作主要是向容器中添加元素,重点在于插入操作本身和插入后的元素位置。返回一个表现插入位置的迭代器更符合这个操作的语义,而通过引用形参返回位置不太符合这种直观的明白。引用形参更多地用于在函数内部修改外部变量的值,而 insert 的主要目的不是修改外部传入的表现位置的变量,而是告知调用者新元素的位置。
- iterator insert(iterator pos, const T& val)
- {
- assert(pos <= _finish && pos >= _start);
- if (_finish == _end_of_storage)
- {
- size_t len = pos - _start;
- reverse(capacity() == 0 ? 4 : capacity() * 2);
- pos = _start + len;
- }
- iterator end = _finish - 1;
- while (end >= pos)
- {
- *(end + 1) = *end;
- end--;
- }
- *pos = val;
- _finish++;
- return pos;
- }
复制代码 4.0erase()
同样erase也会有迭代器失效的问题,所以我们也可以和insert一样通过返回值来更新一下pos
- iterator erase(iterator pos)
- {
- assert(pos >= _start && pos < _finish);
- //挪动数据
- iterator end = pos + 1;
- while (end < _finish)
- {
- *(end - 1) = *end;
- end++;
- }
- _finish--;
- return pos;
- }
复制代码 测试一下:
- void test_vector6()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- v.push_back(5);
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- vector<int>::iterator pos = find(v.begin(), v.end(), 2);
- v.erase(pos);
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- }
复制代码
假如我们要删除全部的偶数呢?
- void test_vector6()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- v.push_back(5);
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- vector<int>::iterator it = v.begin();
- while (it != v.end())
- {
- if (*it % 2 == 0) it = v.erase(it);
- else it++;
- }
- /*vector<int>::iterator pos = find(v.begin(), v.end(), 2);
- v.erase(pos);*/
- for (int e : v)
- {
- cout << e << ' ';
- }
- cout << endl;
- }
复制代码
4.1拷贝构造
拷贝构造可以使用传统写法,也可以使用现代写法,这里我们直接干
- vector(const vector<T>& v)
- {
- reverse(v.size());
- for (auto& e : v)
- {
- push_back(e);
- }
- }
复制代码 测试一下:
- 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赋值重载
赋值重载我们用现代写法来写:
- void Swap(vector<T>& v)
- {
- swap(_start, v._start);
- swap(_finish, v._finish);
- swap(_end_of_storage, v._end_of_storage);
- }
- vector<T>& operator=(vector<T> v)
- {
- Swap(v);
- return *this;
- }
复制代码 测试一下:
- 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迭代器区间构造
- template<class InputIterator>
- vector(InputIterator first, InputIterator last)
- {
- while (first != last)
- {
- push_back(*first);
- first++;
- }
- }
复制代码 一个类模板的成员函数,还可以是一个函数模板
这里InputIterator就是函数模板,可以自动实例化出差别类型的迭代器。
来测试一下:
- 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企服之家,中国第一个企服评测及商务社交产业平台。 |