这本书，我在北师大图书馆和它有过一面之缘。当时随意翻了几页就被吸引到了，然而毕竟是讲算法相关的东西，上学的时候耐心不足，没能下定决心借去读。
终于又在苏州图书馆偶遇此书，看来有缘，不妨一读。
（注：后来发现这本书的英文版可以免费在线阅读，http://elementsofprogramming.com/）
这本书的作者，是C++ STL的创始人。这本书涉及大量基础算法，很多都是C++ STL里面存在的。可是这本书并不是讲STL的书。
这本书讲的是Elements of Programming，这也是这本书的原书名；编程原本，即编程的本质。作者借助严密的数学工具来定义一系列算法和相关的数据结构。可以说，这本书也展现了STL的设计理念和思路。
书中算法并非用C++语言实现的，而是C++的一个变种，一个现实中并不存在的变种。但这个C++变种也是C++创始人操刀参与设计的！
加入了Concept的C++20与书中所采用的变种C++极为相似。而本书中也有Concept，虽然与C++20的Concept不尽相同，但也可以说是殊途同归。作者进行严密定义所借助的主要工具便是它了。
一上来，作者就教我们基础——第一章：基础。
虽说基础，却是令人耳目一新的基础。
他不讲编程的基本数据类型一般有哪些，也不讲基本的流程控制结构有什么。反而是通过一种分类的思想，介绍了编程中常常碰到的一些概念。
有些概念在中文版中实在难以区分，结合英文原版理解会好一些。
比如一开始介绍的，Entity、Species和Genus，后俩我完全不记得中文版是怎么翻译的了，印象中是很容易混淆的。
实际上，上面三个词，分别对应的是实体、种和属（我个人的翻译），其中种要比属概念小一些。
实体又分为抽象实体和具体实体，抽象实体一般是永恒不变的，具体实体则是存在于时空中的独立的事物（但未必一定是物理存在的）。
属性（Attribute）是具体实体和抽象实体的一种关联，一般用于描述具体实体的特性、度量等。可以说，属性让实体变得有血有肉。
标识（Identity）用于区分不同的个体，或者说指示某一个体。即使具体实体的属性发生变化，或者所处的时空发生变化，都不影响其拥有一致的“标识”。换句话说也就是“身份”。
快照（Snapshot）是具体实体在某时某刻的全部属性的集合。
作者举了一些现实的例子，比如“蓝色”、“13”是抽象实体，“苏格拉底”和“美国”是具体实体，“苏格拉底眼睛的颜色”和“美国州的数量”则是属性。
抽象种，描述本质相同的抽象实体的共同特性。例如“人类”，“美国的州”都是抽象种。
函数是关联一个或多个抽象实体的规则，这些实体分别是形参（Argument）和结果（Result）。
抽象属描述具有部分相似的不同种。例如“数字”和“运算符”。
具体属描述具有部分相似的不同的具体种，例如哺乳动物和禽类动物。
一个实体只属于一个种，决定了实体的产生和存在方式。一个实体可以属于多个属，分别描述了一些实体的特性。
讲了这么多，和编程有什么关系呢？
简而言之，对象（Object）和值（Value）就是实体，类型（Type）就是种，概念（Concept）就是属。
那么什么是值？数据（Dataum）和解释（Interpretation）在一起，就是值。
什么是数据不必多说，计算机里面的一部分0和1就是数据。
解释也好理解，同样一个1，可能是一个整数，也可能是一个小数。所以我们需要知道数据如何被解释，也就是数据对应的实体是什么。
对应于实体的数据，可以称为数据表示（Representation）。
除了值，还有值类型（Value Type），表示种和一系列数据的对应关系。
当数据表示一个抽象实体时，数据是良构（Well-Formed）的。例如，32位的二进制序列被解释成补码整数时是良构的，而NaN在解释为IEE 754浮点数时则是非良构（Ill-Formed）的。
同一值类型的两个值，当表示同一个抽象实体时，称之为相等的；当其对应的数据是完全一致的序列时，则称为表示相等的。
举个例子，下面两个分数f1和f2，应被视作相等而非表示相等。所以一般来说，我们应该为它写一个等号运算符重载。
struct 分数 {
int 分子;
int 分母;
};
分数 f1 = {1, 2};
分数 f2 = {2, 4};
对象是内存中用于表示具体实体的值，对象的状态是可变的。对象虽然也有值，但它的值可能在内存中不连续。
对象类型是描述该类型的对象的状态的一种值类型。
……
好啦，摘抄（翻译）了这么多，大概能够体会出作者的良苦用心了吧！作者对编程中涉及的各个与数据、类型等相关的概念，全部进行了非常细化的分类抽象，看起来虽然复杂，但理清楚之后，实在对写出具有良好正确性的程序大有裨益！
可见，学好哲学对编程多么有帮助！ 下面我们再接触一下贯穿全书的核心概念——“概念”！
概念（Concept）即一系列要求（Requirement）。C++20中的概念其实是由一系列约束（Constraint）构成的。其中思想可以说是一脉相承。
本书中的概念，需要一些与类型相关的概念定义：
类型属性：一个类型到一个值的映射，用于描述类型的一些特性。例如sizeof(T)，映射类型T到其所占内存空间大小的值。
类型函数：一个类型到另一个相关类型的映射。例如std::remove_pointer_t<T>映射某个指针类型T到其对应的原始类型，Arity(F)映射函数类型F到其参数个数。
类型构造器：通过已有的一个或多个类型创造一个新类型。例如std::add_pointer_t<T>可以通过类型T创造其指针类型。
哇，对象有构造器，类型还有构造器，是不是有一种Haskell的感觉。其实TypeScript也有类似的做法。
总之，这些泛型、模板做得相对高级的编程语言，都会有针对类型的计算，而不仅仅是传统编程中对对象或者值的计算。
这是一个一元函数的概念的例子。把上面形式化描述，用自然语言翻译一下就是：
一元函数(F)定义为：
函数(F)即 F也是函数概念，- 且
Arity(F) = 1，即参数个数（元）为1，- 且 定义
Domain类型函数为符合一元函数概念的类型到符合常规概念的类型的映射，
其实现为F -> InputType(F, 0)，即将函数映射到其第一个参数的类型。
有了Concept的定义，作者就开始借助这些约束谓词、类型运算等进行算法和数据结构的设计了。比如：
template<typename Op>
requires(BinaryOperation(Op))
Domain(Op) square(const Domain(Op)& x, Op op)
{
return op(x, x);
}
这不是标准C++的写法，而是书中定义的变种C++的写法。
很好理解，square函数接受两个参数，第一个参数是二元运算Op的定义域类型的一个值，第二个参数是一个二元运算Op类型的函数。它返回一个二元运算Op的定义域类型的值。
具体实现就不必多说了。
很显然，这样的定义十分严谨，保证不会有不符合预期的参数传入。
如果是使用当下C++的模板来写这样一个程序，还是颇为费劲的，一般来说大家都不会去考虑这些约束，直接写成这样：
template <typename T, typename Op>
T square(const T& x, Op op)
{
return op(x, x);
}
很显然，如果我们随意传一些参数，错误信息会深入模板内部实现，比较简单直接：
#include <concepts>
#include <functional>
#include <iostream>
#include <string>
int sum(int a, int b) { return a + b; }
int bad() { return 0; }
template <typename T, typename Op>
T square(const T& x, Op op) {
return op(x, x);
}
int main() {
int x = 3;
// std::cout << square(3, bad); // <--- error
std::cout << square(x, sum);
}
<source>: In instantiation of 'T square(const T&, Op) [with T = int; Op = int (*)()]':
<source>:16:29: required from here
<source>:11:12: error: too many arguments to function
11 | return op(x, x);
| ~~^~~~~~
对于我们来说，square可能是个库函数，报错信息出在库函数内部，让人摸不着头脑，并不友好。
我们来试试C++20的Concept吧！
#include <concepts>
#include <functional>
#include <iostream>
template <class F>
concept BinaryOperation = requires(F&& f) {
std::invoke(std::forward<F>(f), 0, 0);
};
template <BinaryOperation F>
struct _Domain;
template <class T>
struct _Domain<T(*)(T, T)> {
using type = T;
};
template <class F>
using Domain = _Domain<F>::type;
int sum(int a, int b) { return a + b; }
int bad() { return 0; }
template <BinaryOperation Op>
Domain<Op> square(const Domain<Op>& x, Op op) {
return op(x, x);
}
int main() {
int x = 3;
// std::cout << square(3, bad); // <--- error
std::cout << square(x, sum);
}
<source>: In function 'int main()':
<source>:32:29: error: no matching function for call to 'square(int, int (&)())'
32 | std::cout << square(3, bad);
| ^
<source>:26:12: note: candidate: 'template<class Op> requires BinaryOperation<Op> Domain<Op> square(Domain<Op>&, Op)'
26 | Domain<Op> square(const Domain<Op>& x, Op op) {
| ^~~~~~
<source>:26:12: note: template argument deduction/substitution failed:
<source>: In substitution of 'template<class F> using Domain = typename _Domain::type [with F = int (*)()]':
<source>:26:12: required by substitution of 'template<class Op> requires BinaryOperation<Op> Domain<Op> square(Domain<Op>&, Op) [with Op = int (*)()]'
<source>:32:29: required from here
<source>:19:7: error: template constraint failure for 'template<class F> requires BinaryOperation<F> struct _Domain'
19 | using Domain = _Domain<F>::type;
| ^~~~~~
<source>:19:7: note: constraints not satisfied
<source>:6:9: required for the satisfaction of 'BinaryOperation<F>' [with F = int (*)()]
<source>:6:27: in requirements with 'F&& f' [with F = int (*)()]
<source>:7:14: note: the required expression 'std::invoke(forward<F>(f), 0, 0)' is invalid
7 | std::invoke(std::forward<F>(f), 0, 0);
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
尽管错误变得复杂，但从中可以清楚地看到，错误原因是约束条件没有满足。
比起刚才直接说square内部的函数调用传参过多，现在应用了Concept的程序会在我们使用square时告诉我们没有匹配到函数，这更容易帮助我们定位错误。毕竟square内部本没有错。
另外当函数调用层次变深、模板参数增多之后，就会知道有Concept在最外层帮我们阻挡是多么幸福！
啊哈！这本十年前的书的思想，终于可以被今天的C++舒服地实践了！
（以前当然也可以写晦涩的模板来做约束，只是报错信息更不会友好…）
以上就是基础——基础基本上涵盖了分类思想，对类型运算做了一些定义，并引入Concept概念。
夹带一点私货，我感觉一般意义上的值是抽象实体、对象是具体实体，值类型是抽象种，引用类型是具体种，概念是抽象属，接口是具体属。
再往后，本书涉及的算法和数据结构也是层层递进，从最简单的基本变换、运算做起，到线性序、顺序代数结构、迭代器、坐标结构、可变后继的坐标结构、复制重整、分区和合并、符合对象等等。每一次算法或者数据结构的定义，都伴随着严密周到的概念约束的定义。可以说几乎有些形式化验证的意味了。
如果你想要对算法和数据结构有一个全新的认识，尤其是想了解C++ STL的设计理念的话，一定不要错过这本书！