pay attention.”從這個意義上看，這本 書並非完全“免費”。為了不辜負你為本書所付出的寶貴“注意力”，我會竭盡所能，投入最大的“注意力” 來完成本書的創作。 本人自知學疏才淺，書中內容雖然已經過一段時間的打磨，但一定仍有許多錯誤，懇請各位老師與同學批評 指正。 本書中的程式碼附有可一鍵執行的原始檔，託管於 github.com/krahets/hello‑algo 倉庫。 動畫在 願這本書在你的腦海中輕輕響起，留下獨特而深刻的旋律。 第 0 章 前言 www.hello‑algo.com 2 0.1 關於本書 本專案旨在建立一本開源、免費、對新手友好的資料結構與演算法入門教程。 ‧ 全書採用動畫圖解，內容清晰易懂、學習曲線平滑，引導初學者探索資料結構與演算法的知識地圖。 ‧ 源程式碼可一鍵執行，幫助讀者在練習中提升程式設計技能，瞭解演算法工作原理和資料結構底層實 現。 ‧ 提倡讀者互助學習，歡迎 碼可以當作“刷題工具庫”或“演算法字典”來使用。 若你是演算法“大神”，我們期待收到你的寶貴建議，或者一起參與創作。 前置條件 你需要至少具備任一語言的程式設計基礎，能夠閱讀和編寫簡單程式碼。 0.1.2 內容結構 本書的主要內容如圖 0‑1 所示。 ‧ 複雜度分析：資料結構和演算法的評價維度與方法。時間複雜度和空間複雜度的推算方法、常見型別、 示例等。 ‧ 資料結構：基本資料型別和資料結構的分類方法。陣列、

edu.tw）。虽然不一定能够每封来函都回复，但是我乐于 知道读者的任何点点滴滴。 3 关于《深入浅出 MFC》2/e 电子书 《深入浅出 MFC》2/ e 电子书共有五个档案： 档名 內容 大小 bytes dissecting MFC 2/e part1.pdf chap1~chap3 3,384,209 dissecting MFC 2/e part2.pdf chap4 是翻翻看，大致了解一 下，待有空时或是工作上需要时再好好细读。 网络书局的盛行，让我也开始上网买些书。但是我只敢买像您的书！有品质嘛！其它的可就 不敢直接买啰，总是必須到书局翻翻看，确定一下內容，才可能考虑。 vii 台北市Jedi Your books is already 100 times better than any translation on the market. I won't Studio 与MFC（Microsoft Foundation Classes）相配合，构成了一个强大 的利用C++ 进行32 位Windows 程序开发的工具，但是由于MFC 系统相当庞大，内 容繁杂，并且夹杂着大量令初学者莫明其妙的macros，更加大了学习上的难度。 当今市面上有不少讲解C++ 和VC++ 程序设计的书籍，但C++ 书籍单纯只讲C++，从 C++ 过渡到VC++ 却是初学者的一大难关；大多数讲解VC++

是不需要重 新分配内存的，也就不会移动元素导致指 针失效。 vector 容器： capacity 函数查询实际的最大容量 • 可以用 capacity() 函数查询已经分配内存的大小，即最大容 量。 • 而 size() 返回的其实是已经存储了数据的数组长度。 • 可以发现当 resize 指定的新长度一个超过原来的最大容量时 时，就会重新分配一段更大容量的内存来存储数组，只有这时 存的时候，我们就能轻松看到。 • 不过这个只能 Linux 系统可以用哦 。 vector 容器： push_back 的问题 • 由于不知道你究竟会推入多少个元素， vector 的初始容 量是零，而 push_back 和 resize 一样，每次遇到容量 不足时，都会扩容两倍，如图。 • 这也体现了实际容量 (capacity) 和数组大小 (size) 分离 的好处，如果死板地让分配的内存容量始终等于当前数 的值，重复的次数（长度）也是参数里指定。 • a.assign(n, val) 基本和 a = vector(n, val) 等价，唯 一的区别是后者会重新分配内存，而前者会保留原来的容 量。 • void assign(size_t n, int const &val); vector 容器： assign 函数 • assign 还可以直接接受一个初始化列表作为参数。 •

C++ 标准库系列课 - 你所不知道的 set 容 器 by 小彭老师（ @archibate ） 课件 & 代码： https://github.com/parallel101/course 上期回顾： https://www.bilibili.com/video/BV1qF411T7sd 课程安排 1. vector 容器初体验 & 迭代器入门 (BV1qF411T7sd) 2. 你所不知道的 中 pair 的定义 • pair 类似于 python 里的元组，不过固定只能有两个元素，自从 C++11 引 入了能支持任意多元素的 tuple 以来，就没 pair 什么事了……但是为了兼 容 pair 还是继续存在着。 pair 是个模板类，根据尖括号里你给定的类型来 替换这里的 _T1 和 _T2 。例如 pair 就会变成： • struct pair

这样 main 里面就可以仅通过函数名从 functab 访问到他们，从而 catFunc 和 dogFunc 甚至不需要在头文件里声明（只需 要他们的函数签名一样即可放入 function 容 器）。 静态初始化的顺序是符号定义的顺序决定的，若在不同文件则顺序可能打乱 • 你可能已经兴冲冲地把 dogFunc 和 catFunc 挪到另一个文件，然后把 functab 声明为

以利用这一点实现稀疏？ • 而当我们试图用 malloc 分配一段 4TB 的 内存，却出错了，明明说是惰性分配的？ • 这是因为 glibc 在操作系统上做了很多事， 他会判断申请的大小是否超过了现有内存容 量，目的是为了防止用户犯错。 • 因此，想要追求稀疏的我们，最好想办法绕 开 glibc ，直接和操作系统打交道。 解决：绕开 glibc ，直接调用操作系统的 mmap 分配 • 那么就要用到

不接受参数，仅仅作为同步用， 不传递任何实际的值。 第 3 章：互斥量 多线程打架案例 • 两个线程试图往同一个数组里推数据。 • 奔溃了！为什么？ • vector 不是多线程安全（ MT-safe ）的容 器。 • 多个线程同时访问同一个 vector 会出现 数据竞争（ data-race ）现象。 std::mutex ：上锁，防止多个线程同时进入某一代码段 • 调用 std::mutex

核才饱和。 • 结论：要想利用全部 CPU 核心，避免 mem-bound ，需要 func 里有足够的计算 量。 • 当核心数量越多， CPU 计算能力越强，相 对之下来不及从内存读写数据，从而越容 易 mem-bound 。 1 2 4 6 8 10 0 50 100 150 200 250 300 350 funcA funcB funcC 内存信息查看工具： dmidecode

第三步：运行源代码。如图 0‑5 所示，对于顶部标有文件名称的代码块，我们可以在仓库的 codes 文件夹内 找到对应的源代码文件。源代码文件可一键运行，将帮助你节省不必要的调试时间，让你能够专注于学习内 容。 图 0‑5 代码块与对应的源代码文件 0.2.4 在提问讨论中共同成长 在阅读本书时，请不要轻易跳过那些没学明白的知识点。欢迎在评论区提出你的问题，我和小伙伴们将竭诚 为你解答，一般情况下可在两天内回复。 地，基于链表实现的数据结构被称为“动态数据结构”，这类数据结构在初始化后，仍可以在程序运行过程中 对其长度进行调整。 � 如果你感觉物理结构理解起来有困难，建议先阅读下一章“数组与链表”，然后再回顾本节内 容。 3.2 基本数据类型 谈及计算机中的数据，我们会想到文本、图片、视频、语音、3D 模型等各种形式。尽管这些数据的组织形式 各异，但它们都由各种基本数据类型构成。 基本数据类型是 CPU 可 hello‑algo.com 130 2. Q & A � 哈希表的时间复杂度为什么不是 ?(?) ？ 当哈希冲突比较严重时，哈希表的时间复杂度会退化至 ?(?) 。当哈希函数设计的比较好、容 量设置比较合理、冲突比较平均时，时间复杂度是 ?(1) 。我们使用编程语言内置的哈希表时， 通常认为时间复杂度是 ?(1) 。 � 为什么不使用哈希函数 ?(?) = ? 呢？这样就不会有冲突了

std::unordered_set/std::unordered_multiset。 它们的用法和原有的 std::map/std::multimap/std::set/set::multiset 基本类似，由于这些容 器我们已经很熟悉了，便不一一举例，我们直接来比较一下 std::map 和 std::unordered_map： #include #include