STL 第九日 : 容器篇总结

xiaoxiao2021-02-28  18

私房STL之vector

一句话vector:vector的空间可扩充,支持随机存取访问,是一段连续线性的空间。所以它是动态空间,与之对比的array是静态的空间,不可扩充。简单来说,vector是数组的增强版。

vector创建与遍历

vector提供了几个版本的构造函数。详见:http://www.cplusplus.com/reference/stl/vector

比如:

vector<int> iv(3,3); /*3,3,3*/

又或:

...... vector<int>::iterator beg = iv.begin(), end = iv.end(); cout << *beg << endl; ......

vector删除

在经常需要删除操作earse()(插入操作也一样insert())的地方,不建议使用vector容器,因为删除元素会导致内存的,无疑增加系统开销。最为极端的情况,删除vector首部的元素:

a b c d e f g hb c d e f g h hb c d e f g h

当然,有更好的做法,为了避免内存,在删除的时候,将需要删除的目标与vector尾端的元素交换,然后才执行删除操作,但这无疑也增加了一个指向vector尾端元素的空间开销。

a b c d e f g hh b c d e f g ah b c d e f g

vector陷阱

需要注意的是,vector备用空间是有限的,当发现备用空间不够用的时候,vector是另外新分配一个比原有更大的空间(原有空间*2),然后把原有的内容倒腾到新的空间上去,接着释放原有的空间。所以迭代器的使用就要特别小心了,在插入元素之后,很可能之前声明定义的迭代器都失效了。

...... vector<int> iv(3,3); iv.push_back(10); /*3,3,3,10*/ vector<int>::iterator beg = iv.begin(), end = --iv.end(); cout << iv.size() << " " << *beg << " " << *end << endl; /*4 3 10*/ iv.push_back(20); cout << iv.size() << " " << *beg << " " << *end << endl; /*bomb.invalid iterator.*/ ...... bomb!!!

vector元素排序

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> iv(3,3); unsigned int i; /*add new elem.*/ iv.push_back(10); iv.push_back(9); iv.push_back(0); vector<int>::iterator beg = iv.begin(), end = iv.end(); /*print.*/ for(i=0; i<iv.size(); i++) cout << iv[i] << " "; cout << endl; /*sort.*/ sort(beg,end); /*print.*/ for(i=0; i<iv.size(); i++) cout << iv[i] << " "; cout << endl; return 0; }

3 3 3 10 9 00 3 3 3 9 10请按任意键继续. . .

vector查找

按上述遍历元素的方法查找,复杂度为O(n)。STL算法实现了find(),可以在指定的迭代器始末寻找指定的元素。

...... vector<int> iv(3,3); unsigned int i; /*add new elem.*/ iv.push_back(10); iv.push_back(9); iv.push_back(0); vector<int>::iterator beg = iv.begin(), end = iv.end(), ret; ret = find(beg,end,10); cout << *ret << endl; ......

建议

之于array,vector虽略胜一筹,但有它的硬伤,那就是它动态增大的时候,空间操作耗费大,特别是当vector内的元素很多的时候。

vector还提供insert,earse,clear等元素的操作,不一一复述。最后是很不错的vector文档:http://www.cplusplus.com/reference/stl/vector/

本文完 2012-10-16

捣乱小子 http://www.daoluan.net/


私房STL之list

一句话list:list是我们在数据结构中接触过的双向循环链表,应用有约瑟夫环;可见其空间非连续的,但可以动态扩充,效率很高,只是不支持随机访问,必须通过迭代器找到指定的元素。总的来说,list用起来比较顺手。

list_node

list的查找

按上述遍历元素的方法查找,复杂度为O(n)。STL算法实现了find(),可以在指定的迭代器始末寻找指定的元素。

...... list<int> il; il.push_back(5); il.push_back(98); il.push_back(7); il.push_back(20); il.push_back(22); il.push_back(17); list<int>::iterator ite; ite = find(il.begin(),il.end(),20); cout << *ite << endl;/*20*/ ......

list创建与遍历

STL中也为list实现了几个版本的构造函数:http://www.cplusplus.com/reference/stl/list/list/,有最简单缺省的版本。

list的遍历使用迭代器,如下:

#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { unsigned int i; list<int> il; il.push_back(5); il.push_back(98); il.push_back(7); il.push_back(20); il.push_back(22); il.push_back(17); list<int>::iterator ite; for(ite = il.begin(); ite != il.end(); ite++) cout << *ite << " "; cout << endl; return 0; }

list在空间拓展的时候,没有经历vector式的空间倒腾,所以只要不earse元素,指向它ite是不会失效的。

list元素操作

list有提供pop_back,erase,clear,insert等实用的元素操作,不一一复述,给出有用的文档:http://www.cplusplus.com/reference/stl/list/

list排序

STL算法(<algorithm>)实现的sort只适用于支持随机访问的数据,所以它不适用于list,list不支持随机访问。所以list内部实现了自己的sort,内部排序使用使用迭代版本的快排。

unsigned int i; list<int> il; il.push_back(5); il.push_back(98); il.push_back(7); il.push_back(20); il.push_back(22); il.push_back(17); list<int>::iterator ite; for(ite = il.begin(); ite != il.end(); ite++) cout << *ite << " "; cout << endl; il.sort(); for(ite = il.begin(); ite != il.end(); ite++) cout << *ite << " "; cout << endl; return 0;

5 98 7 20 22 175 7 17 20 22 98请按任意键继续. . .

建议

list使用轻松自如,硬伤是由于空间的个性(不连续),不能随机访问。

本文完 2012-10-16

捣乱小子 http://www.daoluan.net/


私房STL之deque

一句话deque:deque是双端队列,它的空间构造并非一个vector式的长数组,而是“分段存储,整体维护”的方式;STL允许在deque中任意位置操作元素(删除添加)(这超出了deque的概念,最原始的deque将元素操作限定在队列两端),允许遍历,允许随机访问(这是假象);我们将看到,deque将是STL中stack和queue的幕后功臣,对deque做适当的修正,便可以实现stack和queue。

bug,deque_in_real

deque的迭代器

deque的迭代器与一般的迭代器不同,并不是vector或者list的普通指针式迭代器,有必要写下。

...... typedef T map_pointer; T* cur;//指向当前元素 T* first;//指向缓冲区头 T* last;//指向缓冲区尾巴 map_pointer node;//二级指针,指向缓冲区地址表中的位置 ......

实现的复杂度可见一斑。正是因为deque复杂的空间结构,其迭代器也想跟着复杂晦涩。于是很容易令人产生异或!

为什么要用这么复杂的空间结构

同学A会疑问:“为什么不直接使用似vector抑或array一个长的数组?这样实现起来简单,而且迭代器也不会像”这个问题很容易被解决,想想:array就不用解释了,因为它是静态的空间,不支持拓展;另外,回想一下,vector在做空间拓展的时候,是如何劳神伤肺?!vector是依从“重新配置,,释放”规则,这样的代价是很划不来的。所以宁愿实现复杂的迭代器,来换取宝贵的计算机资源。

那么deque在做空间拓展的时候是如何做的呢?

如果缓冲区中还有备用的空间,那么直接使用备用的空间;否则,另外配置一个缓冲区,将其信息记录到缓冲区地址表里;更有甚者,如果缓冲区地址表都不够的时候,缓冲区地址表也要严格依从“重新配置,,释放”规则,但相比对“重新配置,,释放”规则宗教式追狂热的vector而言,效率高很多。

deque的创建与遍历

STL中deque有提供多种版本的构造函数,一把使用缺省构造函数。

...... deque<int> id; ......

同样,虽迭代器庞杂,但使用游刃有余,和其他的容器保持一致;并且,迭代器有重载“[]”运算符,所以支持“随机访问”(其实这是假象,详见上述内容)。

...... deque<int> id; id.push_back(1); id.push_back(2); id.push_back(3); id.push_back(4); id.push_back(5); id.push_back(6); cout << id[2] << endl; /*3*/ ......

deque的查找

有迭代器在,查找可以用STL<algorithm>内部实现的find()。当然,有重载“[]”运算符,按普通的顺序查找也可行。这里只给出迭代器版本:

...... deque<int> id; id.push_back(1); id.push_back(2); id.push_back(6); deque<int>::iterator ite; ite = find(id.begin(),id.end(),6); cout << *ite << endl; /*6*/ ......

deque的排序

我们已经知道,deque实际不是连续的存储空间,它使用了“分段存储,整体维护”的空间模式,当然代价是庞杂的迭代器。所以STL<algorithm>的sort()函数在这里并不适用。侯杰老师推荐,将deque所有的元素倒腾到一个vector中,再用STL<algorithm>的sort()函数,再从vector中倒腾进deque中。这种折腾是必须的,直接在的deque内部进行排序,效率更低。

建议

deque在实际的应用当中使用的比较少,但正如文章开头指出的,它是容器stack和queue的幕后功臣,所以了解它的内部实现机制多多益善。

本文完 2012-10-17

捣乱小子 http://www.daoluan.net/


私房STL之stack与queue

一句话stack和queue:相对于deque,stack和queue没有那么底层,他们大部分底层的操作都由deque一手操办,特别的stack和queue是deque的子集(换句话说,stack、queue管deque叫老爹);通过关闭或者限制deque的一些接口就可以轻易实现stack和queue(STL源码剖析中管这种机制叫“adapter”。);由stack和queue的定义来看,它们的遍历动作是不被允许的,没有迭代器概念;有趣的是,通过修改list的接口,同样可以让list假冒stack和queue。

stack

==================

queue

stack的创建与遍历

除了默认的构造函数,stack和其他很多容器一样,支持依据vector中元素创建stack。只给出默认版本:更多的资料:http://www.cplusplus.com/reference/stl/stack/stack/

..... stack<int> is; is.push(4); is.push(3); is.push(2); is.push(1); is.push(0); while(!is.empty()) { cout << is.top() << " "; is.pop(); }// while /*0 1 2 3 4*/ .....

stack不允许遍历!

queue的创建与遍历

...... queue<int> iq; iq.push(4); iq.push(3); iq.push(2); iq.push(1); iq.push(0); cout << iq.back() << endl; /*0*/ while(!iq.empty()) { cout << iq.front() << " "; iq.pop(); }// while /*4 3 2 1 0*/ ......

queue不允许遍历!

stack/queue的查找和排序

stack/queue不允许遍历!

关于stack的top()和pop()

在数据结构的课程中,习惯将上面两个功能都整合到pop中去,但STL分开了,一个函数只做一件事情,在queue中也是这样做的。

...... Sequence c; // 底层容器 ...... reference top() { return c.back(); } void pop() { c.pop_back(); } ......

从Sequence c的定义当中可以看出一些端倪,stack允许用户选定底层容器,所以list此时可以作为底层容器来实现stack/queue。

...... stack<int,list<int>> is; is.push(4); is.push(3); is.push(2); is.push(1); is.push(0); while(!is.empty()) { cout << is.top() << " "; is.pop(); }// while /*0 1 2 3 4*/ ......

建议

stack/queue在实际应用用的比较多,两者有很大的共性,因此queue被提取出来。嘿嘿,突然对STL肃然起敬。

关于更多的stack和queue请参看:http://www.cplusplus.com/reference/stl/stack/和http://www.cplusplus.com/reference/stl/queue/

本文完 2012-10-19

捣乱小子 http://www.daoluan.net/

转载请注明原文地址: https://www.6miu.com/read-2650127.html

最新回复(0)