西安学建网站,手机网站模板演示,南宁网站建设 醉懂网络,哈尔滨公司网站目录
一#xff1a;vector的构造函数
二#xff1a;vector的迭代器
三vector的空间增长问题
四#xff1a;vector 增删查改接口
五#xff1a;vector的模拟实现
#xff08;一#xff09;一些简单接口的实现#xff1a;
#xff08;二#xff09;一些复杂接口的…目录
一vector的构造函数
二vector的迭代器
三vector的空间增长问题
四vector 增删查改接口
五vector的模拟实现
一一些简单接口的实现
二一些复杂接口的实现
迭代器失效问题
三五个构造函数的模拟实现
1默认构造
2拷贝构造函数
3使用n个val去初始化容器的构造
4迭代器区间初始化构造
5赋值构造 vector其实就是我们数据结构中的顺序表。
一vector的构造函数
1无参构造即默认构造。vector构造一个没有元素的空容器。 // 走默认构造vectorchar vc;
2填充构造函数构造一个包含 n 个元素的容器。每个元素都是 val 的副本。 // 默认初始化为0vectorint v1(10);// 初始化为1vectorint v2(10, 1);3拷贝构造函数构造一个容器其中包含与范围 [firstlast] 一样多的元素每个元素都按相同的顺序从该区域中的相应元素构造。 // 拷贝构造vectorint v3(v2);
4使用迭代器进行初始化的构造构造一个容器其中包含与范围 [firstlast] 一样多的元素每个元素都按相同的顺序从该区域中的相应元素构造。 vectorint v1(10);// 使用迭代器进行初始化vectorint v3(v1.begin(), v1.end()-3);
二vector的迭代器
同其他的string容器一样begin和end分别是容器的第一个位置和最后一个位置反向迭代器则相反。const迭代器和非const迭代器和string的也是一样的C_STL_string使用和模拟实现-CSDN博客
这里可以看一下。
// 初始化为一个定值
vectorint v2(10, 1);
// 迭代器使用
//vectorint::iterator it;
//vectorint::const_iterator it;
// 反向迭代器
vectorint::reverse_iterator it;
//it v2.begin();
it v2.rbegin();
//while (it ! v2.end())
while (it ! v2.rend())
{//cout (*it) ;cout *it ;it;
}
三vector的空间增长问题
1size()返回元素的实际个数
2capacity()容器容量的大小
3resize() 修改实际容器元素个数
4reserve()改变capacity的大小
5empty()判断容器是否为空
注意在g和vs中capacity在扩容的时候可能不一样有的是1.5倍扩容有的是2倍扩容
具体我们来看下这几个接口的情况
// 测试vector 空间增长问题接口
void test02()
{vectorint v2(10, 1);cout v2.size() endl;cout v2.capacity() endl;cout v2.empty() endl;// resize如果n大于size的话会将size的元素进行初始化v2.resize(40);// 这里改变capacity的为13并不会缩容v2.reserve(13);cout v2.capacity() endl;for (auto x : v2){cout x ;}
} 四vector 增删查改接口
1push_back在容器末尾插入一个值
void push_back (const value_type val);
2pop_back删除容器末尾的一个值
void pop_back();
3find在范围内查找值
返回范围中比较等于 的第一个元素的迭代器。如果未找到此类元素则函数返回 。
template class InputIterator, class T InputIterator find (InputIterator first, InputIterator last, const T val);4insert通过在指定位置的元素之前插入新元素来扩展向量从而有效地增加容器大小增加插入的元素数。
single element (1)
iterator insert (iterator position, const value_type val);
fill (2) void insert (iterator position, size_type n, const value_type val);
range (3)
template class InputIterator void insert (iterator position, InputIterator first, InputIterator last);5erase从向量中删除单个元素 位置 或一系列元素 [firstlast
iterator erase (iterator position);iterator erase (iterator first, iterator last);
6swap交换向量的数据空间
void swap (vector x);
7operator[]返回对向量容器中位置 n 处的元素的引用。
reference operator[] (size_type n);const_reference operator[] (size_type n) const;
1~7接口代码
void test03()
{//find
//push_back
///vectorint v2;for (int i 0; i 100; i){v2.push_back(i);}v2.pop_back();//for (auto e : v2)//{// cout e ;//}cout endl;// 在一个范围内查找数据val,并且返回第一个等于val的迭代器,如果没有找到就返回区间的末尾迭代器vectorint::iterator it find(v2.begin(),v2.end(), 31);//while (it ! v2.end())//{// //cout (*it) ;// cout *it ;// it;//}
/
//insert
//在pos迭代器位置插入val不是下标v2.insert(v2.begin() 10, 10025);it v2.begin();//while (it ! v2.end())//{// //cout (*it) ;// cout *it ;// it;//}//erase
//删除迭代区间的数据或者迭代pos位置的数据// iterator erase (iterator first, iterator last);v2.erase(v2.begin() 3, v2.end() - 10);it v2.begin();while (it ! v2.end()){//cout (*it) ;cout *it ;it;}// iterator erase (iterator position);v2.erase(v2.begin() 20);it v2.begin();while (it ! v2.end()){//cout (*it) ;cout *it ;it;}
}// 测试swap
void test04()
{// template class T, class Alloc// void swap(vectorT, Allocx, vectorT, Allocy);vectorint v2(10, 1);vectorint v3(10, 3);// 交换两个向量的空间v2.swap(v3);vectorint::iterator it;it v2.begin();//while (it ! v2.end())//{// //cout (*it) ;// cout *it ;// it;//}
//
//reference operator[] (size_type n);const_reference operator[] (size_type n) const;for (int i 0; i v2.size(); i){cout v2[i] ;}}
五vector的模拟实现
在实现vector的时候我们采用模板来实现方便vector存取任意的类型可以是自定义类型也可以是内置类型例如vectorvectorint(二维数组)。
因为vector的数据结构本质是顺序表所以我们可以设置一个顺序表来模拟实现它。
然后设置三个标志位
private:iterator _start nullptr;iterator _finsh nullptr;iterator _end_of_storage nullptr;
_start表示容器的起始位置_finsh表示有效数据个数的最后一个位置_end_of_storage表示容器容量的大小。
iterator使我们使用typedef将模板类型重命名的。
namespace cp
{templateclass Tclass vector {public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start nullptr;iterator _finsh nullptr;iterator _end_of_storage nullptr;};
}
我们将我们的vector使用一个单独的命名空间CP包起来避免跟库里面的vector冲突。
关于模板请看C模板初阶-CSDN博客
一一些简单接口的实现
一些比较简单的接口我们就将他们放到类里面
关于容量相关的接口
//清除数据
void clear()
{_finsh _start;
}
//判断容器是否为空
bool empty()const
{return _finsh _start;
}
//获取容器容量的大小
size_t size() const
{//指针相减得到元素个数return _finsh - _start;
}
//获取容器容量的大小
size_t capacity() const
{return _end_of_storage - _start;
}
迭代器的实现const迭代器和非const迭代器反向迭代器就不实现了
几种迭代器
iterator begin()
{return _start;
}
iterator end()
{return _finsh;
}
const_iterator cbegin() const
{return _start;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finsh;
}
const_iterator cend() const
{return _finsh;
}函数后边加const表示成员变量不可以修改。
方括号下标[ ]的重载实现
//返回普通引用可以修改
T operator[](size_t pos)
{return _start[pos];
}
//返回const引用不可以修改
const T operator[](size_t pos)const
{return _start[pos];
}
尾删除函数
void pop_back()
{assert(!empty());--_finsh;
}
二一些复杂接口的实现
这些复杂的接口我们将他们放到类外面。
1reserve开辟空间并检查。
templateclass T
void vectorT::reserve(size_t n)
{if (n capacity()){size_t old_size size();T* tmp new T[n];for (int i 0; i old_size; i){tmp[i] _start[i];}if (_start){delete[] _start;}_start tmp;_finsh _start old_size;_end_of_storage _start n;}
}
注意在更新成员变量的时候要先预存一份没交换之前的size因为在_start和tmp交换的时候也会影响到size的改变。另外记得释放旧空间当然如果原来的容器是空的就不用释放了。
2push_back在容器的末尾位置尾插一个数据
templateclass T
void vectorT::push_back(const T x)
{if (_finsh _end_of_storage){reserve(capacity() 0 ? 4 : 2 * capacity());}*_finsh x;_finsh;
}
只要是往容器里面插入数据都要检查容器是否满了如果满了就需要先扩容再插入数据这和数据结构的顺序表是一样的。
迭代器失效问题
通常我们在插入和删除的时候使用的是迭代器所以在一些情况下会导致迭代器失效string的迭代器版本也会有这样的情况。
1insert在pos迭代器位置插入数据并且返回当前插入数据位置的迭代器。 templateclass Ttypename vectorT::iterator vectorT::insert(iterator pos, T val){assert(pos _start);assert(pos _finsh);if (_finsh _end_of_storage){//防止pos位置因为扩容而失效size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finsh;while (end pos){*end *(end - 1);end--;}*pos val;_finsh;pos;return pos;}
知识点补充在这里我们使用typename的原因,因为在实例化的时候编译器不知道迭代器iterator到底是类型还是成员变量所以我们使用typename。规定使用typename指定的是类型。
在实现insert的时候我们要先扩容但是扩容的时候原来_start指向的空间和tmp交换了 但是我们的pos位置迭代器还是原来空间的pos原来空间交换给tmp之后随着函数结束tmp变量指向的空间销毁pos所指向的也就是一个随机空间。当我们在挪动数据的时候因为pos不是当前对象指向的空间位置所以会发生一些错误插入数据也就会导致一些问题。
解决方案
如上述代码我们先记录pos的相对位置在更新_start指向的空间的之后我们也更新pos的迭代器这样就不会发生问题了。
这是第一种迭代器失效的情况迭代器指向的空间被释放类似于野指针。
2erase挪动覆盖删除迭代器位置的数据返回pos位置的迭代器。
我们先实现一下这个成员函数同样我们将他们放到类外面。
templateclass T
typename vectorT::iterator vectorT::erase(iterator pos)
{assert(pos _start);assert(pos _finsh);iterator start pos;while (start _finsh){*start *(start 1);start;}_finsh--;return pos;
}
当我们删除数据之后pos还是指向原来的位置但是如果我们以下标的形式看待它。
例如我们来测试一下我们写一个vector往里面放一些数据删除之后使用它的迭代器来操作。
因为方便测试我们实现一个打印容器的函数模板 templateclass Containervoid print_container(const Container con){/*auto it con.cbegin();while (it ! con.cend()){cout *it ;it;}cout endl;*/for (auto e : con){cout e ;}cout endl;}
//测试迭代器失效问题
void test_vaid_iterator()
{cp::vectorint v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除5位置的内容cp::vectorint::iterator it v.erase(v.begin()3);cp::print_container(v);*it * 10;cp::print_container(v);
} 可以看到原来位置的意义已经改变了我们原本的位置在删除数据之后已经改变了。
3库里面的迭代器失效问题Windows平台下。
我们来测试一下库里面的insert和erase。 测试函数
1测试insert:
//测试迭代器失效问题
void test_vaid_iterator()
{std::vectorint v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除5位置的内容std::vectorint::iterator pos v.begin() 3;v.insert(pos, 3);//删除pos位置的内容cp::print_container(v);//访问pos位置*pos*10;cp::print_container(v);
} (2)的是erase:
//测试迭代器失效问题
void test_vaid_iterator()
{std::vectorint v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除5位置的内容std::vectorint::iterator pos v.begin() 3;cp::print_container(v);v.erase(pos);//删除pos位置的内容*pos * 10;cp::print_container(v);
} 在vs2020中编译器会强制检查报错。在insert和erase之后是不允许访问pos位置的迭代器的。
总结不管是自己实现的还是标准库内部实现的在容器中string,vector..为了安全考虑在insert和erase之后就不要访问pos位置的迭代器了。如果要访问就要更新迭代器。
三五个构造函数的模拟实现
接下来我们来实现他们的成员函数。
1默认构造
因为构造函数默认走初始化列表所以我们在实现默认构造函数的时候可以这样写。
vector() default;
因为我们在成员变量哪里给了缺省值所以使用default关键字可以强制编译器生成默认构造。
当然如果们没在成员变量给缺省参数的话可以自己走初始化列表 vector():_start(nullptr),_finsh(nullptr),_end_of_storage(nullptr){// 啥也不干因为会自动走舒适化列表用缺省值完成初始化}
我们来测试一下 可以看到v对象的三个成员已经被初始化完成了都是空指针。
2拷贝构造函数
用一个已经存在的对象去初始化另一个刚创建的对象
templateclass T
vectorT::vector(const vectorT v)
{//防止自己给自己赋值if (this ! v){reserve(v.capacity());for (auto e : v){push_back(e);}//_finsh和_endd_of_storage是指针不是整型不能直接赋值而且在reserve和push_back的时候已经更新过了不用更新//_finsh v._finsh;//_end_of_storage v._end_of_storage;}
}
3使用n个val去初始化容器的构造 templateclass TvectorT::vector(size_t n, vectorT val){reserve(n);for (size_t i 0; i n; i){push_back(val);}}
4迭代器区间初始化构造
templateclass input_iterator
vector(input_iterator first, input_iterator last)
{while (first ! last){push_back(*first);first;}
}
测试
void Test03()
{cp::vectorint v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cp::print_container(v);cp::vectorint v4(v.begin()2, v.begin() 5);cp::print_container(v4);} 5赋值构造
因为都是自定义类型且需要开辟空间所以和拷贝构造一样都是深拷贝。 //this vvectorT operator(const vectorT v){if (this ! v){clear();reserve(v.size());/*size_t size v.size();T* tmp new T[v.capacity()];for (size_t i 0; i size; i){tmp[i] v._start[i];}if (_start)delete[] _start;_start tmp;_finsh _start size;_end_of_storage _start v.capacity();*/for (auto e : v){push_back(e);}}return *this;}
赋值构造的现代写法
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finsh, v._finsh);std::swap(_end_of_storage, v._end_of_storage);
}
//现代写法
vectorT operator(vectorT v)
{swap(v);return *this;
}
6析构函数
~vector()
{if (_start)//如果_start是空为假则说明已经析构了不需要析构{delete[] _start;_start _finsh _end_of_storage nullptr;}
}
