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

红太狼 2021-12-01 19:44 225阅读 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 条评论，225人围观）

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

相关阅读

相关 C++标准库 -- 关联容器 (Primer C++ 第五版 · 阅读笔记)

C++标准库 -- 关联容器(Primer C++ 第五版 · 阅读笔记）第11章关联容器------(持续更新) 11.1、使用关联容器

谁借莪１个温暖的怀抱￠/ 2024年03月23日 13:01/ 0 赞/ 53 阅读

相关 C++标准库 -- 顺序容器 (Primer C++ 第五版 · 阅读笔记)

C++标准库 -- 顺序容器(Primer C++ 第五版 · 阅读笔记）第9章顺序容器------(持续更新) 9.1、顺序容器概述

r囧r小猫/ 2024年03月23日 09:53/ 0 赞/ 75 阅读

相关 c++学习笔记第四部分

Part 4 一 this指针有一个特殊的指针，它叫做this。我们从来没有见过他，但是他却从来都存在。我们通过一个典型的例子来认识它： class Human \

布满荆棘的人生/ 2023年07月23日 09:59/ 0 赞/ 2 阅读

相关算法红皮书第四版读书笔记（四）图

> 在许多计算机应用中，由相连的结点所表示的模型起到了关键的作用。这些结点之间的连接很自然地会让人们产生一连串的疑问： > > 沿着这些连接能否从一个结点到达另一个结点？有多

桃扇骨/ 2023年07月14日 08:19/ 0 赞/ 31 阅读

相关算法红皮书第四版读书笔记（三）查找

> 现代计算机和网络使我们能够访问海量的信息。高效检索这些信息的能力是处理它们的重要前提。本章描述的都是数十年来在广泛应用中经过实践检验的经典查找算法。符号表：我们会使

布满荆棘的人生/ 2023年07月13日 15:10/ 0 赞/ 21 阅读

相关算法红皮书第四版读书笔记（二）排序

排序算法类的模板 public static void sort(Comparable[] a) { } priv

约定不等于承诺〃/ 2023年07月13日 13:54/ 0 赞/ 21 阅读

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

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

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

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

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

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

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

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

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

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

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

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