一句话vector:vector的空间可扩充,支持随机存取访问,是一段连续线性的空间。所以它是动态空间,与之对比的array是静态的空间,不可扩充。简单来说,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; ......在经常需要删除操作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是另外新分配一个比原有更大的空间(原有空间*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!!!3 3 3 10 9 00 3 3 3 9 10请按任意键继续. . .
按上述遍历元素的方法查找,复杂度为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/
一句话list:list是我们在数据结构中接触过的双向循环链表,应用有约瑟夫环;可见其空间非连续的,但可以动态扩充,效率很高,只是不支持随机访问,必须通过迭代器找到指定的元素。总的来说,list用起来比较顺手。
list_node按上述遍历元素的方法查找,复杂度为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*/ ......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有提供pop_back,erase,clear,insert等实用的元素操作,不一一复述,给出有用的文档:http://www.cplusplus.com/reference/stl/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/
一句话deque:deque是双端队列,它的空间构造并非一个vector式的长数组,而是“分段存储,整体维护”的方式;STL允许在deque中任意位置操作元素(删除添加)(这超出了deque的概念,最原始的deque将元素操作限定在队列两端),允许遍历,允许随机访问(这是假象);我们将看到,deque将是STL中stack和queue的幕后功臣,对deque做适当的修正,便可以实现stack和queue。
bug,deque_in_realdeque的迭代器与一般的迭代器不同,并不是vector或者list的普通指针式迭代器,有必要写下。
...... typedef T map_pointer; T* cur;//指向当前元素 T* first;//指向缓冲区头 T* last;//指向缓冲区尾巴 map_pointer node;//二级指针,指向缓冲区地址表中的位置 ......实现的复杂度可见一斑。正是因为deque复杂的空间结构,其迭代器也想跟着复杂晦涩。于是很容易令人产生异或!
同学A会疑问:“为什么不直接使用似vector抑或array一个长的数组?这样实现起来简单,而且迭代器也不会像”这个问题很容易被解决,想想:array就不用解释了,因为它是静态的空间,不支持拓展;另外,回想一下,vector在做空间拓展的时候,是如何劳神伤肺?!vector是依从“重新配置,,释放”规则,这样的代价是很划不来的。所以宁愿实现复杂的迭代器,来换取宝贵的计算机资源。
那么deque在做空间拓展的时候是如何做的呢?
如果缓冲区中还有备用的空间,那么直接使用备用的空间;否则,另外配置一个缓冲区,将其信息记录到缓冲区地址表里;更有甚者,如果缓冲区地址表都不够的时候,缓冲区地址表也要严格依从“重新配置,,释放”规则,但相比对“重新配置,,释放”规则宗教式追狂热的vector而言,效率高很多。
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*/ ......有迭代器在,查找可以用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实际不是连续的存储空间,它使用了“分段存储,整体维护”的空间模式,当然代价是庞杂的迭代器。所以STL<algorithm>的sort()函数在这里并不适用。侯杰老师推荐,将deque所有的元素倒腾到一个vector中,再用STL<algorithm>的sort()函数,再从vector中倒腾进deque中。这种折腾是必须的,直接在的deque内部进行排序,效率更低。
deque在实际的应用当中使用的比较少,但正如文章开头指出的,它是容器stack和queue的幕后功臣,所以了解它的内部实现机制多多益善。
本文完 2012-10-17
捣乱小子 http://www.daoluan.net/
一句话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和其他很多容器一样,支持依据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不允许遍历!
stack/queue不允许遍历!
在数据结构的课程中,习惯将上面两个功能都整合到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/