台州免费做网站,南宁网站建设产品,网站设计和营销,艾米艾园wordpress目录
【本节目标】
1.vector的介绍及使用
1.1 vector的介绍
1.2 vector的使用及底层模拟实现
vector类中成员变量
1.2.1 vector的定义
1.2.2 vector iterator 的使用
1.2.3 vector 空间增长问题
1.2.3 vector 增删查改
1.2.4 vector 迭代器失效问题
1.2.5 使用memcp…目录
【本节目标】
1.vector的介绍及使用
1.1 vector的介绍
1.2 vector的使用及底层模拟实现
vector类中成员变量
1.2.1 vector的定义
1.2.2 vector iterator 的使用
1.2.3 vector 空间增长问题
1.2.3 vector 增删查改
1.2.4 vector 迭代器失效问题
1.2.5 使用memcpy拷贝问题 【本节目标】 1.vector的介绍及使用 2.vector深度剖析及模拟实现 1.vector的介绍及使用
1.1 vector的介绍 vector是一个可变大小数组的序列容器就如同数组一样vector也采用的是连续存储空间来存储元素又不同于数组他的大小会被容器自动处理大小会自动改变本质上vector使用动态分配数组来存储元素新元素插入时vector会重新分配一个内存更大的新数组而将之前内存的元素都转移到这个数组中释放之前的数组空间vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大vector占用更多的存储空间为了获得管理存储空间的能力以一种有效方式动态增长vector在访问元素时会更加高效尾删和尾插元素相对高效 1.2 vector的使用及底层模拟实现 vector类中成员变量
templateclass T
class vector
{public:......private:T* _start; //指向数组内存的开始T* _finish; //指向数组内存结束的下一个T* _endofstorage; //数组内存当前的最大容量
}
1.2.1 vector的定义
(constructor)构造函数声明接口说明vector()重点无参构造vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造 无参构造 vector() vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{} 构造并且初始化n个val vectorsize_type n, const value_type val value_type() //初始化一定数量的相同数据
vector(size_t n, const T valT())
{//扩容reserve(n);for (size_t i 0; i n; i){push_back(val);}
}//重载函数解决 vectorint v1(10, 1);的调用错误
vector(int n, const T val T())
{//扩容reserve(n);for (size_t i 0; i n; i){push_back(val);}
} 由于用上面第一个函数时用如下的代码可能会导致寻址错误会与使用迭代器进行初始化构造相冲突导致调用构造的时候会调用与使用迭代器进行初始化构造 vectorint v1(10, 1); 由于类型转换则会两次类型转换与使用迭代器进行初始化构造会只用依次匹配成功则会选用与使用迭代器进行初始化构造 而下面代码则无影响 vectorint v2(10, 1);
print_vector(v2);vectorchar v3(10, a);
print_vector(v3); 因而要解决寻址错误则会直接重载一个会冲突的那个类型的函数 拷贝构造 vector (const vector x) //拷贝构造
//v1(v3)
vector(const vectorT v)
{//扩容reserve(v.capacity());//对于不确定的类型T加上for (auto e : v){push_back(e);}
} 对于不确定的类型迭代器要加上将遍历v中数据插入到this中 使用迭代器进行初始化构造 vector (InputIterator first, InputIterator last) //如果写iterator的话会只允许vector的迭代器初始化
//类模板的成员函数是函数模板
//部分初始化
templateclass Inputiterator
vector(Inputiterator first, Inputiterator end)
{while (first ! end){push_back(*first);first;}
} 类模板的成员函数时函数模板 C11中初始化数组 //C11大括号初始化数组vectorint v1 { 1,2,3,4,5,6,7,8,9,10 };
vector(initializer_listT il)
{//扩容reserve(il.size());//运用initializer_list 中的迭代器for (auto e : il){push_back(e);}
} ininializer_listT类中可以实现大括号初始化数组数组中的元素可以任意添加 // 隐式类型转换优化
//vectorint v1 { 1,2,3,4,5,6,7,8,9,10 };
vectorint v1{ 1,2,3,4,5,6,7,8,9,10 }; 在C11中也有这样的初始化方式 int i 1;
// C11都可以实现
int j { 1 };
int k{ 1 }; 认识既可 1.2.2 vector iterator 的使用
iterator的使用接口说明begin end重点获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下一个位置 的iterator/const_iteratorrbegin rend获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的 reverse_iterator iterator迭代器实现beginend typedef T* iterator;
typedef const T* const_iterator;//普通迭代器
iterator begin()
{return _start;
}iterator end()
{return _finish;
}//const迭代器
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
} 迭代器的作用类似于指针我这里以指针为例 1.2.3 vector 空间增长问题
容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize重点改变vector的sizereserve 重点改变vector的capacity 1.capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。 2.reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。 3.resize在开空间的同时还会进行初始化影响size 获取数据个数 size() //大小
size_t size() const
{return _finish - _start;
} 获取容量大小 capacity() size_t capacity() const
{return _endofstorage - _start;
} const函数指明this指向的对象数据不会被修改并且const对象和普通对象都可以使用 判断是否为空 empty() //判断是否为空
bool empty()
{return _start _finish;
} 改变vector的size resize() //这里的T()指的是对象的默认构造T是谁就是神的默认构造的值int()0
void resize(size_t n,const T valT())
{if (n capacity()){//扩容reserve(n);//插入while (_finish _start n){*_finish val;_finish;}}else{//删除_finish _start n;}} 用if判断容量是否大于自身从而判断是否需要扩容 resize函数的第二个参数的缺省值是用来初始化的这个值由于不知道T的类型用一个匿名对象T()来构造成功 改变vector的capacity reserve() //扩容
void reserve(size_t n)
{if (n capacity()){T *tmp new T[n]; //开辟n个空间size_t old_size size();//防止开辟内存时_start更新以后_finish与之不在同一段空间提前拷贝//如果是string类型的vector扩容时会导致string浅拷贝,两个内容会指向同一份空间//memcpy(tmp, _start, sizeof(T)*size());//将_start原有的数据内存空间拷贝到tmp中for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;_start tmp;_finish _start old_size;_endofstorage _start n;}
} 如果是一个类类型的vector如string时开辟空间时可能会产生浅拷贝memcpy导致的memcpy是将内存的数据拷贝一份到另一段内存但即两个内存的对象都指向同一个字符空间 1.2.3 vector 增删查改
vector增删查改接口说明push_back重点尾插pop_back 重点尾删find查找。注意这个是算法模块实现不是vector的成员接口insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间operator[] 重点像数组一样访问 尾插 push_back(const T val) //尾插
void push_back(const T val)
{//扩容if (_finish _endofstorage){//扩容2倍reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish val;_finish;
} 尾删 pop_back() //尾删
void pop_back()
{//判断是否为空assert(!empty());--_finish;
} 要注意判断是否为空空时删除无效 在position之前插入val insert(iterator pos,const T val) //插入
//指针pos
void insert(iterator pos,const T val)
{assert(pos _start);assert(pos _finish);//判断扩容if (_finish _endofstorage){//扩容会导致_start会指向另一段新空间而pos没有改变到新空间还是在就空间里//计算pos的位置size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);//更新pospos _start len;}//插入//由于这里是指针就不用在意和string产生的无符号整数会无限循环iterator it _finish - 1;while (it pos){*(it 1) *it;it--;}*pos val;_finish;
} 这里的iterator指的是前面T*,typedef T* iterator 使用时 v2.insert(v2.begin(), 11.11);
print_vector(v2); 删除position位置的数据 erase(iterator pos) //删除
void erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator it pos 1;while (it _finish){*it *it 1;it;}_finish--;
} 注意要判断pos指向的位置是否在_start和_finish之间删除时是将pos之后的位置的数据向前移动覆盖之前的数据 交换两个vector的数据空间 swap(const vectorT v) //交换
void swap(const vectorT v)
{std::swap(this-_start, v._start);std::swap(this-_finish, v._finish);std::swap(this-_endofstorage, v._endofstorage);
} 赋值重载 vectorT operator(vectorT v) //赋值重载
//v1v3
//v3的拷贝赋值给v1保证不改变v3的值
vectorT operator(vectorT v)
{//内存不够扩容reserve(v.capacity());swap(v);
} 赋值重载时要v3的值给v1由于v3的改变不能导致v1的改变所以参数是值传递的拷贝 像数组一样访问 T operator[](size_t pos) //运算符重载
T operator[](size_t pos)
{assert(pos 0);return _start[pos];
}const T operator[](size_t pos) const
{assert(pos 0);return _start[pos];
} 将const类型对象和普通对象分开来定义使用 1.2.4 vector 迭代器失效问题 迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如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;
} insert导致的迭代器失效 由于insert扩容时迭代器it还在指向着原本的空间所以迭代器失效而需要更新迭代器 2. 指定位置元素的删除操作--erase 1这是正常的 2结果出错 由于erase是不断的向前覆盖由于每次it则会跳过数据删除导致迭代器错误 3.程序崩溃 这个是由于数据覆盖导致了访问越界了 更新迭代器 vectorint v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(4);
v1.push_back(5);
//v1.push_back(4);// 删除偶数 -- 迭代器失效以后不要直接使用如果要使用按规则重新更新后使用
//std::vectorint::iterator it v1.begin();
vectorint::iterator it v1.begin();// 21:15
//cout typeid(it).name() endl;
while (it ! v1.end())
{if (*it % 2 0){it v1.erase(it);}else{it;}
} 3. 注意Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端 // 1. 扩容之后迭代器已经失效了程序虽然可以运行但是运行结果已经不对了
int main()
{
vectorint 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 vector
#include algorithm
int main()
{
vectorint v{1,2,3,4,5};
vectorint::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;
}
程序可以正常运行并打印
4 4
5 // 3: erase删除的迭代器如果是最后一个元素删除之后it已经超过end
// 此时迭代器是无效的it导致程序崩溃
int main()
{
vectorint v{1,2,3,4,5};
// vectorint 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;
}// 使用第一组数据时程序可以运行
[slyVM-0-3-centos 20220114]$ g testVector.cpp -stdc11
[slyVM-0-3-centos 20220114]$ ./a.out
1 3 5// 使用第二组数据时程序最终会崩溃
[slyVM-0-3-centos 20220114]$ vim testVector.cpp
[slyVM-0-3-centos 20220114]$ g testVector.cpp -stdc11
[slyVM-0-3-centos 20220114]$ ./a.out
Segmentation fault 从上述三个例子中可以看到SGI STL中迭代器失效后代码并不一定会崩溃但是运行结果肯定不对如果it不在begin和end范围内肯定会崩溃的 4. 与vector类似string在插入扩容操作erase之后迭代器也会失效 #include string
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.5 使用memcpy拷贝问题 reserve中memcpy拷贝问题 //扩容
void reserve(size_t n)
{if (n capacity()){T *tmp new T[n]; //开辟n个空间size_t old_size size();//防止开辟内存时_start更新以后_finish与之不在同一段空间提前拷贝//如果是string类型的vector扩容时会导致string浅拷贝,两个内容会指向同一份空间memcpy(tmp, _start, sizeof(T)*size());//将_start原有的数据内存空间拷贝到tmp中_start tmp;_finish _start old_size;_endofstorage _start n;}
}
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是浅拷贝否则可能会引起内存泄漏甚至程序崩溃
