网站开发学习路线,株洲公司做网站,wordpress 4.8 中文包,网站开发什么是会话#x1f3e0;专栏介绍#xff1a;浅尝C专栏是用于记录C语法基础、STL及内存剖析等。 #x1f3af;每日格言#xff1a;每日努力一点点#xff0c;技术变化看得见。 文章目录 vector介绍vector常用接口及使用示例构造类函数迭代器的使用容量操作增删改查 迭代器失效详解与v… 专栏介绍浅尝C专栏是用于记录C语法基础、STL及内存剖析等。 每日格言每日努力一点点技术变化看得见。 文章目录 vector介绍vector常用接口及使用示例构造类函数迭代器的使用容量操作增删改查 迭代器失效详解与vector底层结构探索vector模拟实现构造类函数属性获取类函数扩容与容量重置函数插入与删除函数vector模拟实现代码汇总含正向迭代器vector实现二维数组 vector介绍
vector就是一个可以自动扩大容量的数组它与顺序表具有相同的性质如适合随机访问、尾部插入删除效率高。关于顺序表的特点可以查阅该篇文章→数据结构线性表含顺序表及链表介绍
下面给出6条关于vector的概括性介绍
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因而存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。与其它动态序列容器相比deque, list 及forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。
vector常用接口及使用示例
构造类函数
构造函数声明接口说明vector()无参构造vector(size_type n, const value_type val value_type())构造并初始化为n个valvector(const vector x)拷贝构造vector(InputIterator first, InputIterator last)使用迭代器进行初始化构造
下面给出vector各种构造类函数的使用示例↓↓↓
#include iostream
#include vector
using namespace std;void testVector()
{//无参构造vectorint vc1;//5个c构造vectorvectorchar vc2(5, c);for(auto ch : vc2){cout ch ; }cout endl;//使用vc2构造vc3vectorchar vc3(vc2);for(auto ch : vc3){cout ch ; }cout endl;//使用容器的起始与终止迭代器构造vectorstring s Jammingpro;vectorcharvc4(s.begin(), s.end());for(auto ch : vc4){cout ch ; }cout endl;
}int main()
{testVector();return 0;
}迭代器的使用
迭代器接口说明begin endbegin获取第一个数据的位置end获取最后一个数据的下一个位置rbegin rendrbegin获取最后一个数据的位置rend获取第一个数据的前一个位置 如上图所示begin指向第一个元素的位置end指向向最后一个元素的下一个位置。下面给出begin和end这俩迭代器的使用示例
#include iostream
#include vector
using namespace std;void testVector()
{vectorint vc {1,2,3,4,5,6,7,8};vectorint::iterator it vc.begin();while(it ! vc.end()){cout *it ;it;}cout endl;
}int main()
{testVector();return 0;
}这里可以先将迭代器先理解为数组指针it指向数组的首地址it就可以将指针指向下一个元素的首地址。下文将对vector的迭代器进行模拟实现。 对于反向迭代器来说rbegin指向最后一个元素rend指向首元素的前一个位置。其他操作与正向迭代器begin与end没有区别。对反向迭代器进行操作等同于对指针-1操作。也就说反向迭代器初始化为rbegin后每执行一次操作迭代器就会向前移动一个位置而不是向后移动。
#include iostream
#include vector
using namespace std;void testVector()
{vectorint vc {1,2,3,4,5,6,7,8};vectorint::reverse_iterator it vc.rbegin();while(it ! vc.rend()){cout *it ;it;}cout endl;
}int main()
{testVector();return 0;
}普通迭代器的类型为iterator、反向迭代器的类型为reverse_iterator除了这两种迭代器还有const_iterator和const_reverse_iterator这两个迭代器用于对const类型的容器进行正反向遍历它们不能对容器内的数据进行修改而非const迭代器可以修改容器内的数据。↓↓↓
#include iostream
#include vector
using namespace std;void testConstVector(const vectorint vc)
{vectorint vc {1,2,3,4,5,6};vectorint::const_iterator it vc.begin();while(it ! vc.end()){*it 1;//error!!it;}
}void testVector()
{vectorint vc {1,2,3,4,5,6};vectorint::iterator it vc.begin();while(it ! vc.end()){*it 1;//ok!!it;}for(auto e : vc){cout *it ;}cout endl;
}int main()
{testVector();return 0;
}容量操作
接口声明接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize改变vector的sizereserve改变vector的capacity
vector的capacity容量一般都会size有效数据个数要大。因为vector的底层是包含连续空间的顺序表扩容时可能需要大量移动数据扩容效率较低。因而vector会在扩容时按照1.5倍或2倍扩容。
下面代码用于验证vs下与g下vector的扩容规律↓↓↓
#include iostream
#include vector
using namespace std;void testVector()
{vectorint vc;int sz vc.capacity();//获取初始容量for(int i 0; i 100; i){vc.push_back(i);if(sz ! vc.capacity()){sz vc.capacity();cout vector capacity change to : sz endl;}}
}int main()
{testVector();return 0;
}vs下执行结果如下图所示说明vs按照1.5倍左右进行扩容。 而g下执行结果入下图所示说明g按照2倍左右进行扩容。 empty用于判断vector容器中的有效数据数量是否为0reserve用于提前给vector开辟空间如果我们预先知道将要插入1000个数据则我们可以预先开辟1000个空间这样可以避免频繁扩容导致的效率损失。resize当resize指定大小n小于有效数据个数时则会将位于下标n及n后面的有效数据删除当resize指定大小n大于有效数据个数时则会在size到n-1的位置填充resize传入参数中指定的数据。
下面给出这3个函数的使用示例↓↓↓
#include iostream
#include vector
using namespace std;void testVector()
{vectorint vc;if(vc.empty()){cout vc is empty endl;}cout vcs capacity is vc.capacity() endl;vc.reserve(100);cout vcs capacity is vc.capacity() endl;for(int i 0; i 100; i){vc.push_back(i);}cout vcs size is vc.size() endl;
}int main()
{testVector();return 0;
}增删改查
接口声明接口说明push_back尾插pop_back尾删insert在pos前插入valerase删除pos位置的数据swap交换两个vector的数据空间operator[ ]想数组一样使用[ ]进行访问
下面给出上面各个接口的使用示例↓↓↓
#include iostream
#include vector
using namespace std;void testVector()
{vectorint vc;vc.push_back(1);vc.push_back(2);vc.push_back(3);vc.push_back(4);vc.push_back(5);cout after push back:;for(auto ch : vc){cout ch ;}cout endl;vc.pop_back();cout after pop back:;for(auto ch : vc){cout ch ;}cout endl;vc.insert(vc.begin(), 888);cout after insert:;for(auto ch : vc){cout ch ;}cout endl;vc.erase(vc.begin());cout after erase:;for(auto ch : vc){cout ch ;}cout endl;vectorint vc2 {666,777,888};cout before swap vc2 is: ;for(auto ch : vc2){cout ch ;}cout endl;vc2.swap(vc);cout after swap:;for(auto ch : vc){cout ch ;}cout endl;vc2[2] 999;cout after operator[]:;for(auto ch : vc2){cout ch ;}cout endl;
}int main()
{testVector();return 0;
}迭代器失效详解与vector底层结构探索 我们可以通过vs的监视窗口查看到vector底层总共3个指针_first指向堆区开辟空间的首地址_last指向最后一个有效元素的下一位置_end指向指向容量的下一位置。
而迭代器底层是什么呢由下图可以看到vector迭代器底层是一个指向堆区空间的指针。 如果我们在vector扩容器执行vectorint::iteartor it vc.begin()则可以获得vc的_first指针内容及it的指针指向0x00000000。如果此时插入数据后vc发生扩容将旧空间数据拷贝到新空间并将旧空间释放新的_first指针内容变为0x00FCA580而此时it中的指针仍然指向旧空间如果此时对it进行解引用操作就会发生非法访问的错误。下图演示了该文字表述的内容
vector模拟实现
我们参照SGI版本的STL命名方式它的_start指向指向开辟的空间首地址_final指向最后一个后效数据的下一位置_end_of_storage指向开辟空间最后一个位置的下一位置。 下面给出即将模拟实现的vector类的框架含默认构造及析构函数↓↓↓
templateclass T
class vector
{
public:vector(){}~vector(){if(_start){delete[] _start;_start _final _end_of_storage nullptr;}}
private:T* _start nullptr;T* _final nullptr;T* _end_of_storage nullptr;
};构造类函数
编译器自动生成的默认构造函数与拷贝赋值都是对_first、_final、_end_of_storage进行值拷贝。如下图所示。若使用vc来构造vc2则会使得vc和vc2的成员变量保存同一份地址当vc析构释放_first指向的空间后vc2再析构时也会重复释放该空间导致出错。 因此我们需要重写拷贝构造与拷贝赋值函数
vector(const vectorT vc)
{_final vc._size;_end_of_storage vc._end_of_storage;_start new T[_end_of_storage];memcpy(_start, vc._start, sizeof(T) * vc.size());
}vectorT operator(const vectorT vc)
{if (this ! vc){T* tmp new T[vc._end_of_storage];memcpy(tmp, vc._start, sizeof(T) * vc._size);if (_start) delete[] _start;_start tmp;_final _start vc.size();_end_of_storage _start vc.capacity();}
}属性获取类函数
下面实现的empty、size、capacity、operator[]函数↓↓↓
bool empty() const
{return _start _final;
}
size_t size() const
{return _final - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
T operator[](const size_t pos)
{assert(pos size());return _start[pos];
}扩容与容量重置函数
void reserve(const size_t n)
{if (n capacity()){size_t sz size();T* tmp new T[n];memcpy(tmp, _start, sizeof(T) * sz);if (_start) delete[] _start;_start tmp;_final _start sz;_end_of_storage _start n;}
}void resize(const size_t sz, const T val T())
{if (sz size()){_final _start sz;}else{if (sz capacity()){reserve(sz);}for (int i size(); i sz; i){_start[i] val;}_final _start sz;}
}插入与删除函数
void push_back(const T val)
{if (size() capacity()){int newsize capacity() 0 ? 10 : 2 * capacity();reserve(newsize);}_start[size()] val;_final;
}
void pop_back()
{assert(!empty());_final--;
}
void insert(T* pos, const T val)
{if (size() capacity()){int newsize capacity() 0 ? 10 : 2 * capacity();reserve(newsize);}T* it _final;while (it pos){*it *(it - 1);--it;}*pos val;_final;
}
void erase(T* pos)
{assert(!empty());T* it pos;while (it _final){*it *(it 1);it;}--_final;
}vector模拟实现代码汇总含正向迭代器
★psinsert可能会引起vector产生扩容导致迭代器失效SGI版本STL中将需要新的迭代器返回。下面代码中insert与erase与SGI版本返回值保持一致。
namespace jammingpro
{templateclass Tclass vector{typedef T* iterator;typedef const T* const_iterator;public:iterator begin(){return _start;}iterator end(){return _final;}const_iterator begin() const{return _start;}const_iterator end() const{return _final;}vector(){}vector(const vectorT vc){_final vc._size;_end_of_storage vc._end_of_storage;_start new T[_end_of_storage];memcpy(_start, vc._start, sizeof(T) * vc.size());}vectorT operator(const vectorT vc){if (this ! vc){T* tmp new T[vc._end_of_storage];memcpy(tmp, vc._start, sizeof(T) * vc._size);if (_start) delete[] _start;_start tmp;_final _start vc.size();_end_of_storage _start vc.capacity();}}~vector(){if (_start){delete[] _start;_start _final _end_of_storage nullptr;}}bool empty() const{return _start _final;}size_t size() const{return _final - _start;}size_t capacity() const{return _end_of_storage - _start;}T operator[](const size_t pos){assert(pos size());return _start[pos];}void reserve(const size_t n){if (n capacity()){size_t sz size();T* tmp new T[n];memcpy(tmp, _start, sizeof(T) * sz);if (_start) delete[] _start;_start tmp;_final _start sz;_end_of_storage _start n;}}void resize(const size_t sz, const T val T()){if (sz size()){_final _start sz;}else{if (sz capacity()){reserve(sz);}for (int i size(); i sz; i){_start[i] val;}_final _start sz;}}void push_back(const T val){if (size() capacity()){int newsize capacity() 0 ? 10 : 2 * capacity();reserve(newsize);}_start[size()] val;_final;}void pop_back(){assert(!empty());_final--;}iterator insert(T* pos, const T val){int sz pos - _start;if (size() capacity()){int newsize capacity() 0 ? 10 : 2 * capacity();reserve(newsize);}T* it _final;while (it pos){*it *(it - 1);--it;}*(_start sz) val;_final;return _start sz;}iterator erase(T* pos){assert(!empty());T* it pos;while (it _final){*it *(it 1);it;}--_final;return pos;}private:T* _start nullptr;T* _final nullptr;T* _end_of_storage nullptr;};
}vector实现二维数组
如果想使用vector二维数组可以定义如下代码
void test()
{vectorvectorintvc(5, vectorint(6, 0));
}上面的代码相当于创建了一个包含5个vector的vector容器 欢迎进入浅尝C专栏查看更多文章。 如果上述内容有任何问题欢迎在下方留言区指正b(▽)d
