个性手绘个人网站模板下载广告推广投放平台

目录

1.erase

测试代码1

测试代码2

检测VS中删除后原迭代器是否可以访问

insert和erase的迭代器总结

2.pop_back

 测试代码

3.resize

测试代码 

4.operator=

测试代码

5.深拷贝问题解决

解决方法

测试代码

6.构造函数的其他形式的实现

测试代码

测试代码

7.STL源码的构造函数中有趣的地方

---

承接CD43.vector模拟实现(2)文章

1.erase

参数保持一样的类型:

之前在CD43.vector模拟实现(2)文章提到过迭代器失效问题,因此返回类型为iterator,erase在某些情况下会缩容,为了节省存储空间或者有其他的目的,删除元素的算法和CD38.【C++ Dev】string类的模拟实现(2)文章的算法一样,

注意返回值的要求:指向被删除元素之后的位置

如果不缩容,是这样写的:

iterator erase(iterator position)
{//position最大为finish-1assert(position >= start && position < finish);iterator i = position+1;while (i < finish){*(i-1) = *i;i++;}finish--;return position;
}

测试代码1

void test8()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.erase(v.begin() + 1);return;
}

运行结果:

删除前:

删除后:

测试代码2

void test9()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);auto pos = v.begin();while (v.size())pos=v.erase(pos);//规范写法
}

运行结果:退出代码为0,正常结束

检测VS中删除后原迭代器是否可以访问

只需要验证删除后,能否利用原迭代器继续删除数据

void test10()
{std::vector<int> v;for (size_t i=0;i<9;i++)v.push_back(i);auto pos = v.begin()+3;v.erase(pos);v.erase(pos);return;
}

第一次删除没有问题,但第二次删除会报错,尽管pos仍然指向原来的内存数组

现认为erase有可能不存在迭代器失效问题,仍然能访问,但是通常认为迭代器失效,因为认为访问的不是原来的值 

某些内存紧张的系统上erase后可能会异地缩容,导致使用迭代器访问的不是原来的值

insert和erase的迭代器总结

vector的erase和insert的参数迭代器使用后后,不能再访问这个迭代器,通常认为失效,访问结果是未定义的(可能可以访问,也有可能不能访问)

2.pop_back

参数保持一样的类型:

既然是尾删,那就要删除end()的前一个元素

写法1:

void pop_back()
{erase(--end());//end()返回的是迭代器,需要重载operator--
}

注意:一定不能写成erase(--finish)!!!否则erase的断言条件成立,position==finish

写法2:

void pop_back()
{erase(finish-1);//不用在pop_back中finish--,erase中处理了
}

 测试代码

void test11()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.pop_back();return;
}

删除前:

删除后:

3.resize

参数保持一样的类型:

分析函数的参数

void resize(size_type n, value_type val = value_type())

第一个是元素个数n,第二个参数用到了缺省参数+匿名对象value_type()

对于自定义类型,匿名对象不用解释,但对于内置类型(例如int类型)来说怎么理解?

C++中将内置类型升级为模版,有自己的构造函数,例如以下代码:

int main()
{int val1 = int(1);int val2 = int();//匿名int对象std::cout << "val1=" << val1 << std::endl;std::cout << "val2=" << val2 << std::endl;return 0;
}

运行结果:

所以resize无论接收到的是内置类型的模版,还是自定义类型的模版都能很好的处理.

resize的算法和之前CD39.【C++ Dev】string类的模拟实现(3)文章的string的resize类似.

void resize(size_type n, value_type val = value_type())
{if (n < capacity())finish = start + n;else{//如果vector不为空,reserve不会修改start和finish的相对位置关系reserve(n);while (finish!=start+n){*finish = val;finish++;}}
}

测试代码 

void test12()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.resize(6, 0xFFFFFFFF);return;
}

运行结果: 

4.operator=

operator=不能借助浅拷贝,必须手动实现深拷贝,和CD40.【C++ Dev】string类的模拟实现(4)文章的string的operator=实现思想一样

注意要用const修饰,避免权限放大 

可以不像上面图片那样使用引用,可以直接使用vector<T> x,调用拷贝构造函数

void swap(vector<T> tmp)
{std::swap(start, tmp.start);std::swap(finish, tmp.finish);std::swap(end_of_storage, tmp.end_of_storage);
}vector& operator= (vector<T> x)
{swap(x);//交换3个成员变量return *this;
}

测试代码

void test13()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);mystl::vector<int> tmp=v;for (auto& a : tmp)std::cout << a << " ";return;
}

运行结果:

5.深拷贝问题解决

在CD42.vector模拟实现(1)文章提到了一个问题,本文解决

当vector的模版是内置类型时,增删查改没有问题,但如果是自定义类型呢?

void test14()
{mystl::vector<std::string> v;v.push_back("123123123123123123123");v.push_back("456456456456456456");v.push_back("789789789789789789");v.push_back("123123123123123123123");v.push_back("456456456456456456");v.push_back("789789789789789789");for (auto a : v)std::cout << a << " ";return;
}

运行结果报错:

如果读者对魔数0xDDDDDDDD比较熟悉,应该指的是被释放(deallocated v.解除分配)的空间,而程序又想访问,会造成访问权限的冲突

 (来自https://www.softwareverify.com/blog/unusual-memory-bit-patterns/文章)

下断点到test14函数的return处,F11单步执行,会发现是执行delete[] start后报错:

思路:检查是哪个函数提前释放了start指向的空间

进一步分析:哪个功能需要释放start指向的空间? 答:异地扩容,需要将旧空间的数据拷贝到新空间,再释放原空间,很有可能是start的值仍然指向旧空间,导致访问发生冲突

异地扩容在reserve函数中,查其bug:

问题在memove,虽然vector是深拷贝,但vector上存储了string对象,调用delete[] start时,会自动调用string的析构函数,释放string的空间,导致string对象是浅拷贝

验证0xDDDDDDDD的产生:

解决方法

删掉memmove,手动调用operator=复制成员变量,进行深拷贝

if (start)
{for (size_type i = 0; i < len; i++){tmp[i] = start[i];}delete[] start;
}

运行结果:
 

当然,拷贝构造函数也要修改:

vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0)
{reserve(x.capacity());for (size_type i = 0; i < x.size(); i++){start[i] = x.start[i];}finish = start + x.size();

测试代码

void test15()
{mystl::vector<std::string> v;v.push_back("123123123123123123123");v.push_back("456456456456456456");v.push_back("789789789789789789");v.push_back("123123123123123123123");v.push_back("456456456456456456");v.push_back("789789789789789789");mystl::vector<std::string> tmp = v;for (auto a : tmp)std::cout << a << " ";return;
}

运行结果:

6.构造函数的其他形式的实现

在CD42.vector模拟实现(1)文章只实现的第一种写法,这里实现剩下两种

fill(2):省去空间配置器

explicit vector(size_type n, const value_type& val = value_type()):start(nullptr),finish(nullptr),end_of_storage(nullptr)
{resize(n, val);
}

注:explicit关键字在CD24.【C++ Dev】类和对象(15) 初始化列表(下) 对象隐式类型转换和explicit文章讲过,是为了禁止类对象之间的隐式转换

测试代码

void test16()
{mystl::vector<int> v(3,0xFFFFFFFF);for (auto a : v)std::cout << a << " ";return;
}

运行结果:

range(3):省去空间配置器

注意不能写成

vector (iterator first, iterator last);

 如果定义为iterator类型,就只能使用vector类型来初始化,不具有适用性

template <class InputIterator>vector (InputIterator first, InputIterator last);

注意:first和last定义为InputIterator,

区间是左闭右开的,即[first,last)

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{InputIterator i = first;while (i != last){push_back(*i);i++;}
}

测试代码

void test17()
{mystl::vector<std::string> v;v.push_back({ "12" });v.push_back({ "23" });v.push_back({ "34" });v.push_back({ "45" });mystl::vector<std::string> tmp(v.begin()+1,v.end()-1);for (auto a : tmp)std::cout << a << " ";return;
}

运行结果:

如果写成这样: 

vector(iterator first, iterator last)
{iterator i = first;while (i != last){push_back(*i);i++;}
}

测试代码:

void test18()
{std::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);mystl::vector<int> v(ls.begin(), ls.end());for (auto a : v)std::cout << a << " ";return;
}

list迭代器不能像数组一样可以连续访问(后面文章会讲),所以会报错

如果改成InputIterator,就没有问题:

7.STL源码的构造函数中有趣的地方

(来自SGI STL v3.0的源码)

画框的n定义了三种类型size_type、int和long,这样做的原因是什么?

运行代码无法通过编译

void test19()
{mystl::vector<int> v(5,3);return;
}

报错信息: 

 模板实例化上下文(最早的实例化上下文)为
1>        C:\Users\Administrator\source\repos\myvector\test.cpp(219,22):
1>        查看对正在编译的函数 模板 实例化“mystl::vector<int>::vector<int>(InputIterator,InputIterator)”的引用
1>        with
1>        [
1>            InputIterator=int
1>        ]
1>            C:\Users\Administrator\source\repos\myvector\test.cpp(219,22):
1>            请参阅 "test19" 中对 "mystl::vector<int>::vector" 的第一个引用

使用者想匹配explicit vector(size_type n, const value_type& val = value_type()),但是编译器匹配错了.

原因:对于常数5和3,编译器默认认为是int类型,由于size_type n和const value_type& val类型上有差别,但是InputIterator first和InputIterator last在类型上一致,编译器会匹配最符合的那个

解决方法1:让first和last类型不一样即可

例如mystl::vector<int> v(5u,3),其中u代表5为unsigned int类型,即重定义后的size_type类型

解决方法2:STL库的解决方法: 定义一个重载函数

参数n类型为int: 

explicit vector(int n, const value_type& val = value_type()):start(nullptr), finish(nullptr), end_of_storage(nullptr)
{resize(n, val);
}

运行结果:

参数n类型为long:

explicit vector(long n, const value_type& val = value_type()):start(nullptr), finish(nullptr), end_of_storage(nullptr)
{resize(n, val);
}