vector 是表示可变大小数组的序列容器(动态数组),包含三个迭代器,start 和 finish 之间是已经被使用的空间范围,end_of_storage 是整块连续空间(包括备用空间的尾部)。
就像数组一样,vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
与其它动态序列容器相比(deques, lists and forward_lists), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起 lists 和 forward_lists 统一的迭代器和引用更好
(constructor)构造函数声明 接口说明 vector()(重点) 无参构造 vector(size_type n, const value_type& val = value_type()) 构造并初始化 n 个 val vector (const vector& x) (重点) 拷贝构造 vector (InputIterator first, InputIterator last) 使用迭代器进行初始化构造 // constructing vectors #include
#include int main () { // constructors used in the same order as described above: std::vector<int> first; // 构造无参的vector std::vector<int> second (4,100); // four ints with value 100 std::vector<int> third (second.begin(),second.end()); // iterating through second std::vector<int> fourth (third); // a copy of third // the iterator constructor can also be used to construct from arrays: int myints[] = {16,2,77,29}; std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) ); std::cout << "The contents of fifth are:"; for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
结果:
The contents of fifth are: 16 2 77 29
- 1
iterator 的使用 接口说明 begin() 、end() begin() 获取第一个数据位置的 iterator / const_iterator, end() 获取**最后一个数据的下一个位置**的iterator/const_iterator rbegin() 、rend() rbegin() 获取最后一个数据位置的reverse_iterator,rend() 获取第一个数据前一个位置的reverse_iterator #include
#include using namespace std; void PrintVector(const vector<int>& v) { // const对象使用const迭代器进行遍历打印 vector<int>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; } int main() { // 使用push_back插入4个数据 vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 使用迭代器进行遍历打印 vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; // 使用迭代器进行修改 it = v.begin(); while (it != v.end()) { *it *= 2; ++it; } // 使用反向迭代器进行遍历再打印 vector<int>::reverse_iterator rit = v.rbegin(); while (rit != v.rend()) { cout << *rit << " "; ++rit; } cout << endl; PrintVector(v); return 0; }
- 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
结果:
1 2 3 4 8 6 4 2 2 4 6 8
- 1
- 2
- 3
容量空间 接口说明 size 获取数据个数 capacity 获取容量大小 empty 判断是否为空 resize(重点) 改变 vector 的 size reserve (重点) 改变 vector 的 capacity
- capacity的代码在vs和g++下分别运行会发现,vs下 capacity 是按1.5倍增长的, g++是按2倍增长的。这个问题经常会考察,不要固化的认为,顺序表增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
- reserve() 只负责开辟空间,如果确定知道需要用多少空间,reserve() 可以缓解vector增容的代价缺陷问题。
- resize() 可以改变有效空间的大小,也有初始化的功能。
// 测试vector的默认扩容机制 void TestVectorExpand() { size_t sz; vector<int> v; sz = v.capacity(); cout << "making v grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } } //vs:运行结果:vs下使用的STL基本是按照1.5倍方式扩容 making foo grow: capacity changed: 1 capacity changed: 2 capacity changed: 3 capacity changed: 4 capacity changed: 6 capacity changed: 9 capacity changed: 13 capacity changed: 19 capacity changed: 28 capacity changed: 42 capacity changed: 63 capacity changed: 94 capacity changed: 141 //g++运行结果:linux下使用的STL基本是按照2倍方式扩容 making foo grow: capacity changed: 1 capacity changed: 2 capacity changed: 4 capacity changed: 8 capacity changed: 16 capacity changed: 32 capacity changed: 64 capacity changed: 128
- 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
// 如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够 // 就可以避免边插入边扩容导致效率低下的问题了 void TestVectorExpandOP() { vector<int> v; size_t sz = v.capacity(); v.reserve(100); // 提前将容量设置好,可以避免一遍插入一遍扩容 cout << "making bar grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
vector增删查改 接口说明 push_back(重点) 尾插 pop_back (重点) 尾删 find 查找。(注意这个是算法模块实现,不是vector的成员接口) insert 在position之前插入val erase 删除position位置的数据 swap 交换两个vector的数据空间 operator[] (重点) 像数组一样访问 // find / insert / erase #include
#include #include 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位置之前插入30 v.insert(pos, 30); vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据 v.erase(pos); it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; } //结果 1 2 30 3 4 1 2 30 4
- 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
// operator[]+index 和 C++11中vector的新式for+auto的遍历 // vector使用这两种遍历方式是比较便捷的。 #include
#include using namespace std; int main() { int a[] = { 1, 2, 3, 4 }; vector<int> v(a, a + sizeof(a) / sizeof(int)); // 通过[]读写第0个位置。 v[0] = 10; cout << v[0] << endl; // 通过[i]的方式遍历vector for (size_t i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; vector<int> swapv; swapv.swap(v); cout << "v data:"; for (size_t i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; cout << "swapv data:"; for (size_t i = 0; i < swapv.size(); ++i) cout << swapv[i] << " "; cout << endl; // C++11支持的新式范围for遍历 for(auto x : v) cout<< x << " "; cout<<endl; return 0; } //结果 10 10 2 3 4 v data: swapv data:10 2 3 4
- 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
- vec.clear() :清空内容,但是不释放内存。
- vector().swap(vec) :清空内容,且释放内存,得到一个全新的 vector
- vec,shrink_to_fit() :请求容器降低其 capacity 和 size 匹配
- vec.clear() ; vec.shrink_to_fit() :清空内容,且释放内存
对于vector可能会导致其迭代器失效的操作有:
#include
using namespace std; #include int main() { vector<int> v{1,2,3,4,5,6}; auto it = v.begin(); // 1、将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容 // v.resize(100, 8); // 2、reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变 // v.reserve(100); // 3、插入元素期间,可能会引起扩容,而导致原空间被释放 // v.insert(v.begin(), 0); // v.push_back(8); // 4、给vector重新赋值,可能会引起底层容量改变 // v.assign(100, 8); while(it != v.end()) { cout<< *it << " " ; ++it; } cout<<endl; return 0; /* 出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉, 而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的 空间,而引起代码运行时崩溃。 解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新 赋值即可。 */ }
- 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
#include
using namespace std; #include 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; // 此处会导致非法访问,因为pos的意义已经变了 return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
erase 删除 pos 位置元素后,pos 位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果 pos 刚好是最后一个元素,删完之后 pos 刚好是end的位置,而 end 位置是没有元素的,那么pos就失效了。因此删除vector 中任意位置上元素时,vs 就认为该位置迭代器失效了(linux下可能不会报错,但是意义也是变了)。
解决方案如下: 迭代器失效解决办法:在使用前,对迭代器重新赋值即可。
#include
using namespace std; #include //很显然这个是错的,因为判断到2的时候,2是偶数,所以erase掉,但是这个时候 迭代器it 就失效了 //再者,当erase掉2后,数组元素会向前挪动,但是it又被++了,导致3并没有被判断,造成漏判了 //而到4的时候,将4 erase掉后,数组元素向前挪动,而end()也会向前更新挪动,导致it++后移到了end()后面,造成越界 int main() { vector<int> v{ 1, 2, 3, 4 }; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); ++it; } return 0; } //这个写法是对的,也是erase避免迭代器失效的解决方法 //因为erase后迭代器就失效了,但是erase函数会返回一个有效的迭代器,所以当我们要删除某个元素的时候 //需要让 it = v.erase(it),这样子就能避免失效问题 int main() { vector<int> v{ 1, 2, 3, 4 }; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) it = v.erase(it); else ++it; } return 0; }
- 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
- 注意:Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端。
// 1. 扩容之后,迭代器已经失效了,程序虽然可以运行,但是运行结果已经不对了 int main() { vector<int> v{1,2,3,4,5}; for(size_t i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; auto it = v.begin(); cout << "扩容之前,vector的容量为: " << v.capacity() << endl; // 通过reserve将底层空间设置为100,目的是为了让vector的迭代器失效 v.reserve(100); cout << "扩容之后,vector的容量为: " << v.capacity() << endl; // 经过上述reserve之后,it迭代器肯定会失效,在vs下程序就直接崩溃了,但是linux下不会 // 虽然可能运行,但是输出的结果是不对的 while(it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; } 程序输出: 1 2 3 4 5 扩容之前,vector的容量为: 5 扩容之后,vector的容量为: 100 0 2 3 4 5 409 1 2 3 4 5 // 2. erase删除任意位置代码后,linux下迭代器并没有失效 // 因为空间还是原来的空间,后序元素往前搬移了,it的位置还是有效的,但是意义已经变了 #include
#include int main() { vector<int> v{1,2,3,4,5}; vector<int>::iterator it = find(v.begin(), v.end(), 3); v.erase(it); cout << *it << endl; while(it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; } 程序可以正常运行,并打印: 44 5 // 3: erase删除的迭代器如果是最后一个元素,删除之后it已经超过end // 此时迭代器是无效的,++it导致程序崩溃 int main() { vector<int> v{1,2,3,4,5}; // vector v{1,2,3,4,5,6}; auto it = v.begin(); while(it != v.end()) { if(*it % 2 == 0) v.erase(it); ++it; } for(auto e : v) cout << e << " "; cout << endl; return 0; } ======================================================== // 使用第一组数据时,程序可以运行 [liren@VM-0-3-centos 20220729]$ g++ testVector.cpp -std=c++11 [liren@VM-0-3-centos 20220729]$ ./a.out 1 3 5 ========================================================= // 使用第二组数据时,程序最终会崩溃 [liren@VM-0-3-centos 20220729]$ vim testVector.cpp [liren@VM-0-3-centos 20220729]$ g++ testVector.cpp -std=c++11 [liren@VM-0-3-centos 20220729]$ ./a.out Segmentation fault //因为判断6的时候,erase掉后,数组元素向前挪动,end()也向前挪动,然后it++,导致跳到了end()后面,造成越界
- 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
从上述三个例子中可以看到:SGI STL中,迭代器失效后,代码并不一定会崩溃,但是运行结果肯定不对,但是如果 it 不在 begin和end范围内,也就是越界了,肯定会崩溃的。
- 与vector类似,string 在 插入+扩容操作+erase 之后,迭代器也会失效
#include
void TestString() { string s("hello"); auto it = s.begin(); // 放开之后代码会崩溃,因为resize到20会string会进行扩容 // 扩容之后,it指向之前旧空间已经被释放了,该迭代器就失效了 // 后序打印时,再访问it指向的空间程序就会崩溃 //s.resize(20, '!'); while (it != s.end()) { cout << *it; ++it; } cout << endl; it = s.begin(); while (it != s.end()) { it = s.erase(it); // 按照下面方式写,运行时程序会崩溃,因为erase(it)之后 // it位置的迭代器就失效了 // s.erase(it); ++it; } }
- 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
总结:
其中的几个要点问题:
为何要重载一个 int 版本的构造函数,而不是直接使用 size_t 版本的?
为什么不能用memcpy进行拷贝而用 “=” 就可以呢?(具体看下面的解释)
对于内置类型,用memcpy就是一个一个字节拷过去当然没问题
但是对于自定义类型,用memcpy拷贝可能涉及到深拷贝的问题,因为像string、list这些类,里面都含有指针,若只是将他们拷贝过去,相当于只是浅拷贝,这样子调用了析构函数,对同一块空间析构了两次,程序就奔溃了。
而如果用 “=”,其实相当于调用自定义类型自己实现的赋值运算符拷贝,这是深拷贝,如下赋值运算符的实现,_start[i] 和 v._start[i]都为string类型,用了 “=” 实则又就是调用了string自己的赋值运算符拷贝函数,这样子就实现了深拷贝。
vector<T>& operator=(const vector<T>& v)
{
reserve(v.capacity());
for (size_t i = 0; i < v.size(); ++i)
_start[i] = v._start[i];
_finish = _start + v.size();
return *this;
}
#pragma once
#include
#include
using namespace std;
namespace liren
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
public:
vector()
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{}
//(注意,使用reserve的话需要初始化一下变量,因为reserve中需要用到这些变量,若为随机值则乱套了)
// 但是调试发现,vs2022做了优化,默认替我们初始化为nullptr,但是为了可移植性,强烈建议还是加上初始化列表
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
/*
// 第一种写法,memcpy有缺陷,会引发深层次的深浅拷贝问题
_start = new T[v.capacity()];
memcpy(_start, v.cbegin(), v.size() * sizeof(T));
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
*/
// 第二种写法,复用reserve开空间,用循环给空间拷贝
reserve(v.capacity());
for (size_t i = 0; i < v.size(); ++i)
push_back(v._start[i]);
}
//第一种写法,自己实现
/*vector& operator=(const vector& v)
{
reserve(v.capacity());
for (size_t i = 0; i < v.size(); ++i)
_start[i] = v._start[i];
_finish = _start + v.size();
return *this;
}*/
// 第二种写法,复用拷贝构造,且不需要接收引用的参数,只需传值
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
// 类模板的成员函数,还可以再是函数模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
//对于需要继续构造一个int参数的函数,其实这里改成模板T,让编译器去推类型即可
//这里的T()表示构造函数,对于内置类型也会调用其构造函数,若不给值则默认初始化为0
vector(size_t n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
/*
* 理论上将,提供了vector(size_t n, const T& value = T())之后
* vector(int n, const T& value = T())就不需要提供了,但是对于:
* vector v(10, 5);
* 编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型
* 就不会走vector(size_t n, const T& value = T())这个构造方法,
* 最终选择的是:vector(InputIterator first, InputIterator last)
* 因为编译器觉得区间构造两个参数类型一致,因此编译器就会将InputIterator实例化为int
* 但是10和5根本不是一个区间,编译时就报错了
* 故需要增加该构造方法
*/
vector(int n, const T& value = T())
: _start(new T[n])
, _finish(_start + n)
, _end_of_storage(_finish)
{
for (int i = 0; i < n; ++i)
{
_start[i] = value;
}
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
iterator begin()
{
return _start;
}
const_iterator cbegin() const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator cend() const
{
return _finish;
}
T& operator[](size_t index)
{
assert(index < capacity());
return _start[index];
}
const T& operator[](size_t index) const
{
assert(index < capacity());
return _start[index];
}
void resize(size_t n, const T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
for (iterator i = _finish; i < _start + n; ++i)
{
*i = val;
}
_finish = _start + n;
}
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//拷贝的第一种写法,但是如果传的是string等自定义类型,就会出现深层次的深浅拷贝问题,不推荐
//memcpy(tmp, _start, sz * sizeof(T));
//拷贝的第二种写法,用了赋值运算符,string等底层已经实现了深拷贝,所以不会有问题
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
bool empty() const
{
return _start == _finish;
}
void pop_back()
{
assert(!this->empty());//防止_finish相等时候减到_start前面越界
--_finish;
}
void swap(vector<T>& v)
{
if (&v == this)
return;
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_end_of_storage, v._end_of_storage);
}
//STL中的insert不采用在函数中解决失效问题是因为有缺陷
//但是如果面试官要求解决失效问题,可以把下面的两点要点补上,即可解决
//所以用insert时候尽量用一次就重新查找pos的位置,避开失效问题
void insert(iterator pos, const T& x) //解决pos失效的方法一:pos用传引用
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//更新pos,解决扩容后pos变成野指针后失效的问题
pos = _start + len;
}
iterator tmp = _finish - 1; //记得是减1,因为_finish是指向最后一个元素的后面一位
while (tmp >= pos)
{
*(tmp + 1) = *tmp;
tmp--;
}
*pos = x;
++_finish;
//解决pos失效的方法二:将每次插入后pos位置向后移动一个位置,保持原来的相对位置不变
//pos = pos + 1;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
assert(!empty());
iterator begin = pos;
while (begin < _finish - 1)
{
*begin = *(begin + 1);
begin++;
}
_finish--;
return pos;
}
~vector()
{
if(_start)
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
假设模拟实现的vector中的reserve接口中,使用memcpy进行的拷贝,以下代码会发生什么问题?答案是奔溃。
int main()
{
liren::vector<liren::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
问题分析:
memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
如果拷贝的是自定义类型的元素,memcpy即高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。
以下面的代码为例子,这里有两种情况:
1、在多次的尾插中,若发生扩容,则会导致浅拷贝,最后同一块空间被析构两次,导致奔溃
int main() { liren::vector<liren::string> v; v.push_back("1111"); v.push_back("2222"); v.push_back("3333"); v.push_back("4444"); v.push_back("5555"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
2、还有一种奇怪的现象,就是在vs编译器下,对于string类型,vs多了个buf成员数组变量,用于存储比较短的字符串,一般为16个字节,当字符串长度大于buf长度时候,vs下的string才会去堆区开辟空间存放字符串。
若随着不断地插入,vector会扩容,这个时候新的数组的空间位置已经变了,但是由于第一个字符串长度大于buf长度,所以第一个字符串是存在堆区的,而因为空间位置的改变,_ptr 指向的位置被销毁了,但是由于是浅拷贝,新空间的 _ptr 也是该空间,由于被析构了,新的_ptr 就变成了野指针了,打印出来的可能是随机值。(vs2022做了优化,可能已经把这种给优化了)
//注:该情况只适用于vs下,因为每个编译器的设计方式不一样 (且vs2022做了优化,可能已经把这种给优化了) int main() { liren::vector<liren::string> v; v.push_back("111111111111111111111111111111111111111"); //插入的字符串长度大于buf的长度 v.push_back("2222"); v.push_back("3333"); v.push_back("4444"); v.push_back("5555"); for (size_t i = 0; i < v.size(); ++i) cout << v[i] << endl; cout << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
总结: T 如果是内置类型(如int)或者浅拷贝自定义类型(如Date),他们增容或者拷贝构造时,用memcpy是没有问题的。
但是 T 如果是深拷贝的自定义类型(如string),他们增容或者拷贝构造时,不能用memcpy。
STL 中是用类型萃取来区分类型的,也就是对于内置类型使用 memcpy,而对于自定义类型使用 for + 赋值。
这体现了C++极致追求效率的特点,但是缺点就是太复杂。