cpp vector学习笔记

起因是百度实习二面的时候被问了一道类似这样的题:

给我下面的代码,问有没有什么问题。

面试的时候只给了部分代码,func函数没有给出。

当时没有看出问题在哪里…

后来知道了,这道题其实考的是vector的底层实现…

以下内容参考《STL源码解析》4.2章 侯捷著

vector是动态增加空间,但是并不是在原空间后面增加新空间(因为不能保证原空间之后是否还有可以配置的空间),而是以原大小的两倍另外配置一块较大空间,然后将原内容拷贝过来,之后才开始在原内容后面构建新内容,并释放原空间。

因此,对vector的任何操作,一旦引起对空间重新配置,指向原vector的所有迭代器都失效了!

因此,对vector的任何操作,一旦引起对空间重新配置,指向原vector的所有迭代器都失效了!

因此,对vector的任何操作,一旦引起对空间重新配置,指向原vector的所有迭代器都失效了!

 

vector采取的是存储方式是连续线性空间,用两个迭代器start和finsh分别指向当前配置的空间中已经使用的部分的开始和结尾,用另一个迭代器end_of_storage指向当前配置的整块连续空间(包含备用部分)的尾端。

当我们用push_back()将元素插入vector尾端时,push_back()会先检查是是否还有备用空间,如果有就直接在备用空间上构建元素,并调整迭代器finsh,使vector变大。如果没有备用空间了,就扩充空间。

 

可以用以下代码来测试:

结果如下:

codeforces 29 C. Mail Stamps

http://codeforces.com/contest/29/problem/C
题意:给出n个边的关系,保证可以构成一条链。正向或者反向输出这个链。
思路:由于下标很大(1E9),而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs…