没有合适的资源?快使用搜索试试~ 我知道了~
首页STL学习指南:突破与挑战
STL学习指南:突破与挑战
需积分: 11 0 下载量 97 浏览量
更新于2024-07-28
收藏 1.04MB PDF 举报
"Efficient STL" 是一本经典的编程指南,专注于C++标准模板库(STL)的学习,作者在1995年开始撰写相关文章,最初是作为《More Effective C++》的一个补充部分。然而,由于当时作者对STL的理解不够深入,他未能立即分享自己的见解。随着作者对STL的实践经验逐渐积累,他发现尽管STL在效率和可扩展性上有显著优势,但在实际应用过程中却遇到了诸多挑战:不同编译器对模板的支持差异大,且文档匮乏,错误处理复杂,难以理解和解决。 STL的学习资料稀缺,使得理解和掌握其编程方式变得困难。然而,尽管存在这些难题,作者观察到许多实际的程序员,包括他的咨询客户,仍在积极地使用STL进行产品开发,表明其在业界的应用和接受度正在不断提高。尽管STL在移植性、文档和错误信息方面存在问题,但其出色的设计理念和功能强大性使专业程序员认为哪怕版本不够完美,也胜过没有可用的库。 随着时间的推移,STL的境况在不断改善,标准兼容性和文档质量得到了提升。作者意识到,STL的未来是光明的,即使现在的问题尚存,但它在提升代码质量和编程效率方面的作用不可忽视。因此,尽管作者曾对是否推荐STL给实践中的程序员持保留态度,但他认识到STL已经成为C++编程的重要组成部分,值得深入学习和利用。 总结来说,"Efficient STL" 提供了一条从入门到精通STL的路径,强调了这个库在C++编程中的核心地位,同时揭示了在实践中面临的挑战和改进的趋势。对于任何希望提升C++编程技能,特别是使用STL的开发者来说,这本书提供了宝贵的经验和指导。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/4391920/bg10.jpg)
条款1:仔细选择你的容器
新元素被查入或者已存元素被删除,其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空
间或者填充原来被删除的元素所占的空间。这种移动影响了效率(参见条款5和14)和异常安全(就像我们将
会看到的)。标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。
基于节点的容器
在每个内存块(动态分配)中只保存一个元素。容器元素的插入或删除只影响指向节点的指
针,而不是节点自己的内容。所以当有东西插入或删除时,元素值不需要移动。表现为链表的容器——比如
list和slist——是基于节点的,所有的标准关联容器也是(它们的典型实现是平衡树)。非标准的散列容器使
用不同的基于节点的实现,就像我们将会在条款25中看到的。
利用这个不恰当的术语,我们已经准备好描述一些大多数关于在容器间选择的问题。在这个讨论中,我略过
考虑非STL类容器(比如,数组、bitset等),因为毕竟这是本关于STL的书。
●
你需要“可以在容器的任意位置插入一个新元素”的能力吗?
如果是,你需要序列容器,关联容器做
不到。
●
你关心元素在容器中的顺序吗?
如果不,散列容器就是可行的选择。否则,你要避免使用散列容器。
●
必须使用标准C++中的容器吗?
如果是,就可以除去散列容器、slist和rope。
●
你需要哪一类迭代器
?如果必须是随机访问迭代器,在技术上你就只能限于vector、deque和string,但
你也可能会考虑rope(关于rope的更多信息在条款50)。如果需要双向迭代器,你就用不了slist(参见
条款50)和散列容器的一般实现(参见条款25)。
●
当插入或者删除数据时,是否非常在意容器内现有元素的移动?
如果是,你就必须放弃连续内存容器
(参见条款5)。
●
容器中的数据的内存布局需要兼容C吗?
如果是,你就只能用vector(参见条款16)。
●
查找速度很重要吗?
如果是,你就应该看看散列容器(参见条款25),排序的vector(参见条款23)和
标准的关联容器——大概是这个顺序。
●
你介意如果容器的底层使用了引用计数吗?
如果是,你就得避开string,因为很多string的实现是用引
用计数(参见条款13)。你也不能用rope,因为权威的rope实现是基于引用计数的(参见条款50)。
于是你得重新审核你的string,你可以考虑使用vector<char>。
●
你需要插入和删除的事务性语义吗?
也就是说,你需要有可靠地回退插入和删除的能力吗?如果是,
你就需要使用基于节点的容器。如果你需要多元素插入(比如,以范围的方式——参见条款5)的事
务性语义,你就应该选择list,因为list是唯一提供多元素插入事务性语义的标准容器。事务性语义对
于有兴趣写异常安全代码的程序员来说非常重要。(事务性语义也可以在连续内存容器上实现,但会
有一个性能开销,而且代码不那么直观。要了解这方面的知识,请参考Sutter的《Exceptional C++》的
条款17
[8]。)
●
你要把迭代器、指针和引用的失效次数减到最少吗?
如果是,你就应该使用基于节点的容器,因为在
这些容器上进行插入和删除不会使迭代器、指针和引用失效(除非它们指向你删除的元素)。一般来
说,在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
●
你需要具有有以下特性的序列容器吗:1)可以使用随机访问迭代器;2)只要没有删除而且插入只发
file:///D|/Documents%20and%20Settings/Fingster/My%20Documents/Effective%20STL/item_01.html (2 of 3)2005-4-26 15:14:47
![](https://csdnimg.cn/release/download_crawler_static/4391920/bg11.jpg)
条款1:仔细选择你的容器
生在容器结尾,指针和引用的数据就不会失效?
这个一个非常特殊的情况,但如果你遇到这种情况,
deque就是你梦想的容器。(有趣的是,当插入只在容器结尾时,deque的迭代器也可能会失效,deque
是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。)
这些问题几乎不是事情的完结。比如,它们没有关注不同的容器类型使用不同的内存配置策略(条款10和14
讨论了这些策略的一些方面)。但是,它们已经足够是你信服了,除非你对元素顺序、标准的一致性、迭代
器能力、内存布局和C的兼容性、查找速度、因为引用计数造成的行为不规则、事务性语义的轻松实现和迭
代器失效的条件没兴趣,你得在容器操作的算法复杂度上花更多的考虑时间。当然这样的复杂度是重要的,
但这离整个故事很远。
当面对容器时,STL给了你很多选项。如果你的视线超越了STL的范围,那就会有更多的选项。在选择一个容
器前,要保证考虑了所有你的选项。一个“默认容器”?我不这么认为。
file:///D|/Documents%20and%20Settings/Fingster/My%20Documents/Effective%20STL/item_01.html (3 of 3)2005-4-26 15:14:47
![](https://csdnimg.cn/release/download_crawler_static/4391920/bg12.jpg)
条款2:小心对“容器无关代码”的幻想
Center of STL Study
——最优秀的STL学习网站
条款2:小心对“容器无关代码”的幻想
STL是建立在泛化之上的。数组泛化为容器,参数化了所包含的对象的类型。函数泛化为算法,参数化了所
用的迭代器的类型。指针泛化为迭代器,参数化了所指向的对象的类型。
这只是个开始。独立的容器类型泛化为序列或关联容器,而且类似的容器拥有类似的功能。标准的内存相邻
容器(参见条款1)都提供随机访问迭代器,标准的基于节点的容器(再参见条款1)都提供双向迭代器。序
列容器支持push_front或push_back,但关联容器不支持。关联容器提供对数时间复杂度的lower_bound、
upper_bound和equal_range成员函数,但序列容器却没有。
随着泛化的继续,你会自然而然地想加入这个运动。这种做法值得赞扬,而且当你写你自己的容器、迭代器
和算法时,你会自然而然地推行它。唉,很多程序员试图把它推行到不同的样式。他们试图在他们的软件中
泛化容器的不同,而不是针对容器的特殊性编程,以至于他们可以用,可以说,现在是一个vector,但以后
仍然可以用比如deque或者list等东西来代替——都可以在不用改变代码的情况下来使用。也就是说,他们努
力去写“容器无关代码”。这种可能是出于善意的泛化,却几乎总会造成麻烦。
最热心的“容器无关代码”的鼓吹者很快发现,写既要和序列容器又要和关联容器一起工作的代码并没有什
么意义。很多成员函数只存在于其中一类容器中,比如,只有序列容器支持push_front或push_back,只有关
联容器支持count和lower_bound,等等。在不同种类中,甚至连一些如insert和erase这样简单的操作在名称和
语义上也是天差地别的。举个例子,当你把一个对象插入一个序列容器中,它保留在你放置的位置。但如果
你把一个对象插入到一个关联容器中,容器会按照的排列顺序把这个对象移到它应该在的位置。举另一个例
子,在一个序列容器上用一个迭代器作为参数调用erase,会返回一个新迭代器,但在关联容器上什么都不返
回。(
条款9给了一个例子来演示这点对你所写的代码的影响。)
假设,然后,你希望写一段可以用在所有常用的序列容器上——vector, deque和list——的代码。很显然,你必
须使用它们能力的交集来编写,这意味着不能使用reserve或capacity(参见
条款14),因为deque和list不支持它
们。由于list的存在意味着你得放弃operator[],而且你必须受限于双向迭代器的性能。这意味着你不能使用需
要随机访问迭代器的算法,包括sort,stable_sort,partial_sort和nth_element(参见
条款31)。
另一方面,你渴望支持vector的规则,不使用push_front和pop_front,而且用vector和deque都会使splice和成员
函数方式的sort失败。在上面约束的联合下,后者意味着你不能在你的“泛化的序列容器”上调用任何一种
sort。
这是显而易见的。如果你冒犯里其中任何一条限制,你的代码会在至少一个你想要使用的容器配合时发生编
file:///D|/Documents%20and%20Settings/Fingster/My%20Documents/Effective%20STL/item_02.html (1 of 4)2005-4-26 15:14:54
![](https://csdnimg.cn/release/download_crawler_static/4391920/bg13.jpg)
条款2:小心对“容器无关代码”的幻想
译错误。可见这种代码有多阴险。
这里的罪魁祸首是不同的序列容器所对应的不同的迭代器、指针和引用的失效规则。要写能正确地和vector,
deque和list配合的代码,你必须假设任何使那些容器的迭代器,指针或引用失效的操作符真的在你用的容器
上起作用了。因此,你必须假设每次调用insert都使所有东西失效了,因为deque::insert会使所有迭代器失效,
而且因为缺少capacity,vector::insert也必须假设使所有指针和引用失效。(条款1解释了deque是唯一一个在迭
代器失效的情况下指针和引用仍然有效的东西)类似的理由可以推出一个结论,所有对erase的调用必须假设
使所有东西失效。
想要知道更多?你不能把容器里的数据传递给C风格的界面,因为只有vector支持这么做(参见
条款16)。你
不能用bool作为保存的对象来实例化你的容器,因为——正如
条款18所阐述的——vector 并非总表现为一个
vector,实际上它并没有真正保存bool值。你不能期望享受到list的常数时间复杂度的插入和删除,因为vector
和deque的插入和删除操作是线性时间复杂度的。
当这些都说到做到了,你只剩下一个“泛化的序列容器”,你不能调用reserve、capacity、operator[]、
push_front、pop_front、splice或任何需要随机访问迭代器的算法;调用insert和erase会有线性时间复杂度而且
会使所有迭代器、指针和引用失效;而且不能兼容C风格的界面,不能存储bool。难道这真的是你想要在你
的程序里用的那种容器?我想不是吧。
如果你控制住了你的野心,决定愿意放弃对list的支持,你仍然放弃了reserve、capacity、push_front和
pop_front;你仍然必须假设所有对insert和erase的调用有线性时间复杂度而且会使所有东西失效;你仍然不能
兼容C风格的布局;而且你仍然不能储存bool。
如果你放弃了序列容器,把代码改为只能和不同的关联容器配合,这情况并没有什么改善。要同时兼容set和
map几乎是不可能的,因为set保存单个对象,而map保存对象对。甚至要同时兼容set和multiset(或map和
multimap)也是很难的。set/map的insert成员函数只返回一个值,和他们的multi兄弟的返回类型不同,而且你
必须避免对一个保存在容器中的值的拷贝份数作出任何假设。对于map和multimap,你必须避免使用operator
[],因为这个成员函数只存在于map中。
面对事实吧:这根本没有必要。不同的容器是不同的,而且它们的优点和缺点有重大不同。它们并不被设计
成可互换的,而且你做不了什么包装的工作。如果你想试试看,你只不过是在考验命运,但命运并不想被考
验。
接着,当天黑以后你认识到你决定使用的容器,嗯,不是最理想的,而且你需要使用一个不同的容器类型。
你现在知道当你改变容器类型的时候,不光要修正编译器诊断出来的问题,而且要检查所有使用容器的代
码,根据新容器的性能特征和迭代器,指针和引用的失效规则来看看那些需要修改。如果你从vector切换到
其他东西,你也需要确认你不再依靠vector的C兼容的内存布局;如果你是切换到一个vector,你需要保证你
不用它来保存bool。
file:///D|/Documents%20and%20Settings/Fingster/My%20Documents/Effective%20STL/item_02.html (2 of 4)2005-4-26 15:14:54
![](https://csdnimg.cn/release/download_crawler_static/4391920/bg14.jpg)
条款2:小心对“容器无关代码”的幻想
既然有了要一次次的改变容器类型的必然性,你可以用这个常用的方法让改变得以简化:使用封装,封装,
再封装。其中一种最简单的方法是通过自由地对容器和迭代器类型使用typedef。因此,不要这么写:
class Widget {...};
vector<Widget> vw;
Widget bestWidget;
... // 给bestWidget一个值
vector<Widget>::iterator i = // 寻找和bestWidget相等的Widget
find(vw.begin(), vw.end(), bestWidget);
要这么写:
class Widget { ... };
typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw;
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget);
这是改变容器类型变得容易得多,如果问题的改变是简单的加上用户的allocator时特别方便。(一个不影响
对迭代器/指针/参考的失效规则的改变)
class Widget { ... };
template<typename T> // 关于为什么这里需要一个template
SpecialAllocator { ... }; // 请参见条款10
typedef vector<Widget, SpecialAllocator<Widget> > WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw; // 仍然能用
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget); // 仍然能用
如果typedef带来的代码封装作用对你来说没有任何意义的话,你仍然会称赞它们可以节省许多工作。比如,
你有一个如下类型的对象
file:///D|/Documents%20and%20Settings/Fingster/My%20Documents/Effective%20STL/item_02.html (3 of 4)2005-4-26 15:14:54
剩余244页未读,继续阅读
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://profile-avatar.csdnimg.cn/35931c6d771f4398af8049228d2238d2_gemire.jpg!1)
gemire
- 粉丝: 34
- 资源: 7
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- AirKiss技术详解:无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验:位示图法管理磁盘空闲空间
- JSON详解:数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析:WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型:便捷管理与低成本优势
- 机器学习入门指南:从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS:优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso:加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战:轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)