安丘网站建设公司,外贸建站有什么用,珠海市做网站,wordpress 本地加速目录 前言#xff1a;
1.vector的介绍及使用
1.2 vector的使用 1.2 1 vector的定义
1.2 2 vector iterator#xff08;迭代器#xff09;的使用
1.2.3 vector 空间增长问题
1.2.4 vector 增删查改
1.2.5vector 迭代器失效问题。
2.vector模拟实现
2.1 std::vect…目录 前言
1.vector的介绍及使用
1.2 vector的使用 1.2 1 vector的定义
1.2 2 vector iterator迭代器的使用
1.2.3 vector 空间增长问题
1.2.4 vector 增删查改
1.2.5vector 迭代器失效问题。
2.vector模拟实现
2.1 std::vector的核心框架接口的模拟实现bit::vector 2.2 使用memcpy拷贝问题 前言 在前面的章节我们已经接触过了关于STL的知识也就是string类我们详细介绍了string类的特性及使用而严格来说string类并没有被归为STL中因为string类的出现早于STLstring类的接口也比STL中的单个类多使得string类较其他类显得冗余这一期我们就要开始讲STL中的内容。
1.vector的介绍及使用
1. vector是表示可变大小数组的序列容器。 2. 就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3. 本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4. vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5. 因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 6. 与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。
1.2 vector的使用 vector的使用与string类相似要实现一些基本的操作如增删查改这些操作c在库中都已经实现好了接口我们只需要调用这些接口就可以实现对应的操作。c如今的地位在很大程度上是因为引入了STL这块的内容。 1.2 1 vector的定义 1.2 2 vector iterator迭代器的使用 1.2.3 vector 空间增长问题 1capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。
2reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。
3resize在开空间的同时还会进行初始化影响size。
// 测试vector的默认扩容机制
void TestVectorExpand()
{
size_t sz;
vectorint 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.4 vector 增删查改 如果我们实现增删查改只需要调用相应的接口就可以了 其中标重点的是我们在日常的开发使用vector中常用的接口需要我们重点掌握。
1.2.5vector 迭代器失效问题。 迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。 对于vector可能会导致其迭代器失效的操作有
1. 会引起其底层空间改变的操作都有可能是迭代器失效比如一些常用的接口resize、reserve、insert、assign、push_back等等。
#include iostream
using namespace std;
#include vector
int main()
{
vectorint v{1,2,3,4,5,6};
auto it v.begin();
// 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容
// v.resize(100, 8);
// reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变
// v.reserve(100);
// 插入元素期间可能会引起扩容而导致原空间被释放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 给vector重新赋值可能会引起底层容量改变
v.assign(100, 8);
/*
出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉
而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的
空间而引起代码运行时崩溃。
解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新
赋值即可。
*/
while(it ! v.end())
{
cout *it ;
it;
}
coutendl;
return 0;
}
2. 指定位置元素的删除操作--erase
#include iostream
using namespace std;
#include vector
int main()
{
int a[] { 1, 2, 3, 4 };
vectorint v(a, a sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vectorint::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就认为该位置迭代器失效了。 我们来看一个删除vector所有偶数的例子
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)v.erase(it);it;}return 0;
}
我们来运行一下这段代码 可以看到程序直接崩溃了这就是经典的迭代器失效的例子这是为什么呢我们画图来看 这是我们的vector刚开始的样子 第一次进入循环先判断it指向的数1对2取模是否为0结果不为零所以it往前走来到了2的位置 在程序发现2模2为0后2就被删除了3和4都往前移动一个位置紧接着it也往前移动了一个位置 此时end还不等于end程序判断4模2为0后又将4删除了然后end往前一个位置it又往前一个位置 可以看到此时it指向了end后面的位置而我们循环结束的条件是it等于end就结束而it在end后面他就会一直往后走循环也无法停下来不仅造成非法访问也会使程序死循环这也就是程序奔溃的原因。这个例子也再次告诉我们如果我们使用erase删除了数据那么就不要再使用pos了。 3. 与vector类似string在插入扩容操作erase之后迭代器也会失效
#include string
void TestString()
迭代器失效解决办法在使用前对迭代器重新赋值即可。
1.2.5 vector 在OJ中的使用。
1. 只出现一次的数字i
2. 杨辉三角OJ
{
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;
}
}
2.vector模拟实现 由于使用命名空间时将函数的定义和声明分到不同的文件中会引起连结错误所以我们分两个文件来实现vector一个用来实现功能一个用来测试。
2.1 std::vector的核心框架接口的模拟实现bit::vector
vector.h :
#pragma once
#includeassert.h
#includeiostream
using namespace std;namespace Myvector
{templateclass Tclass vector{public:typedef T* iterator;vector(){}vector(vectorT v){reserve(v.size());for (auto ch : v){push_back(ch);}}~vector(){delete[] _start;_start _finish _end_of_storage nullptr;}void swap(vectorT v1){std::swap(_start, v1._start);std::swap(_finish, v1._finish);std::swap(_end_of_storage, v1._end_of_storage);}vectorT operator(vectorT v){swap(v);return *this;}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}void reserve(size_t n){if (n capacity()){size_t old_size size();T* tmp new T[n];memcpy(tmp, _start, size() * sizeof(T));delete _start;_start tmp;_finish _start old_size;_end_of_storage _start n;}}void push_back(const T x){if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}T operator[](const T x){return _start[x];}iterator begin(){return _start;}iterator end(){return _finish;}void pop_back(){--_finish;}void resize(size_t n, T val T()){if (n size()){_finish _start n;}else{reserve(n);while (_finish _start n){*_finish val;_finish;}}}void erase(iterator pos){assert(pos _start);assert(pos _finish);iterator it pos 1;while (it ! end()){*(it - 1) *it;it;}--_finish;}void insert(iterator pos, const T x){assert(pos _start);assert(pos _finish);if (_finish _end_of_storage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos x;_finish;}private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};
}test.cpp :
#includevector.h
namespace Myvector
{void test(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.insert(v.begin() 2, 40);for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;for (auto ch : v){cout ch ;}cout endl;v.erase(v.begin() 2);v.resize(10, 1);for (auto ch : v){cout ch ;}cout endl;}void test02(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto ch : v){cout ch ;}cout endl;vectorint v1;v1 v;for (auto ch : v1){cout ch ;}cout endl;}
}int main()
{//Myvector::test();Myvector::test02();return 0;
}2.2 使用memcpy拷贝问题
假设模拟实现的vector中的reserve接口中使用memcpy进行的拷贝以下代码会发生什么问题
int main()
{
bite::vectorbite::string v;
v.push_back(1111);
v.push_back(2222);
v.push_back(3333);
return 0;
} 问题分析
1. memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中 2. 如果拷贝的是自定义类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。 结论如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃。 本章完。
