<C++Primer>第四版阅读笔记第二部分 “容器和算法”

红太狼 2021-12-01 19:44 162阅读 0赞

泛型算法中，所谓“泛型（generic）”指的是两个方面：这些算法可作用于各种不同的容器类型，而这些容器又可以容纳多种不同类型的元素。

# 第九章 顺序容器 #

顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。

IO库类型不支持复制或赋值。因此，不能创建存放IO类型对象的容器。

定义容器的容器时，注意使用空格：

vector< vector<string> > lines; OK

vector<vector<string>> lines; ERROR

两个迭代器相加的操作是未定义的。

vector和deque容器提供了对元素的快速随机访问，但付出的代价是，在容器的任意位置插入或删除元素，比在容器尾部插入和删除的开销更大。list类型的任何位置都能快速插入和删除，但付出的代价是元素的随机访问开销较大。

在list容器的元素之间移动的唯一方法是顺序跟随指针。

string类型与vector容器不同的是，它不支持以栈方式操纵容器：在string类型中不能使用front、back和pop\_back操作。

# 第十章 关联容器 #

关联容器与顺序容器的区别：关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

关联容器支持通过键来高效地查找和读取元素。两个基本的关联容器类型是map和set。map的元素以键-值（key-value）对的形式组织：键用作元素在map中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。

一般来说，如果希望有效地存储不同值的集合，那么使用set容器比较合适，而map容器则更适用于需要存储（乃至修改）每个键所关联的值的情况。

关联容器不能通过容器大小来定义，因为这样的话就无法知道键所对应的值是什么。

对于键类型，唯一的约束就是必须支持 < 操作。

map<K,V>::value\_type 一个pair类型，它的first元素具有constmap<K,V>::key\_type类型，而second元素则为map<K,V>::mapped\_type类型。

在学习map的接口时，需谨记value\_type是pair类型，它的值成员可以修改，但键成员不能修改。

map迭代器进行解引用将产生pair类型的对象。

使用下标访问map与使用下标访问数组或vector的行为截然不同：用下标访问不存在的元素将导致在map容器中添加一个新的元素，它的键即为该下标值。

\--------------------经典的小代码--------------------

// count number of times each word occurs in the input

map<string,int> word\_count; //empty map from string to int

string word;

while (cin>>word)

\++word\_count\[word\];

\--------------------经典的小代码--------------------

在添加新的map元素时，使用insert成员可避免使用下标操作符所带来的副作用：不必要的初始化。

map对象中一个给定键只对应一个元素。如果试图插入的元素所对应的键已在容器中，则insert将不做任何操作。

查找并读取map中的元素：如果希望当具有指定键的元素存在时，就获取该元素的引用，否则就不在容器中创建新的元素，那么应该使用find。

set容器只是单纯的键的集合。set不支持下标操作符，而且没有定义mapped\_type类型。与map一样，set容器存储的键也必须唯一，而且不能修改。

在获得指向set中某元素的迭代器后，只能对其做读操作，而不能做写操作。

在multimap中，同一个键所关联的元素必然相邻存放。

# 第十一章 泛型算法 #

关键概念：泛型算法永不执行容器提供的操作

理解算法的最基本方法是了解该算法是否读元素、写元素或者对元素进行重新排序。

初学者常犯的错误：在没有元素的空容器上调用fill\_n函数（或者类似的写元素算法）。

流迭代器的限制：

1、不可能从ostream\_iterator对象读入，也不可能写到istream\_iterator对象中。

2、一旦给ostream\_iterator对象赋了一个值，写入就提交了。赋值后，没有办法在改变这个值。此外，ostream\_iterator对象中每个不同的值都只能正好输出一次。

3、ostream\_iterator没有->操作符。

标准库定义了五种迭代器类型：输入、输出、前向、双向和随机访问迭代器。

算法从不直接改变它所操纵的序列的大小。（如果算法的实参是插入迭代器，则该迭代器会添加新元素，但算法并不直接这么做。）

待继续····

转载于:https://www.cnblogs.com/fengty90/p/3768871.html

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关 Hibernate实战(第二版)笔记----第四章--映射持久化类

一、本章主要介绍了实体类型: 该类的实例有OID,一个实例对应表的一条记录，实例的OID就是该记录的主键。一个实例可以被多个其他实体对象共享引用

╰+攻爆jí腚メ/ 2022年06月13日 09:54/ 0 赞/ 225 阅读

相关算法导论-第二部分-读书笔记

\第六章 \\堆 \\\6.1 什么是堆？（二叉）堆是一个“数组”，它可以被看成一个挖的完全二叉树，树上每一个结点对应数组中一个元素。除了最底层外

男娘i/ 2022年05月31日 13:50/ 0 赞/ 243 阅读

相关算法导论-第四部分-读书笔记

第十五章动态规划 15.1 钢条切割这里要算的是切割的段数，和从切头切还是从尾切没有关系，只要计算切前1米后，后面的米数的各种可能性切前2米后

Myth丶恋晨/ 2022年05月31日 13:50/ 0 赞/ 593 阅读

相关算法导论-第六部分-读书笔记

第二十一章用于不相交集合的数据结构 > 第二十一章本来是第五部分里的，但它的内容和第六部分关系更为密切，所以放到了这里。 21.1 不相交集合的操作不相交集合

约定不等于承诺〃/ 2022年05月31日 13:15/ 0 赞/ 284 阅读

相关算法导论-第五部分-读书笔记

第十八章 B树 B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树，它在降低磁盘 IO 操作回数方面要更好一些，许多数据库系统使用 B树或者 B树的变种来存

待我称王封你为后i/ 2022年05月31日 13:15/ 0 赞/ 223 阅读

相关 04《算法（第四版）·Robert Sedgewick等》读书笔记

目录第1章基础 1.1 基础编程模型 1.1.1 Java程序的基本结构 1.1.2 原始数据类型与表达式

短命女/ 2022年04月17日 01:13/ 0 赞/ 339 阅读

相关第四版阅读笔记第二部分 “容器和算法”

泛型算法中，所谓“泛型（generic）”指的是两个方面：这些算法可作用于各种不同的容器类型，而这些容器又可以容纳多种不同类型的元素。第九章顺序容器顺序

红太狼/ 2021年12月01日 19:44/ 0 赞/ 163 阅读

相关 C#入门经典（第6版）阅读笔记（第二篇）（11章集合比较和转换）

目录第十一章集合、比较和转换 -------------------- 第十一章集合、比较和转换集合：可以使用集合来维护数组，控制对它们对象的

喜欢ヅ旅行/ 2021年06月24日 16:11/ 0 赞/ 258 阅读

相关 C#入门经典（第6版）阅读笔记（第四篇）（ASP.NET WEB 编程）

目录第十九章 ASP.NET WEB 编程 -------------------- 第十九章 ASP.NET WEB 编程前言：由于目前我在这边以后主

ゞ浴缸里的玫瑰/ 2021年06月24日 16:11/ 0 赞/ 283 阅读

相关算法图解阅读笔记——第四曲（狄克斯特拉算法和贪婪算法）

目录结构第7章狄克斯特拉算法第8章贪婪算法 -------------------- 正文狄克斯特拉算法 ![在这里插入图片描述][water

系统管理员/ 2021年05月12日 11:50/ 0 赞/ 537 阅读