linux视频播放网站,公司购买网站怎么做分录,2017手机网站建设方案,公司网站如何租用服务器STL库#xff08;1#xff09; vectorvector介绍vector使用初始化元素访问内存扩容插入删除 listlist介绍初始化#xff0c;元素访问插入删除元素 vector和list区别 vector
vector介绍
vector是可以改变大小的数组的容器。其内存结构和数组一样#xff0c;使用连续的存储… STL库1 vectorvector介绍vector使用初始化元素访问内存扩容插入删除 listlist介绍初始化元素访问插入删除元素 vector和list区别 vector
vector介绍
vector是可以改变大小的数组的容器。其内存结构和数组一样使用连续的存储空间也就可以使用指针指向其元素通过偏移量来访问存储空间中的元素。和数组不同之处在于vector的大小可以动态的变化容器可以自动扩容存储空间。vector使用一个动态分配的连续存储空间来存储元素在插入新元素的时候也可能需要重新分配存储空间也就意味着每次扩容都需要将其元素重新移动到新的存储空间中很显然这效率是非常低的为此不会每次像容器中添加元素都重新分配。容器可以分配一些额外的存储空间以适应添加的对象其每次扩容以原本的1.5或2倍来扩容。与其他的容器相比vector可以更加高效的访问其他元素并且可以高效的从尾部添加或者删除元素。对于节位意外的位置插入删除效率较低。
vector使用
初始化
int main() {vectorint iar;vectordouble dar(12,10,0);vectorint ibr{1,2,3,4,5,6};vectorInt Iar;//处理自定义类型vectorint*par;//尽量别这么使用因为其可能指向动态申请的内存其不会主动释放。
}元素访问
1.at访问(返回的是引用可以进行修改) 2.下标访问 3.data()返回首地址通过首地址偏移量进行解引用操作。 4.迭代器 5.范围for
int main() {vectorint iar{1,2,3,4,5};int niar.size();for(int i0;in;i) {ibr.at(i)10;coutiar.at(i) iar[i]endl;}coutiar.back()endl;coutiar.front()endlint* pibr.data();for(int i0;in;i) {coutp[i]endl;//*(pi);}for(auto x:iar) {coutx ;}vectorint::iterator itiar.begin();vectorint::const_iterator citiar.begin();vectorint::reverse_iterator ritiar.rbegin();//逆向迭代器for(;rit!rend();) {cout*ritendl;}vectorint::const_reverse_iterator itiar.rbegin();for(;it!iar.end();){(*it)-100;cout*itendl;}
}内存扩容
int main() {
vectorint var ;for (int i 0; i 100; i) {var.push_back(i);cout size: var.size() endl;;cout capacity: var.capacity() endl;}
}运行上面代码我们观察输出结果 其容量分别是1234691319…其扩容分别按照原本的1.5倍扩容如果其1.5倍和原本一样就对容量进行1操作。 这里我们用的是内置类型如果是我们自己定义的类呢就会发生这样的过程比如我们定义的是ptr类类中存在构造拷贝构造移动构造移动赋值析构等函数此处不做编写。 扩容等操作我们来具体理解以下
int main() {std::vectorPtr ar;for(int i0;i100;i) {ar.push_back(Ptr(i));cout size: ar.size() endl;;cout capacity: ar.capacity() endl;}
}首先观察第一张图容量为1大小为1在首先会调用缺省构造函数来构造ptr的无名对象其为右值然后使用移动构造来将无名对象的资源移动到新的对象中该对象就存在于容器中然后析构无名对象。紧接着当再次添加对象的时候需要进行扩容处理其扩容就是重新申请一块内存将原本内存中的资源拷贝一份放入新的内存中然后释放旧的资源。为此我们可以看到其调用拷贝构造函数创建新对象来放入新内存中然后析构掉原本的对象然后创建新添加的对象移动构造来移动无名对象的资源最后析构无名对象。这就是其扩容的内部操作。很明显效率很低在不断的构建对象和析构对象。
为此呢我们可以使用reserve()函数。
int main() {std::vectorPtr ar;ar.reserve(200);//ar.resize(200);//ar.assign(10,Ptr(10));for(int i0;i100;i) {ar.push_back(Ptr(i));cout size: ar.size() endl;;cout capacity: ar.capacity() endl;}
}该函数可以直接申请够200个对象的内存不会进行反复的扩容和拷贝构造和这个函数相仿的还存在一个resize()函数该函数与其不同之处在于这个函数在申请内存之后会创建100个对象为此加入对象的时候会从第100个后面进行添加。还存在一个assign()函数该函数页会创建对新象不过其需要指定创建的对象。
插入删除
int main() {std::vectorPtr ar;ar.reserve(10);ar.push_back(Ptr(1));ar.push_back(Ptr(2));ar.push_back(Ptr(3));ar.push_back(Ptr(4));ar.push_back(Ptr(5));vectorPtr::operator itar.begin();ar.insert(it,Ptr(6));for(auto x:ar){x.Print();}ar.pop_back();
}很明显vector的插入删除一般都是在尾部插入删除而通过迭代器和插入函数头部插入时必然将后面所有的元素都要向后移动效率大幅度降低当我们使用了迭代器之后然后尾删的时候很明显出现了程序崩掉的现象这是为什么呢因为我们对迭代器进行操作之后迭代器失效了。为什么会失效呢迭代器实际上是和对象绑定的 我们的迭代器是和对象绑定的例如迭代器此时指向首元素1然后进行了头删那么头结点内存释放了对象丢失了为此迭代器也就丢失了。而扩容依然是如此重新申请了内存拷贝了资源那么原本的对象就丢失了迭代器也就丢失了。
list
list介绍
list是序列容器允许在序列中任何位置执行O(1)时间的插入和删除并在两个方向上进行迭代。其底层结构是双链表将每个元素存储在不同的存储位置每个结点通过nextprev指针连结成的顺序表。list与其他容器相比可以在任何位置插入和删除获得迭代器的情况下时间复杂度为O(1).不能通过下标访问需要通过迭代器找到位置才可以访问需要遍历的时间开销。存储密度低使用一些额外的内存空间next,prev指针来保持每个元素的关联性从而导致存储小元素的列表存储密度低。
初始化元素访问
数组初始化范围for遍历
int main() {std::listint arlist{1,2,3,4,5,6,7,8};coutarlist.back()endlcoutarlist.front()endl;for(auto x:arlist) {coutx ; }
}插入
int main() {std::listPtr arlist;for(int i0;i5;i) {//arlist.push_back(Ptr(i));arlist.emplace_back(i);}for(const auto x:arlist) {x.Print(); }
}因为其list容器结构是双链表结构所以我们进行头插尾插的效率都是一样的不过push_back插入我们知道是先创建对象然后进行移动构造来插入数据效率较低为此在list中存在emplace_back函数他和push_back不同之处在于他是原位构造直接在申请的内存上构造对象不会进行移动构造然后析构对象。范围for遍历时也最好用常引用如果不是引用便会调用拷贝构造构造对象来调用Print函数输出使用引用就可以不在调用拷贝构造函数大大节省了时间和空间。而加入const可以保证容器中的元素不发生改变。 同vector一样也list容器中最好不要使用指针为什么呢
int main() {std::listPtr* arlist;for(int i0;i5;i) {//arlist.push_back(Ptr(i));arlist.emplace_back(new Ptr(i));}for(const auto x:arlist) {x-Print(); }
}我们使用上面代码的时候很明显其没有析构对象因为容器中是指针其不能判断内部是不是动态申请了内存而释放他所以呢就不会进行析构为此最好不要使用指针要析构就要在范围for中使用delete析构。或者使用智能指针。
删除元素
erase()删除指定位置的元素也可以删除某个区间的多个元素。clear()删除所有元素。remove(val):删除所有等于val的元素。unique():删除容器中相邻的重复元素。
int main() {listint ilist{1,2,3,4,5,1,2,3,4,5};ilist.sort();ilist.unique();for(auto x :ilist) {coutx ;}
}unique()删除通过上面代码就可以展示出来。 list中的sort排序底层是快排而当数据量足够大的时候呢就会存在一个阈值高于这个值就会使用归并排序。
vector和list区别
vectorlist底层实现连续存储的容器动态数组对上分配空间动态双向链表堆上分配空间空间利用率连续空间不易造成内存碎片化空间利用率高节点不连续容易造成内存碎片化小元素使结点密度低空间利用率低查找元素下标atfindbinary_search()find O(n)插入push_back(val);O(1)//空间足够O1迭代器随机迭代器检查越界支持–…双向迭代器检查越界支持–迭代器失效插入删除都会导致迭代失效插入元素不会导致迭代器失效删除会导致迭代器失效不影响其他迭代器
两者适用情况
需要高效得随机存储不在乎插入删除效率很少使用插入删除选用vector需要大量得插入删除苏哦系取值很少使用选用list。
