CS 106L

本篇文章是我学习CS 106L课程的笔记记录，但本文中大部分内容来自于学习过程中查阅的各种blog以及StackOverflow和cpp的标准文档，作为个人日后查询、补充和深入学习的手册使用。此外，我将2019秋季Stanford的CS 106L作业发布在我的Github仓库，按照课程要求，设置为私人仓库。

stream

stringstream

以下内容来自官方文档：

Stream class to operate on strings.

Objects of this class use a string buffer that contains a sequence of characters. This sequence of characters can be accessed directly as a string object, using member str.

Characters can be inserted and/or extracted from the stream using any operation allowed on both input and output streams.

stream buffer: “A stream buffer is an object in charge of performing the reading and writing operations of the stream object it is associated with: the stream delegates all such operations to its associated stream buffer object, which is an intermediary between the stream and its controlled input and output sequences.”

All stream objects, no matter whether buffered or unbuffered, have an associated stream buffer: Some stream buffer types may then be set to either use an intermediate buffer or not.

stringstream类继承自几个ios基础类：

stringbuf继承自streambuf:

read & write

该类在实际使用中，常常用于分割字符（按空格）。它将string存放到一个string buffer（继承自streambuf）中：

Internally, its iostream base constructor is passed a pointer to a stringbuf object constructed with str and which as arguments.

我们可以通过参数stringstream::ate指定指针位置在末端；如果我们使用的是istringstream，那么可以使用stringstream::bin的方式以二进制读取。

每当我们使用stringstream object向该string buffer中读入数据时，指针会不断向后做相应移动，就像这样：

我们还可以使用.str()方法将存放于string buffer中的内容读取成字符串。

about “»”

我们可以指定类型，之后使用>>操作符将内容读入指定类型的变量中。在cpp官方文档页面上，对这一操作进行了详细的描述，该运算符被多次重载用以接受以下三种参数：

• arithmetic types
• stream buffers
• manipulators

具体的操作可以参见上边的链接，总之就是要借助于继承自istream的sentry类来辅助处理输入流（接受一个stream object parameter），它首先会检测当前internal error flags的状态，如果为good，则继续进行，否则不会对流做任何操作，这一点需要注意。

在运算过程中，程序通过设定ios_base::iostate的值来告诉目前stream的情况–还提供了相应的函数帮助我们进行判断，这几个常量被称为internal error state flags，具体见下表:

我们可以通过调用方法ios::rdstate() const来获取当前internal error state flags的值，或者使用basic_ios::setstate()来修改当前标志位的值。需要注意的是，已经设置了的bitflag是不会自动清除的(sticky!)，需要通过调用basic_ios::clear(iostate state = goodbit)来替换当前状态。

需要注意的是，End-Of-File并不是什么存在于文件末尾的字符，EOF是定义于标准库内的一个宏(macro):

#define EOF (-1)

当文件或者字符串被读取到末尾时，读取函数会返回-1，所以我们也说eof reached.当文件（字符串）末尾到达后，程序设置eofbit，但是需要注意此时failbit与badbit也可能同时被设置.

“Reaching the End-of-File sets the eofbit. But note that operations that reach the End-of-File may also set the failbit if this makes them fail (thus setting both eofbit and failbit).”

那么问题来了，>>会在什么时候设置这几个bitflag呢？官方文档也给出了详细说明（啥都没发生就是goodbit）:

当内置错误标志为fail时，我们也可以利用cpp库的从istream object&到bool的隐式转换ss >> ch作为!ss.fail()的替代，之后的getline()函数也可以利用null pointer->bool的转换:

在本课的stringToInteger函数中，我们见到如下使用方式：

int stringToInteger(const string& str) {
    istringstream iss(str);
    int result;
    iss >> result;
    cout << "result: " << result << endl;
    if (iss.fail())
        throw domain_error("error1");
    char remain;
    iss >> remain;
    cout << "remain: " << remain << endl;
    if (!iss.fail())
        throw domain_error("error2");
    return result;
}

// case 1:
// result: 5, remain: l
// error2
stringToInetger("5lol");
// case 2:
// result: 0
// error1
stringToInteger("lol");

为什么会出现如上的情况？这要考虑到>>第一种重载模式，即用来读取算术类型的内置操作：

“Extracts and parses characters sequentially from the stream to interpret them as the representation of a value of the proper type, which is stored as the value of val. Internally, the function accesses the input sequence by first constructing a sentry object (with noskipws set to false). Then (if good), it calls num_get::get (using the stream’s selected locale) to perform both the extraction and the parsing operations, adjusting the stream’s internal state flags accordingly. Finally, it destroys the sentry object before returning.”

注意到此时在内部是使用了num_get::get方法对数字进行读取的，如果成功读取，把结果存储在参数val中，并利用此函数更新internal error flags(利用传递给get方法的ios_base::iostate& err参数)：

• “The function stops reading characters from the sequence as soon as one character cannot be part of a valid numerical expression (or end is reached). The next character in the sequence is pointed by the iterator returned by the function.”

• “Return value: The next character in the sequence right after where the extraction operation ended.”

• 

当尝试使用int type读入字符串"5lol"时，首先num_get::get方法读取数字5，由于下一个char不是part of valid numerical expression，所以他立即停止读取，此时val的数值为5. 指针指向5的下一个字符l.

当尝试使用int type读入字符串"lol"时，首先num_get::get方法读取字符l，发现 The sequence did not match the expected format，所以他立即停止读取，此时val的数值为0. 指针仍然指向头部，并设置了一个failbit，于是当我们返回到>>的处理过程中时，就会显示fail()了，这也与>>产生failbit的条件吻合，因为此时相当于没有新的字符被成功提取，同时sb此时也是一个null pointer.(因为我们用的是int type处理)。并且result的输出值为0，这也是num_get::get方法中val被存储的值。

如果我们把第二次读取的类型换成double，并尝试读入字符串“5.2”时，不会出现任何问题，因为在第一次读取5之后，序列中余下的.2被程序理解为0.2，也是我们第二次读取输出的结果。

white space separating？

为什么使用stringstream之后istream >> string读取字符串能够自动以空白字符作为分割？

这是因为string类本身也对extraction operator进行了重载：

istream& operator>> (istream& is, string& str);

按照StackOverflow的说法，该函数的实现类似于C中的scanf %s，他会持续读取直到遇到空白字符（包括空格、tab等）下一次从空白字符开始读取（但是默认会skipws）。在官方文档中，我们找到了依据：

Notice that the istream extraction operations use whitespaces as separators; Therefore, this operation will only extract what can be considered a word from the stream. To extract entire lines of text, see the string overload of global function getline.

也就是说如果我们使用>>将数据读入字符串，那么他会尝试着一个单词一个单词地读取。该过程的实现也是借助于一个由指针sb指向的streambuf object，每次我们都在向该streambuf写入数据，在向streambuf写入完毕之后，将streambuf object中的内容写给string对象。所有的stream对象，都有一个与之关联的streambuf object.

Again–About Whitespaces!

下边来看这样两个例子：

1. string a = " 12 3";
   stringstream iss(a);
   char b, c;
   iss >> std::noskipws >> b >> c;
   cout << "b: " << b << " c: " << c << endl;
   // result: b:  c: 1
   

   string a = " 12 3";
   stringstream iss(a);
   char b, c;
   iss >> b >> c;
   cout << "b: " << b << " c: " << c << endl;
   // result: b:1  c: 2
   

2. string a = " 12 3";
   stringstream iss(a);
   string b, c;
   iss >> std::noskipws >> b >> c;
   cout << "b: " << b << " c: " << c << endl;
   // result: b:  c: 
   

   string a = " 12 3";
   stringstream iss(a);
   string b, c;
   iss >> b >> c;
   cout << "b: " << b << " c: " << c << endl;
   // result: b: 12 c: 3
   

这两个例子中唯一的区别就是第一个我们提供了char类型，而第二个是string类型。首先我们不去关注代码中的noskipws，看第二个例子，即string的那一个：根据上一节的描述，当istream >> string遇到了空白字符时，他会停止读取，而恰好，在字符串a的最前边存在一个空白字符，所以我们想它应该会直接在开头处停止，不会读取到任何东西，所以最后返回的是空字符串。

但是我们发现如果尝试将代码中的std::noskipws去掉，那么返回的结果会与之前不同，这又是为什么呢？

首先我们需要了解运算符>>重载的第三种类型：manipulators。

注意到skipws/noskipws这种类型，当skipws被设置时，stream默认会忽视所有的空白字符，文档中提到：

“For standard streams, the skipws flag is set on initialization.”

也就是说，在默认情况下初始化的结果为设置了skipws，所以所有空白字符都会被读取之后跳过，直到我们又发现了一个非空白字符。如此一来，上边例子的结果就好理解了。需要注意的是，在cpp中，对于所有的formatted input（即可以格式化成我们需要的类型的，比如C中的prinf, scanf，cpp中使用>>操作的），默认都是noskipws=false，也就是说会跳过空白字符；而对于所有的unformatted input（比如getchar(char), getline(string)）均设置为noskipws=true。

关于格式化输入与非格式化输入，我是这么理解的，格式化输入意味着我们可以把输入的数据变成我们想要的类型，比如当我们使用>>操作符时，我们可以读入整型，也可以读入一个字符串；但是非格式化输入只能读入rawText type，好比geline(string)我们输入了一个字符串那么接受类型就是一个字符串.

同时，skipws与noskipws两者是sticky的，也就是说我们只有重新设置，才能变回原来的状态。如果想要每一步都可以设置是否保留空白字符，我们可以使用std::ws，提取空白字符，直到遇到非空白字符。

设置skipws等的步骤是在为输入序列创建sentry对象时进行的.

除了上述提到的skipws这种manipulator之外，常见的可以用于pad output的还有：left/right/internal, setw, setfill等：

这几个manipulator在内部调用了内置的一些方法，比如setfill是调用了basic::ios::fill(char_type)，left是设置了名为adjustfiled的flag value，setw则和使用width(n)的效果相同，设置了field width–所以该函数指定的是输出序列中允许存在的最少的字符数。

set position

需要注意的是，在streamoff中，n的值可正可负。常见的使用方法如下：

fpos = oss.tellp() + streamoff(3);
oss.seekp(pos);
// or
oss.seekp(streamoff(1), stringstream::cur);

cin & cout

由于cin实际上是一种istream object，有些特性上边一节已经总结的差不多了…这里只总结两点：

1. 为什么明明输入流默认设置skipws，但是我们输入一个\n时，console内仍然会打印出新的一行？

这是因为控制台内的打印是由consle software控制的，与cin没有任何关系。

2. cin is tied to the standard output stream cout (see ios::tie), which indicates that cout’s buffer is flushed (see ostream::flush) before each i/o operation performed on cin.

The tied stream is an output stream object which is flushed before each i/o operation in this stream object.

我们常用的std::endl就是换行+刷新输出缓冲区，所以如果我们仅仅使用cout而不添加endl，字符会首先存到output buffer中，只有当output buffer满了或者程序终止时，才会调用flush方法。

那么问题来了，std::flush是如何工作的？这里给出了较为详细的解答。

言简意赅地说，ostream::flush()会在内部调用streambuf::pubsync()方法，对流缓冲区进行操作；流缓冲区的作用是负责“缓冲”字符并把数据发送给外部目的地–这发生在缓冲区已满或者内部数据应当与外部目的地进行同步的时候（比如flush()）。当需要同步时，缓冲区内部的数据立即发送给外部目的地，根据官方文档：

For stream buffer objects that implement intermediate buffers, this function requests all characters to be written to the controlled sequence.

这意味着，如果我们正在尝试把数据输出到控制台上，那么此操作会立即把缓冲区内目前所有的字符输出输出流中，再显示到控制台界面上，这意味着清空了stream buffer。对于文件流效果是一样的，只不过外部目的地换成了文件而已。

所以何时需要进行flush操作呢？当然是我们接下来有可能需要向外部目的地写入数据的时候，因为如果此时缓冲区内还存有先前的数据，那毫无疑问的会造成影响！

3. 如果我们注意在输入过程中internal error flag的变化，则在每次flush之后，以及每次cin读取完数据后，内置错误标志位都会被设置成eof. 因为输入流意识到自己读到了字符串的末尾。需要注意的是，如果在输入过程中，标志位在某一刻被设置成fail，那么此后的所有尝试输入的操作均会失效，这一点我们在前边提到过，必须使用clear()清空状态才可以继续进行。

ignore

函数原型：

istream& ignore (streamsize n = 1, int delim = EOF);

注意到这种特殊的使用方法，可以帮助我们忽略掉当前stream buffer中所有的数据，直到eof：

con.ignore(numeric_limits<streamsize>::max(), ‘\n’);

getline(string)

该函数常被用来读取一整行的数据，或者按照delimiters分割数据；这是一个unformatted input function，根据前几节所属的特点，非格式化输入函数默认设置noskipws，那么当遇到分割字符时，它的处理方法是：

If the delimiter is found, it is extracted and discarded (i.e. it is not stored and the next input operation will begin after it).

同样的，该函数也会对internal error flags进行设置。

在文件读取中，如果我们读到了文件末尾，那么getline会设置一个eofbit，但是此时并不会设置failbit，而在继续的下一次读取中，因为我们没有读取到任何内容，根据failbit的定义，sentry object会置一个failbit，借助这一特点，我们在实际使用中常把读取循环写作如下形式而非while(!input.fail())，进而避免向数据结构中输入最后一次读取的garbage value：

ifstream file(filename);
while(true) {
    string line;
    getline(file, line);
    if (file.fail()) {
        break;
    }
    // process the read data
}

我们可以通过在char*(c-string)后加一个s字母的方式，将其转化为cpp string

type deduction

structure

pair

在cpp中，传统的返回多个值的方法是使用reference parameters，但问题在于除非我们查看函数定义，否则引用参数并不明显。在cpp11中提供了pair或者tuple，我们可以使用他们组合多个返回值：

std::pair<std::string, std::string> f(std::pair<std::string, std::string> p)
{
    return {p.second, p.first}; // list-initialization in return statement
}

tuple

structured binding

在cpp17中，与Python类似，我们可以做unpack（structured binding）：

auto [min, max] = findPriceRange(dist);

如果我们使用结构体作为以上函数的返回值，那么structured binding仍然可以使用。

我们还可以对引用使用structured binding:

void transformToDST(vector<Course>& courses) { 
    for (auto& [code, start, end, instructors] : courses) { 
        start++; 
        end++; 
    }
}

void print_map(std::string_view comment, const std::map<std::string, int>& m)
{
    std::cout << comment;
    for (const auto& [key, value] : m) {
        std::cout << key << " = " << value << "; ";
    }
    std::cout << "\n";
}

Aggregate initialization

随着cpp标准的不断更新，初始化的方式愈发多样化。aggregate initialization是一种list-initilization，在cpp20中也被叫做direct initialization. 他应用于arrays以及class type，比如结构体或者联合，但是在使用时有一些特殊要求，可参见文档。

这里的course是一个结构体

需要注意的是，当使用uniform initialization（目前我将这两者理解为相同的东西……）时，对象会首先尝试使用initilizer list constructor而非普通的构造函数：

另一个使用uniform intialization的例子是我们将要初始化一个std::pair：我们可以选择使用{}语法初始化所有部分，或者初始化一部分：

foo({ {}, {} }); // OK: call default constructor on both parts
foo({ key, {} }); // OK: call defualt constructor on the second part
foo({ key1, key2 }); // OK

下边根据文档说一些比较细节的内容：

当我们尝试使用aggregate initialization的方法初始化结构体等class type时，在cpp11中被做了不允许在存在默认初始化参数的情况下使用的限制，这一限制条件在cpp14中被取消。：

struct A {
  string str;
  int n = 42;
  int m = -1;
};
A{.m=21}  // Initializes str with {}, which calls the default constructor
          // then initializes n with = 42
          // then initializes m with = 21

文档截图中的初始化方案3、4被称为designated initilizers，这种初始化方法要保证所有元素的初始化顺序与定义顺序一样，但是我们可以缺省某个参数：

struct A { int x; int y; int z; };
A a{.y = 2, .x = 1}; // error; designator order does not match declaration order
A b{.x = 1, .z = 2}; // ok, b.y initialized to 0

我们可以使用designated initializers来初始化联合，但是union只允许我们提供一个初始化参数成员：

union u { int a; const char* b; };
u f = { .b = "asdf" };         // OK, active member of the union is b
u g = { .a = 1, .b = "asdf" }; // Error, only one initializer may be provided

详细内容参见官方文档.

STL

vector[i] causes undefined behavior!

• Sequence containers

1. vector
2. deque（双端队列）
3. array
4. list（双向链表）
5. forward_list（单链表）

• Container Adaptors

1. stack
2. queue
3. priority_queue

这类容器之所以叫adaptors，是因为他们底层的结构实际上是由另一种容器构成的，我们也可以通过更换函数声明中的模板参数: stack和queue的底层是一个deque:

• Associative containers

1. map
2. set
3. unordered_map
4. unordered_set
5. multimap/unordered_multimap
6. multiset/unordered_multiset

所谓multimap与multiset，是指的可以存在多个相同的键值（元素）.

需要注意的是，map方法at(i)和[i]的区别：at方法如果没有找到该元素，会抛出一个异常，而如果我们使用[]，那么在没有找到该元素时，会先进行创建。

deque & vector

如图所示的结构使得deque的左右插入要比vector更快，但是对于元素的随机访问和随机删除操作，要比vector慢。

iterator

迭代器是STL的重要方法，我们所使用的range for loop就是使用迭代器在内部工作的。

注意iterator的end指向的是最后一个元素的后一位.

map iterator

map的迭代器比较特殊，它指向一个pair对象，所以我们可以使用a.first和a.second获取键与值：

map<int, int> m;
map<int, int>::iterator i = m.begin();
map<int, int>::iterator end = m.end();
while(i != end) {
    cout << (*i).first << (*i).second << endl;
    ++i;
}

在cpp20之前，如果我们想要查找容器中是否存在某个键，那么需要调用find或者end方法，而在cpp20中，我们只需要调用contains即可。

如果find成功，则iterator指向对应的元素，否则指向end. count方法通过调用find实现，所以find方法的速度更快.

lower_bound & upper_bound

lower_bound接受一个值v，返回一个iterator对象，该对象指向第一个不小于元素v的位置，如果没有找到，则指向end。

upper_bound与lower_bound的工作方式类似，但是其返回的迭代器对象指向第一个大于元素v的位置。

Iterator Types Introduction

共有五种基本的迭代器类型：

上图中的箭头我们可以理解成继承关系。对于所有的迭代器类型，他们都具备以下几种基本操作功能：

• Is copy-constructible, copy-assignable and destructible
• can be advanced using ++
• can be derederenced using *

1. Input Iterators

应用对象：连续+单向输入，下边来分别解释这两个限制条件的意思：

• 连续，表示所应用的数据结构不可以是queue，stack等（不包括deque，因为deque实际效果上是一个优化了前序插入的vector）
• 单向（single-pass），迭代器对应的每个位置只能允许被经过一次，这个限制条件之后会详细解释

input iterators只能作为右值（rvalue）被解引用：

int val = *itr;

这种迭代器的应用场景有之前提到过的find以及count函数等。这种迭代器类型数据是只读的。

2. output iterators

它的应用条件与input iterators相同，但是它只能作为左值（lvalue）被解引用：

*itr = 12;

该迭代器对象的应用场景主要有copy以及output streams等。它是只写的。

3. forward iterators

这种迭代器类型与把前两种类型结合起来的效果类似，不同的是，他可以做multiple pass. 应用场景主要有replace函数以及forward_list中。

4. bidirectional iterators

承接forward iterators，但是可以做--操作：

vector<int>::iterator itr = v.begin();
--itr;

应用场景主要有reverse函数，map, set以及list等。

5. random Access iterators

承接上一种类型，但是支持+=n与-=n操作，同时可以使用offset dereference operator ([])，应用在容器vector, deque, string以及指针上。

Instead of being defined by specific types, each category of iterator is defined by the operations that can be performed on it. This definition means that any type that supports the necessary operations can be used as an iterator – for example, a pointer supports all of the operations required by LegacyRandomAccessIterator, so a pointer can be used anywhere a LegacyRandomAccessIterator is expected.

关于迭代器类型，补充以下一些内容：

除了上述提到的5种基本类型的迭代器，cpp后来新增了一种基本迭代器类型：Contiguous Iterator，这种迭代器类型在randomAccess Iterators的基础上保证了其中的数据在内存必须连续存储。

在cpp20中，根据新的关键字concept以及requires对迭代器类型根据新的系统设计了一套定义，但是基本的类型是相似的；

我们可以简单地将这两个关键字的功能理解为：为模板参数制定一些限制，使得在编译阶段就能够进行evaluation。应用他们的主要优点是可以得到更加清晰地编译器报错。这里不去深究，这篇文章写的较为清楚。

新的迭代器定义基本方法是先使用这两个关键字定义了一种input_or_output_iterator类型，之后扩展的每一种类型均满足这种基本迭代器类型的要求，从定义中可以看到，这种基本类型支持两种操作：解引用+递增操作符：

新定义的迭代器类型除了output_iterator是直接在input_or_output_iterator基础上增加了写入功能之外，其余的迭代器类型均继承自cpp20之前的迭代器类型，比如对于input iterator:

What is single-pass?

什么是single-pass？为什么只能single-pass？cpp标准库中提到：

For input iterators, a == b does not imply ++a == ++b. (Equality does not guarantee the substitution property or referential transparency.) Algorithms on input iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. Value type T is not required to be an Assignable type (23.1). These algorithms can be used with istreams as the source of the input data through the istream_iterator class.

这里对该问题进行了细致的讨论。在讨论input iterators时，常使用istream_iterator作为例子，该迭代器类型从输入流中读取数据，我们可以想到，无论该读取过程是否需要用到stream buffer，读取都是发生在迭代器不断向前推进的时候，而输入流某个位置在被读取之后，我们就不能够再次对流中同一个位置的元素进行操作了，也就是说我们只能用一个迭代器，单向，走一次：

std::istream_iterator is a single-pass input iterator that reads successive objects of type T from the std::basic_istream object for which it was constructed, by calling the appropriate operator>>. The actual read operation is performed when the iterator is incremented, not when it is dereferenced. The first object is read when the iterator is constructed. Dereferencing only returns a copy of the most recently read object.

The default-constructed std::istream_iterator is known as the end-of-stream iterator. When a valid std::istream_iterator reaches the end of the underlying stream, it becomes equal to the end-of-stream iterator. Dereferencing or incrementing it further invokes undefined behavior.

所以在标准文档给出的说明中，++a==++b为什么此时不能够保证成立呢？这里首先我们要明确以下++操作符的作用机理：

Increment/decrement operators

根据官方文档中的解释，前置递增操作符的运算过程与x += 1完全相同，在对元素递增之后，返回一个该元素的引用；而后置递增操作符则是先保存一下元素副本，对该元素本身（引用）进行递增之后，把副本（保存着原值）返回。

在清楚了++操作符的作用机理后，我们把目光转回到iterator上。在表达式++a==++b上，如果我们已经进行了++a的操作，那么根据istream_iterator的特性，已经对流内的数据进行了读取，那么此时iterator b就找不到流内原位上的数据了，换而言之，iterator b失效了！

如果我们读取的是字符，那么需要用到stream buffer，此时使用std::istreambuf_iterator是效率更高的选择，因为他不需要对每一个字符建立一个sentry object，程序在开始时先建立一个sentry object，之后把所有数据放入缓冲区，再使用迭代器进行读取.

所以，在count以及find函数中，我们确实只需要走一次就可以获得我们想要的结果，于是只需要使用一个input iterator即可。对应着output iterator的ostream_iterator也是一样的道理。

Write our own iterator?

在cpp17之前的版本中，如果我们想给自己的类写一个iterator，那么一般的方法是继承std::iterator的类模板，并在类模板中指定所谓的iterator_category：

迭代器标签关联着之前所述的迭代器实体。但是自cpp17起，std::iterator的类模板遭到舍弃，详情参见。所以现在，我们只能手写迭代器，具体可以看这里。

在这里，iterator_traits是一个meta-function，返回的是根据给入参数决定的迭代器的type（通过::iterator_category），也即上图中的各种iterator_tag，这些tags绑定着一些同名迭代器类实体，我们可以利用这些类别构造我们自己的函数，在下方模板一章节的最后一个例子中有提到（来自于Stanford CS 106L Fa2020 lecture）。

iterator – friend class

在作业HashMap中，我们被要求手写一个迭代器类。在这里，我们被要求将hashmap与hashmap_iterator的定义（声明）放到两个头文件中。所以，而迭代器与容器本身的关系要求他们互为友元，也是我们后边提到的mutual friends class，因为此处均为模板类，所以我们使用了Template friends class的方法在各自类中声明其友元。

需要注意的是，我们应当把该类也声明做友元，因为我们可能会获取它的成员们：

friend iterator_of_hashmap<HashMap, !Const>;

iterator – const?

在这里，一个很重要的方法是利用std::conditional_t<>来对迭代器内部的数据类型（是否为const）进行条件选择–这是因为我们要提供iterator与const-iterator两个类。而const_iterator之所以存在，是因为当我们的容器（container）类被置为const时，迭代器不应该被允许修改数据：

当一个类对象为常量对象时，其中所有数据也均为常量类型的数据。而对于常量数据，只能使用指向常量的指针指向他们，或者使用const引用与他们绑定，否则会编译错误。

这就是为什么在代码中我们需要诸如：

using node_pointer = std::conditional_t<Const, const node*, node*>;

iterator – basic requirement

using difference_type = std::ptrdiff_t;
using value_type = std::conditional_t<Const, const _value_type, _value_type>;
using pointer = std::conditional_t<Const, const _value_type*, _value_type*>;
using reference = std::conditional_t<Const, const _value_type&, _value_type&>;
using iterator_category = std::forward_iterator_tag;

我们必须添加这些以满足程序对iterator类设计的基本要求，同时根据iterator_category提供必要的运算符重载，需要注意的是其中前置++与后置++的实现方法（基本是固定套路），参看我的Github repository.

根据Mastering the cpp17 STL这本书的设计，我们还提供了一个conversion operator，允许迭代器从iterator转型到const_iterator：

/** a conversion operator */
operator iterator_of_hashmap<HashMap, true>() const {
    return iterator_of_hashmap<HashMap, true>{_buckets_array, _ptr, curr_bucket};
}

iterator – private member variables

迭代器的内部数据成员一定会有一个指针，指向容器中具体的，每一个数据的位置（注意：也要通过std::consitional_t来选择），其他私有成员根据需要提供，比如在HashMap中我们就需要一个size_t来告诉我们现在内部指针处于第几个bucket中。在设计时，还包含了一个指向容器的数据区的指针，具体可参见后边的Template mutual friends的一节。

我们使用一个private constructor，这是因为除了在该类及其友元类中，别处不允许直接初始化一个迭代器。

Template–Generic Programming

关于模板，这里有一篇很好的文章。

function template

函数模板的基本形式是：

template<typename T>
T getInteger(const string& prompt, const string& reprompt) {
    while (true) {
        cout << prompt; 
        string line; 
        T result; 
        char extra; 
        if (!getline(cin, line))
            throw domain_error(“[shortened]”);
        istringstream iss(line);
        if (iss >> result && !(iss >> extra)) 
            return result; 
        cout << reprompt << endl; 
    }
}

class template

e.g.

template<class T, class Container = std::vector<T>>
class Priority_Q {
  // do something  
};

template parameters & template arguments

函数模板的形参列表可以由几下几种方式构成：

1. non-type template parameter

什么是非类型模板参数？非类型模板参数会在编译阶段被预定义并被替换为常量值作为实参，它可以具备如下类型：

• An integral type
• An enumeration type
• A pointer or reference to a class object
• A pointer or reference to a function
• A pointer or reference to a class member function
• std::nullptr_t
• A floating point type (since cpp20)

对于该类型的参数，我们需要注意以下几点：

1. The top-level cv-qualifiers on the template-parameter are ignored when determining its type

// this const will be ignored
template<const int k>
void foo() {
    // do something
}

2. When the name of a non-type template parameter is used in an expression within the body of the class template, it is an unmodifiable prvalue unless its type was an lvalue reference type, or unless its type is a class type (since cpp20).

template <int N>
void f()
{
    // N is a prvalue, so this is invalid! It will produce a compile error
    N = 42;
}

2. the expression we give to the template as its argument must can be parsed and substitued during compile time (non-constant expressions cannot do this, since they could change during runtime)

因为模板的匹配是在编译的时候完成的，所以实例化模板的时候所使用的参数，也必须要在编译期就能确定。

template <int N>
void f()
{
    // do something
}

int main() {
    int a = 1;
    const int b = 0; // constexpr int b = 0;
    // error
    f<a>();
    // ok
    f<b>();
}

2. type template parameter

这类参数包括使用typename与class(即分别对应了函数模板与类模板的两种type-parameter-key)，在cpp20中还提出了使用constrained type template:

template<typename... Ts> concept C2 = true; // variadic concept
template<C2... T> struct s3;      // constraint-expression is (C2<T> && ...)

3. template template parameter

模板模板参数：

// two type template parameters and one template template parameter:
template<typename K, typename V, template<typename> typename C = my_array>
class Map
{
    C<K> key;
    C<V> value;
};

instantiation（explicit/implicit）

在调用模板函数时，我们可以显式指定对应的模板参数类型（explicit instantiation）,也可以不显式指定模板参数类型（implicit instantiation），让模板函数进行类型推断（Template Argument Deduction），需要注意的是，如果我们省略<>符号，那么overload resolution会查找所有的模板类型重载与非模板类型重载，而不是仅仅查找模板类型重载。

什么是overload resolution?后边有提到.

需要注意的是，如果我们在explicit instantiation之前已经做了模板特化（template specialization），那么此时的实例化是不起作用的。

implicit inference

在模板函数中，我们可能会隐含着一些使用参数的限定条件，比如对于下图所示的函数：

其实隐含着这样一些限定参数使用条件：

这些限定条件意味着如果我们在调用函数时给出了不恰当的参数，那么该模板函数会报出一些非常凌乱的错误…

在cpp20中给出了新的关键字concepts与requires，也就是在之前我们提到过用于重写iterator的两个关键字，他们可以帮助我们在编译阶段就检查出参数错误，将报错的位置从函数主体转移到这两个关键字的位置上：

既然concepts关键字可以方便解决模板编译与运行过程中的报错问题的，那么接下来就针对模板的编译过程进行分析。

Compile a template function call

接下来所述的概念来自于官方文档以及这两篇12博客. 根据作者原文给出的例子:

struct Bar {
    typedef double internalType;  
};

template <typename T> 
typename T::internalType foo(const T& t) { 
    cout << "foo<T>\n"; 
    return 0; 
}

int main() {
    foo(Bar());
    foo(0); // << error!
}

当我们向程序中添加了一个新的非模板函数重载int foo(int i)时，程序便不会报错，为什么呢？我们需要了解函数整个的编译过程。

name lookup

根据官方文档,为了编译一个函数调用，程序首先会进行name lookup，这一步是将程序中出现的名字与引入它的声明联系起来，比如对于如下语句，程序正是通过name lookup的方式来解析这条语句中出现的各个名字：

For example, to compile std::cout « std::endl;, the compiler performs:

• unqualified name lookup for the name std, which finds the declaration of namespace std in the header
• qualified name lookup for the name cout, which finds a variable declaration in the namespace std
• qualified name lookup for the name endl, which finds a function template declaration in the namespace std
• both argument-dependent lookup for the name operator<<, which finds multiple function template declarations in the namespace std, and qualified name lookup for the name std::ostream::operator«, which finds multiple member function declarations in class std::ostream.

std::cout << std::endl;

在进行name lookup时，我们依赖的是scope这个概念，也即名称的声明所在地，scope有很多种类，namespace,function,class,block,enumeration,template parameter都拥有自己的scope.

unqualified name lookup & qualified name lookup

在上边的例子中，编译器首先会对名称std进行unqualified name查找，在头文件<iostream>中找到它；之后再对cout, endl做qualified name的查找，即在命名空间std中进行的查找过程。

qualified name即在作用域解析符::右侧出现的名称，所以他包括：

• class member
• namespace member
• enumerator

同样地，unqualified name即没有在作用域解析符::右侧出现的名称

需要注意的是，如果作用域解析符::左侧没有东西，那么程序会默认在global namespace scope或者由using引入的命名空间中进行查找：

#include <iostream>
int main() {
  struct std{};
  std::cout << "fail\n"; // Error: unqualified lookup for 'std' finds the struct
  ::std::cout << "ok\n"; // OK: ::std finds the namespace std
}

Argument-dependent lookup (ADL)

这种名称查找方式也属于一种unqualified name lookup，叫Koenig lookup，用于查找function-call expressions中的unqualified function names（包括运算符重载时对函数的隐式调用），这种查找方式的存在使得在进行函数调用时，程序不仅仅会查找一般的unqualified name lookup的scope和命名空间，还会查找函数参数们所在的命名空间：

该示例来自于官方文档：

#include <iostream>
int main()
{
    std::cout << "Test\n"; // There is no operator<< in global namespace, but ADL
                           // examines std namespace because the left argument is in
                           // std and finds std::operator<<(std::ostream&, const char*)
    operator<<(std::cout, "Test\n"); // same, using function call notation
 
    // however,
    std::cout << endl; // Error: 'endl' is not declared in this namespace.
                       // This is not a function call to endl(), so ADL does not apply
 
    endl(std::cout); // OK: this is a function call: ADL examines std namespace
                     // because the argument of endl is in std, and finds std::endl
 
    (endl)(std::cout); // Error: 'endl' is not declared in this namespace.
                       // The sub-expression (endl) is not a function call expression
}

Template Argument Deduction

在进行完name lookup这一步之后，程序会进行Template Argument Deduction：

In order to instantiate a function template, every template argument must be known, but not every template argument has to be specified. When possible, the compiler will deduce the missing template arguments from the function arguments. This occurs when a function call is attempted, when an address of a function template is taken, and in some other contexts.

这一机制以及上一节提到的ADL，让我们使用template operator成为可能，因为在使用template operator时，我们无法显式指定所用的模板参数的类型：

#include <iostream>
 
int main() 
{
    std::cout << "Hello, world" << std::endl;
    // operator<< is looked up via ADL as std::operator<<,
    // then deduced to operator<<<char, std::char_traits<char>> both times
    // std::endl is deduced to &std::endl<char, std::char_traits<char>>
}

需要注意的是，对于函数以及函数模板名称，name lookup可以找到多个合理的名称，并交给之后的overload resolution过程处理，但是对于其他的名字，比如变量，类，命名空间等，name lookup只允许找到一个名字的声明以保证正常编译。

Template Argument Substitution

现在，我们已经获取到了所使用的模板参数类型，在这一步我们要将所有出现在原本的模板中的参数T替换为我们推断出的参数类型。

When all template arguments have been specified, deduced or obtained from default template arguments, every use of a template parameter in the function parameter list is replaced with the corresponding template arguments.

需要注意的是如果在替换过程中，出现了错误，比如在先前给出的例子中，我们获得了一个int::interalType的类型，那么此时，我们需要把这一参数类型（一个替换方案）剔除出overload set，这一操作被称为SFINAE–Substitution failure is not an error.

overload resolution

在做完Template Argument Substitution这一步后，如果overload set中已然没有可用的函数，那么编译失败，但存在这样一种情况：即目前有多个candicate function可供选用，那么此时overload resolution便会派上用场。

In order to compile a function call, the compiler must first perform name lookup, which, for functions, may involve argument-dependent lookup, and for function templates may be followed by template argument deduction. If these steps produce more than one candidate function, then overload resolution is performed to select the function that will actually be called.

这是一种针对于function call的通用概念，并非只针对template.

当我们试图在模板函数中应用overload resolution以选择最佳匹配重载函数时，会使用partial ordering of overloaded function templates的方法来选择最佳匹配。什么是最佳匹配重载函数？

Informally “A is more specialized than B” means “A accepts fewer types than B”.

StackOverflow上有一篇很详细的文章描述这一机理。这也是为什么在先前的例子中加入一个匹配的新function，就可以编译成功的原因。

SFINAE

在上一节的template argument substituion中，我们提到了SFINAE的内部作用机理，那么我们要如何写出这样的代码或者说这一机理有什么用处呢？

Why we need SFINAE?

在这篇文章里，其实解释的很清楚。这里是我的一个总结。

• 首先，对于我们自己的函数模板代码，如果其中存在if-else分支，并且我们利用了compile-time-if，那么程序很有可能会在编译阶段报错，因为他会编译if-else两个分支，之后程序发现自己无法reject the invalid code (for this case)：

template <typename T>
std::string str(T t) {
    if (std::is_convertible_v<T, std::string>)
        return t;
    else if (std::is_same_v<T, bool>)
        return t ? "true" : "false";
    else
        return std::to_string(t);
}

而我们要做的，就是让程序在编译阶段把在当前情况下不正确的分支给剔除，从overload set中将其去掉，只编译符合要求的部分，这也对应着SFINAE的定义。

How to leverage SFINAE?

为了解决这个问题，cpp11/14/17/20提出了多种方案：

Tag Dispatching

enable_if

std::enable_if can be used as an additional function argument (not applicable to operator overloads), as a return type (not applicable to constructors and destructors), or as a class template or function template parameter.

这一语法自cpp11提出，但当时的写法是enable_if，在cpp14/17中，提出了enable_if_t.

模板偏特化

也就是说，当B==true时，enable_if具备一个typedef type，即T，否则没有type成员，就会发生我们所说的SFINAE，于是当我们写成如下代码：

template <class T>
typename std::enable_if<std::is_arithmetic<T>::value, T>::type

或者参看文档中的alias–enable_if_t的定义时，如果其不具备成员type但是我们却使用了::type，那么编译就会出错，并使用SFINAE机制处理。在cpp14及以后的版本中，上述代码可被简化为：

template <class T>
typename std::enable_if_t<std::is_arithmetic_v<T>, T> 

enable_if常与type traits一起使用：

type traits在编译阶段用以确定模板特征和属性。在cpp14中也提出了类似于is_arithmetic_v的形式（原本的value当T为arithmetic type是返回true，反之false）

借助于enable_if_t，我们可以将本节最初的代码更改为：

template <typename T>
enable_if_t<is_convertible_v<T, string>, string> strOld(T t) {
    return t;
}

template <typename T>
enable_if_t<!is_convertible_v<T, string>, string> strOld(T t) {
    return to_string(t);
}

关于enable_if的缺点，StackOverflow上的一篇文章进行了探讨。

需要注意的是，enable_if这里直接充当了函数的返回值类型，因为它本身就返回一个type

enable_if除了可以放在返回值的位置上以外，还可以直接使用在模板参数、函数参数中，或者在模板偏特化中出现，它的使用方式十分灵活，具体可以看官方文档：

// 2. the second template argument is only valid if T is an integral type:
template < class T,
           class = typename std::enable_if<std::is_integral<T>::value>::type>
bool is_even (T i) {return !bool(i%2);}

// the partial specialization of A is enabled via a template parameter
template<class T, class Enable = void>
class A {}; // primary template
 
template<class T>
class A<T, typename std::enable_if<std::is_floating_point<T>::value>::type> {
}; // specialization for floating point types

在使用enable_if或者enable_if_t时，我们也可以省略模板参数中的T，因为T具备默认值void。

Notes

需要注意的是，这里提到的是only differ in default template arguments，如果两个模板的default template argument一样但是template parameters不一样，那么不会发生编译错误.

所以如上图所示，对于第一个例子，由于两者只在默认模板参数上有所不同，进而报错。但是第二个例子两者的模板参数是不一样的（虽然两者的默认模板参数都被设置成了true，但仍然不会报错）

if constexpr

在cpp17中，我们可以将if conxtexpr statement使用在模板中，起到与enable_if_t相同的作用：

template <typename T>
auto get_value(T t) {
    if constexpr (std::is_pointer_v<T>)
        return *t; // deduces return type to int for T = int*
    else
        return t;  // deduces return type to int for T = int
}

concepts-requires

终于，我们来到了concepts。

// concept:
template<typename T>
concept Hashable = requires(T a) {
    { std::hash<T>{}(a) } -> std::convertible_to<std::size_t>;
};

在这里，我们定义一个concept，将一个requires-expression赋值给它。requires关键字有很多种写法：

• requires clauses

template<typename T>
void f(T&&) requires Eq<T>; // can appear as the last element of a function declarator
 
template<typename T> requires Addable<T> // or right after a template parameter list
T add(T a, T b) { return a + b; }

• requires expressions

template<typename T>
concept Addable = requires (T x) { x + x; }; // requires-expression

• simple requirements

template<typename T>
concept Addable =
requires (T a, T b) {
    a + b; // "the expression a+b is a valid expression that will compile"
};

因为所有以关键字requires开头的requirements都会被解释成nested requirement，所以simple requirements不会以requires开头

• Type requirements

template<typename T> using Ref = T&;
template<typename T> concept C =
requires {
    typename T::inner; // required nested member name
    typename S<T>;     // required class template specialization
    typename Ref<T>;   // required alias template substitution
};

• Compound requirements

• Nested requirements

Abbreviated function template

自cpp20始，提出了Abbreviated function template的做法，即使用placeholder types(auto, concept auto)出现在函数声明或者函数模板声明中：

void f1(auto); // same as template<class T> void f(T)
void f2(C1 auto); // same as template<C1 T> void f2(T), if C1 is a concept
void f3(C2 auto...); // same as template<C2... Ts> void f3(Ts...), if C2 is a concept
void f4(const C3 auto*, C4 auto&); // same as template<C3 T, C4 U> void f4(const T*, U&);
template <class T, C U>
void g(T x, U y, C auto z); // same as template<class T, C U, C W> void g(T x, U y, W z);

于是对于原博客中给出的例子：

// requires:
template <typename T>
requires std::is_floating_point_v<T>
constexpr bool close_enough20(T a, T b) {
   return absolute(a - b) < precision_threshold<T>;
}
constexpr bool close_enough20(auto a, auto b) {
   return a == b;
}

根据官方文档，我们利用constrained auto将其改写为：

constexpr bool close_enough20(std::floating_point auto a,
                              std::floating_point auto b) {
   return absolute(a - b) < precision_threshold<std::common_type_t<decltype(a), decltype(b)>>;
}
constexpr bool close_enough20(std::integral auto a, std::integral auto b) {
   return a == b;
}

这里有一篇文章作了较为详细的介绍。

Template friends

这是一节单独列出来的主题。分为两个部分，Template class friends和Template function friends，在第二种中尤其讨论Template friend operator.

Template class friends

在做hashmap作业时，我们需要将自己实现的iterator class作为友元声明到container也即hashmap类中，我们有两种方法来实现这一声明操作：

template<typename T>
class foo{
    template<typename U>
    friend class foo_1;
};

Template parameters cannot shadow each other.

如此一来，不论T被实例化为什么类型，任何类型的foo_1类都是foo的友元。需要注意的是类模板的声明方式，我们不可以写出这样的语法：

template<typename U>
friend class foo_1<U>;

或者我们也可以这样声明，这也是hashmap中我们可以做的（因为只需要这么做就足够了）：

template<typename T>
class foo{
    friend class foo_1<T>;
};

这种声明方式中，模板参数推断只发生在一开始的类模板部分，而在类内部仅仅对foo_1按照推断出来的类型T做了一次实例化。如若foo被实例化为foo<int>，那么此时也便只有foo_1<int>有资格成为它的友元了。

我们可以在友元处做模板特化（Template specialization），需要注意的是，模板友元（Template friends）不允许我们做模板偏特化，但是我们可以做模板全特化：

template<class T> class A {}; // primary
template<class T> class A<T*> {}; // partial,因为此时T*仍然带有泛型T
template<> class A<int> {}; // full, int已经脱离T了，被“完全特化”了，所以模板参数中也不需要填东西
class X {
    template<class T> friend class A<T*>; // error!
    friend class A<int>; // OK
};

Template function friends

我们常常需要将重载的操作符声明为友元（见下方Object-Oriented Programming部分详述），根据这篇文章，我们有三种方式实现这一声明操作：

The Extrovert

与模板友元类类似，我们可以这样声明：

template <typename T>
class Test {
   template <typename U>      // all instantiations of this template are my friends
   friend std::ostream& operator<<( std::ostream&, const Test<U>& );
};
template <typename T>
std::ostream& operator<<( std::ostream& o, const Test<T>& ) {
   // Can access all Test<int>, Test<double>... regardless of what T is
}

按照友元声明习惯，将声明放在类内部，定义放在类外部，这种方法类似模板友元类声明的第一种方法，不再详述。

The Introverts

我们也可以把友元函数的声明+定义全部放在类内，这允许我们进行如下两种声明模式：

这两种声明不允许我们将函数定义放在类外，否则编译器无法找到模板函数的定义

template <typename T>
class Test {
   friend std::ostream& operator<<( std::ostream& o, const Test& t ) {
      // can access the enclosing Test. If T is int, it cannot access Test<double>
   }
};

这种方法类似模板友元类声明的第二种模式，不同的是在这里我们必须给函数在类内提供一个定义。

或者，我们也可以做得更加麻烦一些，在官方文档中也提过这种方法：

or the function template has to be declared as a template before the class body, in which case the friend declaration within Foo<T> can refer to the full specialization of operator<< for its T:

// Forward declare both templates:
template <typename T> class Test;
template <typename T> std::ostream& operator<<( std::ostream&, const Test<T>& );

// Declare the actual templates:
template <typename T>
class Test {
   // refers to a full specialization for this particular T 
    friend std::ostream& operator<< <> (std::ostream&, const Test&);
    // note: this relies on template argument deduction in declarations
    // can also specify the template argument with operator<< <T>":
    // friend std::ostream& operator<< <T>( std::ostream&, const Test<T>& );
};
// Implement the operator
template <typename T>
std::ostream& operator<<( std::ostream& o, const Test<T>& t ) {
   // Can only access Test<T> for the same T as is instantiating, that is:
   // if T is int, this template cannot access Test<double>, Test<char> ...
}

Template meta-programming

本部分内容来自于Stanford CS 106L Fa2020的guest lecture，以及cpp Template Tutorial和cpp官方文档。

在学习了一系列基本关于模板的基础知识以及先前关于iterator的内容后，对模板元编程（Template meta-pragramming）做一下浅显的了解和认识。在这一章节，也会对先前没有提到的模板特化（Template Specialization）做一些介绍。

所以什么是元编程？这里直接引用提到的文章中的一段话：

元（meta）无论在中文还是英文里，都是个很“抽象（abstract）”的词。因为它的本意就是“抽象”。元编程，也可以说就是“编程的抽象”。用更好理解的说法，元编程意味着你撰写一段程序A，程序A会运行后生成另外一个程序B，程序B才是真正实现功能的程序。那么这个时候程序A可以称作程序B的元程序，撰写程序A的过程，就称之为“元编程”。

我们的目的，是找出程序之间的相似性，进行“元编程”。而在cpp中，元编程的手段，可以是宏，也可以是模板。

Template Specialization

我们应当区分模板特化与模板实例化的区别，其实实例化（template instantiation也可以被叫做模板实例化的特例（instantiated/generated specialization））模板特化又分为Explicit/full specialization与Partial template specialization(模板偏特化)两种。对于模板特化，首先我们要注意以下几点规则：

1. 在定义模板特例之前应当有模板通例（generic template/primary template）在先
2. 模板偏特化（部分特化）（partial template specialization）只适用于class template和variable template。
3. 模板特化的匹配规则遵循以下顺序：

• If only one specialization matches the template arguments, that specialization is used

• If more than one specialization matches, partial order rules are used to determine which specialization is more specialized. The most specialized specialization is used, if it is unique (if it is not unique, the program cannot be compiled)

• If no specializations match, the primary template is used

这也是我们在先前提到过的Partial ordering方法，只不过在模板特化这里被使用并明确了。简而言之，从特例到通例，从more specializaed到less specialized。

Template Specialization Examples

// primary template
template <typename T> class TypeToID
{
public:
    static int const ID = -1;
};
// specialization template
template <> class TypeToID<uint8_t>
{
public:
    static int const ID = 0;
};

需要注意的是，在模板特化时，如果我们特化的类型不需要依赖模板参数T，那我们就不需要也不能在specialiazed template中的<>位置写任何东西，因为他的位置已经被其后的int占领了：

// use float specialization
template <> class TypeToID<float>
{
  static int const ID = 0xF10A7;
};
// use void* specialization
template <> class TypeToID<void*>
{
  static int const ID = 0x401d;
};

但有些时候我们不得不给入一个模板参数T来进行模板特化，比如我们要特化所有指针类型：

template <typename T>                    // 嗯，需要一个T
class TypeToID<T*>                        // 我要对所有的指针类型特化，所以这里就写T*
{
public:
    typedef T         SameAsT;
    static int const ID = 0x80000000;    // 用最高位表示它是一个指针
};

在进行模板特化时，我们需要注意的一点是，特化的模板可以把我们提供的类型中的const或者*给去掉，也就是说，当我们给如下的模板定义分别提供float*与const int时，其中对应的T分别变成了float与int:

// float* -> T:float
template <typename T>
class RemovePointer<T*> {
public:
    typedef T Result;
};

// const int -> T:int
template<typename T>
class RemovePointer<const T> {
public:
    using type = T;
};

在继续进行我们的主题之前，我们先来对模板中的名称查找问题进行解决，这会帮助我们理解之后的例子。

Name Resolution

在一开始给到的文章中，提到了Name Resolution这一概念：

这里我们需要注意的是，模板中的名称可以被分为两个大类：依赖性名称与非依赖性名称。什么是依赖性名称？

A dependent name is a name that depends on the type or the value of a template parameter. For example：

template<class T> class U : A<T>
{
  typename T::B x;
  void f(A<T>& y)
  {
    *y++;
  }
}; 

在这里，A<T>，T::B，y都是依赖性名称。

- 除此之外，如果成员访问运算符(., ->)依赖于模板参数，则p->x中的x也是依赖性名称；

- this->x在模板定义中出现时，也是依赖性名称;

- f(A<T>)中的f也是依赖性名称.

而他们被程序进行name lookup的时机也不相同：Non-dependent names会被程序在模板定义的时候查找，可是dependent names只有当模板被实例化时才被查找到，因为他们都是与模板参数有关的，依赖于具体的模板参数。所以，我们在模板这一节开始时提到的name lookup过程会在模板定义和实例化时各做一次，分别处理Non-dependent names与dependent names。这一机制被称为Two phase name lookup(两阶段查找)。

而正是基于这样的原因，在如下的例子中：

#include <iostream>
using namespace std;

void f(double) { cout << "Function f(double)" << endl; }

template <class A> struct container{ // point of definition of container
   void member1(){
      // This call is not template dependent, 
      // because it does not make any use of a template parameter.
      // The name is resolved at the point of definition, so f(int) is not visible.
      f(1); 
   }
   void member2(A arg);
};

void f(int) { cout << "Function f(int)" << endl; }

void h(double) { cout << "Function h(double)" << endl; }

template <class A> void container<A>::member2(A arg){ 
   // This call is template dependent, so qualified name lookup only finds
   // names visible at the point of instantiation.
   ::h(arg);  
}

template struct container<int>; // point of instantiation of container<int>

void h(int) { cout << "Function h(int)" << endl; }

int main(void){   
   container<int> test;   
   test.member1();
   test.member2(10);
   return 0;
}

在这个例子中，我们为f和h分别提供了两种类型的重载，并在第26行对模板进行实例化。由于文件编译顺序自上而下，所以在模板定义阶段发生的第一阶段名称查找只能找到在模板定义上方的f或者h，实例化也同样。如果更改这两个函数定义的位置，那么程序最终会输出不同的结果。

我们得到了如下的结果：

Function f(double)
Function h(double)

正是因为编译器分别在模板定义和模板实例化时完成了名称查找。在之后进行名称解析时，根本不会用到后边定义的东西。

而name lookup中提到，名称查找又分为qualified name look-up以及unqualified name look-up。这样一来，在模板名称定义的概念里，我们有如下四种组合：

基于这种特性，对于一个多文件的项目，我们必须把模板类或者模板函数的声明与实现放在一个文件中，根据官方文档：

Because templates are compiled when required, this forces a restriction for multi-file projects: the implementation (definition) of a template class or function must be in the same file as its declaration. That means that we cannot separate the interface in a separate header file, and that we must include both interface and implementation in any file that uses the templates.

Why use typename?

正因为这一Two phase name lookup的特性，typename关键字在模板定义内派上了用场。

template <typename T> struct X {};

template <typename T> struct Y
{   
    // X[T] is a dependent name on template parameter T
    // which will be lookup during the template instantaition
    // not the template definition period
    typedef X<T> ReboundType;                        
    typedef typename X<T>::MemberType MemberType2;    // 这里的typename是做什么的？
};

这里使用typename的目的简而言之，就是cpp标准规定，T::type的形式不仅可以是一个类型，还可以是T的一个成员变量，**如果编译器能够在模板定义（该形式出现）时就明确知道它的类型，就不需要加typename；如果要等到二阶段，即模板实例化时才知道它是否合法（到底是个变量还是个类型），那么我们必须使用typename明确指定这是一个类型。**更多的例子参见原文章。

这个例子更清晰一些：

template<class T> class A
{
  T::x(y);
  typedef char C;
  A::C d;
}

根据IBM文档的解释，T::x可以被理解成一个函数调用，即T::X()；或者是T::x类型用y初始化的变量；在这种情况下，cpp编译器解释为函数调用，我们为了让编译器把它理解为类型，typename派上了用场。最后的A::C这里就成了ill-formed，我们也需要使用typename来告诉编译器我们想让你如何处理它。

Type Computations

与Computations on Types相对应的是Computations on Values:

int s = 3; // computations on values
using S = int; // computations on types

int triple = 3 * s; // computations on values
using cl_ref = const S&; // computations on types

int result = foo(triple); // computations on values
using result = std::remove_reference<cl_ref>::type; // computations on types

bool equals = (result = 0); // computations on values
constexpr bool equals = std::is_same<result, const int>::value; // computations on types

if (equals) exit(1); // computations on values
if constexpr (equals) exit(1); // computations on types

我们通过将type传递给meta_function实现这一点。

A meta-function is a “function” that operates on some types/values (parameters) and outputs some types/values (return values). Concretely, it is a struct that has public member types/fields which depend on what the template types/values are instantiated with.

比如：

// a value meta-function: identity
template<int V>
struct identity {
    static const int value = V;
}

// a type meta-function: identity
template<typename T>
struct identity {
    using type = T;
}

在第一个结构体中使用static关键字的作用是，允许我们在不实例化结构体（或者类）的时候使用其成员（他们在定义的时候就存在了），即：

int val = identity<3>::value;

那么这种meta-function有什么作用呢？

type_traits

我们结合meta-function的知识，以及先前我们对模板特例化（template specialization）的了解，我们便可以得知cpp内置的type traits库是在做什么事情了，并且为什么我们经常遇到::type或者::value的写法。这里只需要一个例子，就可以说明问题：

// primary/generic template
template<typename T>
struct is_pointer {
    static const bool value = false;
}

// specializaed template
template<typename T>
struct is_pointer<T*> {
    static const bool value = true;
}

如此一来，根据partial ordering的规则，如果我们传入一个指针，那么is_pointer<int*>::value应当为true，如果不是指针，则无法匹配specialized template，会使用通例模板，最终返回false。

Examples

最后，我们来看一个例子。这里我们想写一个标准库里iterator的distance函数，大致的结构应该是这样：

template<typename It>
size_t my_distance(It first, It last) {
    // if it_category == random_access_Iterator
    // then
    // return last - first
    else {
        size_t result = 0;
        while (first != last) {
            ++first;
            ++result;
        }
        return result;
    }
}

现在的问题在于我们首先要找到一个办法能拿到迭代器的类型。于是我们想到了我们的meta functions和cpp的type traits:

template<typename It>
size_t my_distance(It first, It last) {
    // notice! typename, lol we just introduced its effect
    using category = typename std::iterator_traits<It>::iterator_category;
    if (std::is_same<category, std::random_access_iterator_tag>::value) {
        return last - first;
    }
    else {
        size_t result = 0;
        while (first != last) {
            ++first;
            ++result;
        }
        return result;
    }
}

但是！这个例子目前并不完美，他无法编译通过，原因正是我们之前总结的-没有利用SFINAE！

在cpp17中，很简单，我们只需做如下改写：

template<typename It>
size_t my_distance(It first, It last) {
    // notice! typename, lol we just introduced its effect
    using category = typename std::iterator_traits<It>::iterator_category;
    if constexpr (std::is_same<category, std::random_access_iterator_tag>::value) {
        return last - first;
    }
    else {
        size_t result = 0;
        while (first != last) {
            ++first;
            ++result;
        }
        return result;
    }
}

Lambda Expressions

1话题的引入来自于该函数中的predicate，我们尝试着将它写做一个非固定最大值的版本，即将下边的5替换为一个limit变量：

call it by using function pointers

Pre-cpp11(Functors)

在cpp11之前，我们使用如下方法，这也是我们所说的闭包，之后lambda表达式的基础或者说内部形式：

// by value
class GreaterThan {
public:
    GreaterThan(int limit) : limit(limit) {}
    // note: this should have a const
    bool operator() (int val) const {return val >= limit};
private:
    int limit; /* the value we captured outside*/
}

// by reference
class GreaterThan {
public:
    GreaterThan(int &limit) : limit(limit) {}/* pass by reference */
    // note: this should have a const
    bool operator() (int val) const {return val >= limit};
private:
    int& limit; /* the value we captured outside, by reference*/
}

在cpp11中引入了lambda expression:

auto func = [capture-clause](parameters) -> return-value {
// body
};

// the simplest lambda:
[]{};

• return-value is optional
• can use = to capture all by value (not recommend)
• can use & to capture all by reference (not recommend)

需要注意的是，在cpp11中引出了一种返回值的写法：

auto identifier(argument) -> return type

这种写法帮助我们写出如下函数：

template<typename T1, typename T2>
auto compose(T1 a, T2 b) -> decltype(a + b);

而在cpp14中，我们可以直接省略->return type。

在cpp11中规定，如果lambda函数体内部出现了除了return额外的语句，则lambda对象默认返回void，所以我们需要-> return type指定返回类型.

cpp14

1. can use auto as the parameters to templatize the lambda–generic lambda

auto p = [](auto a) {cout << a << endl; };

1. can capture with an initialiser–z = x + y

cpp17

1. use constexpr :

constexpr auto Square = [](int n) { return n * n; };

2. can capture *this

cpp20

We can pass a template tail:

auto ForwardToTestFunc = []<typename ...T>(T&& ...args) {
  return TestFunc(std::forward<T>(args)...);
};

同时对于未捕获值的lambda对象，拥有了默认构造函数和赋值运算符(不再被声明为delete).

mutable

让我们把注意力移回到cpp11之前的版本，严格来说，成员函数operator()的重载应当设置一个指向常量对象的常量指针，即写为：

void operator()(...) const {
    // since there is a const,
    // if captured by reference, we can change the values captured
    // if captured by value, we cannot change it.
}

所以关键字mutable允许我们改变捕获的值：

class a {
  
public:
  a(int x1): x(x1) {}
  mutable int x;
  
  bool changeX(int y) const {
    x = y;
  }
};

关于关键字mutable的用法，其只能作用于非常量和非静态数据成员上（因为静态数据成员不属于类自己）。

globals & statics

lambda表达式仅允许捕捉当前函数中定义的具有automatic storage duration的变量，所以我们不能够捕捉global/static variables，对于定义在当前函数之外的名字，lambda可以直接使用。

storage duration

需要注意的是，对于具有static生命周期的变量，还包括我们使用static关键字定义的变量。即使我们将static variable定义到了函数中，他的生命周期也是直至程序结束，只不过在函数栈退出后，我们无法获取这个定义的变量了. 它还包括一种特殊情况，就是字符串字面值(string literals)：

// a string literal
char *str = "ABCDEFG";
// NOT a string literal -- 储存在栈上
char str[] = "ABCDEFG";

这三种不同的生命周期的变量，在其后的CS 61C课程中我们会了解到，其实是对应着储存在三个不同的存储器区域：static,stack,heap.

type of lambda?

需要注意的是，lambda expression最前边的auto并不是lambda的返回值，而是函数类型。所以我们是否能够不使用auto或者说在模板中为了得到lambda的类型使用decltype关键字？

在cpp20之前，答案是不行。从定义上来说，lambda表达式的类型是闭包类型（closure type），如果我们尝试使用typeid关键字获取其类型，则即使是同一个类型的lambda对象，每一个lambda对象的typeid值也是不同的：

The type of the lambda-expression (which is also the type of the closure object) is a unique, unnamed non-union class type — called the closure type.

这是由于lambda被编译器翻译为未命名类的未命名对象(cpp Primer P508)，即使定义一样，编译器也会认为每个匿名类名都不一样。

该匿名类的默认构造函数被设置为delete，并且赋值函数也被禁用，但是我们可以调用其拷贝构造函数(是否含有默认的拷贝构造/移动构造函数通常要视捕获的数据成员类型而定)：

auto f = [](int x){ return x; };
decltype(f) g = f;

需要注意的是，cpp允许使用decltype提取已经计算的lambda表达式，如上所示；但是不允许提取未计算的lambda表达式类型：

decltype([](int x){ return x; })    // error

不过自cpp20起，未捕获值的lambda表达式拥有了默认构造函数和赋值运算符。

当捕获列表为空时，我们可以将lambda表达式赋值给一个拥有相同函数签名的函数指针，相应的函数指针指向的是lambda表达式内部的一个static成员函数：

int(* f)(int, int) = [](int a, int b){ return a + b; };

但是当存在捕获值时，便无法进行这种隐式转换，因为捕获对象的实体是以类成员的形式存在的，对象整体上形成一个functor。

Pass Lambda As Argument?

所以接下来要思考的一个问题是，如何才能把一个lambda表达式作为参数传进函数？

根据先前的讨论，当lambda捕获值时，我们无法执行到函数指针的隐式转换。同时此时由于我们无法确定lambda表达式的具体类型是什么，意味着使用继承，即运行期多态让lambda对象进行动态绑定不可行。那么我们只有使用模板，作为一种编译器多态，可以将lambda表达式传入函数当中。这样做的一个好处是编译器可以在编译期将lambda表达式内联进调用函数内部，加快运行速度：

template< class ForwardIt, class T >
constexpr std::pair<ForwardIt,ForwardIt>
              equal_range( ForwardIt first, ForwardIt last,
                           const T& value );

std::function

而在cpp11中，提出了std::function，它的存在使得几个可调用对象共享同一种调用形式成为可能。

// normal functions
int add(int i, int j) { return i + j; }
// lambda
auto mod = [](int i, int j) { return i % j; };
// function object class
struct divide {
    int operator()(int denominator, int divisor) {
        return denominator / divisor;
    }
}

我们也可以利用std::function来把lambda表达式传入函数中：

std::function<double(double, double)> f_mul = [a](double x, double y) { return x * y + a; };

double calculator(double a, double b, std::function<double(double, double)> fn)
{
	return fn(a, b);
}

Class template std::function is a general-purpose polymorphic function wrapper. Instances of std::function can store, copy, and invoke any CopyConstructible Callable target – functions, lambda expressions, bind expressions, or other function objects, as well as pointers to member functions and pointers to data members.

std::bind

除了lambda expression之外，我们还可以使用头文件<functional>中的bind方法来写先前我们所需要的predicate函数,根据官方文档给出的示例，我们可以结合占位符std::placeholders来使用该函数：

using namespace std::placeholders;  // for _1, _2, _3...

std::cout << "1) argument reordering and pass-by-reference: ";
int n = 7;
// (_1 and _2 are from std::placeholders, and represent future
// arguments that will be passed to f1)
auto f1 = std::bind(f, _2, 42, _1, std::cref(n), n);
n = 10;
f1(1, 2, 1001); // 1 is bound by _1, 2 is bound by _2, 1001 is unused
                // makes a call to f(2, 42, 1, n, 7)

在该段示例代码中，std::cref(n)的作用是为n创建一个reference_wrapper的对象，与之有相同作用的还有函数std::ref(n)：

std::reference_wrapper is a class template that wraps a reference in a copyable, assignable object. It is frequently used as a mechanism to store references inside standard containers (like std::vector) which cannot normally hold references.

放到上边的例子中，就是让bind函数按照引用传递n。

比如，我们可以使用如下语法：

std::vector<std::reference_wrapper<int>> v(l.begin(), l.end());

如此一来，v内所有元素均是vector l内元素的引用。

bind()函数会给原函数创建一个call wrapper，调用wrapper函数相当于invoke f with some of its arguments bound to args.值得注意的是，bind函数声明也是通过可变函数参数实现的。

Variadic template

Variadic arguments

1在cpp11之前，如果我们想让一个函数接受任意参数，那么我们需要使用...的语法配合va_系列的宏来使用，文档给出了一个例子：

#include <iostream>
#include <cstdarg>
 
void simple_printf(const char* fmt...) // C-style "const char* fmt, ..." is also valid
{
    va_list args;
    va_start(args, fmt);
 
    while (*fmt != '\0') {
        if (*fmt == 'd') {
            int i = va_arg(args, int);
            std::cout << i << '\n';
        } else if (*fmt == 'c') {
            // note automatic conversion to integral type
            int c = va_arg(args, int);
            std::cout << static_cast<char>(c) << '\n';
        } else if (*fmt == 'f') {
            double d = va_arg(args, double);
            std::cout << d << '\n';
        }
        ++fmt;
    }
 
    va_end(args);
}
 
int main()
{
    simple_printf("dcff", 3, 'a', 1.999, 42.5); 
}

我们首先建立一个va_list的对象用于储存余下几个宏需要的信息，之后调用va_start，允许程序访问后随具名参数parm_n的可变参数：

void va_start( std::va_list ap, parm_n );

之后每当我们调用一次va_arg，就可以获取va_list内的下一个参数；最终调用va_end终止这一过程。

需要注意的是，在使用variadic arguments时，...必须跟随在参数列表之后，而不允许被放到参数列表的前边。但是在cpp中，这样的使用方式是被允许的：

int printz(...)

这种使用方式在模板重载中被作为SFINAE的fallback overload使用，因为...最不specialized，所以在overload resolution中具有最低的优先级。

fallback is a function that does not take any arguments and does not return anything.

Parameter pack

上一节中提到的variadic argument与parameter pack不一样：

Note: this is different from a function parameter pack expansion, which is indicated by an ellipsis that is a part of a parameter declarator, rather than an ellipsis that appears after all parameter declarations. Both parameter pack expansion and the “variadic” ellipsis may appear in the declaration of a function template, as in the case of std::is_function.

换而言之：

// variadic arguments
int printx(const char* fmt...);
// parameter pack
void foo(const T &t, const Args&... rest);

parameter pack是构成variadic template的基础：

A template with at least one parameter pack is called a variadic template.

共有两种参数包：模板参数包与函数参数包：

template <typename T, typename... Args> // a template parameter packet
void foo(const T &t, const Args&... rest); // a function parameter packet

我们如何理解上边的语句？可以举例来想，模板参数包中将各种不同的可能出现的类型（int, double, char* ...）打包，之后把这个包交给函数，函数对包Args做包扩展（packet expansion），传入的每一种类型都可能存在多个元素，比如double a, double b...，于是对每一种类型（即模板参数包中的每一个对应元素）打包、组合成一个名为rest的函数参数包。

需要注意的是，对于class template，参数包只能出现在最后一个参数的位置上。但是对于function template，参数包可以出现在任意位置上。

Packet expansion

在上一节中，提到了包扩展：pattern…，扩展一个包就是将他分解为构成的元素，并对每个元素应用模式pattern:

template<class ...Us> void f(Us... pargs) {}
template<class ...Ts> void g(Ts... args) {
    f(&args...); // “&args...” is a pack expansion
                 // “&args” is its pattern
}
g(1, 0.2, "a"); // Ts... args expand to int E1, double E2, const char* E3
                // &args... expands to &E1, &E2, &E3
                // Us... pargs expand to int* E1, double* E2, const char** E3

包扩展可以出现在函数调用符()内部，根据官方文档：

f(&args...); // expands to f(&E1, &E2, &E3)
f(n, ++args...); // expands to f(n, ++E1, ++E2, ++E3);
f(++args..., n); // expands to f(++E1, ++E2, ++E3, n);
f(const_cast<const Args*>(&args)...);
// f(const_cast<const E1*>(&X1), const_cast<const E2*>(&X2), const_cast<const E3*>(&X3))
f(h(args...) + args...); // expands to 
// f(h(E1,E2,E3) + E1, h(E1,E2,E3) + E2, h(E1,E2,E3) + E3)

一个包扩展的例子可参见cpp Primer P621，需要注意的是，在例中进行函数调用时的包扩展，先将包中第一个参数剥离（peel off），对应了const T &t,余下的元素构成了新的参数包，并递归调用，直到我们遇到了base case，并使用对应了非可变参数函数模板：

// base case function
template<typename T>
ostream &print(ostream &os, const T &t) {
    return os << t;
}

template<typename T, typename... Args>
// the first packet expansion, using pattern `const Args&`
ostream& print(ostream &os, const T &t, const Args&... rest) {
    os << t << ", ";
    // the second packet expansion, using pattern `rest`
    // then peel off the first element in the expansion list to be `const T &t`
    // recursion with the list with other elements
    return print(os, rest...);
}

sizeof...

我们可以通过使用sizeof...()得到包中参数的数目。

Performance

摘自：https://eli.thegreenplace.net/2014/variadic-templates-in-c/

If you’re concerned with the performance of code that relies on variadic templates, worry not. As there’s no actual recursion involved, all we have is a sequence of function calls pre-generated at compile-time. This sequence is, in practice, fairly short (variadic calls with more than 5-6 arguments are rare). Since modern compilers are aggressively inlining code, it’s likely to end up being compiled to machine code that has absolutely no function calls. What you end up with, actually, is not unlike loop unrolling.

Compared to the C-style variadic functions, this is a marked win, because C-style variadic arguments have to be resolved at runtime. The va_ macros are literally manipulating the runtime stack. Therefore, variadic templates are often a performance optimization for variadic functions.

range

在cpp20中，提出了range的概念，写了一个range库，其中包含range, view, range adaptor等……但这里不打算深究，具体详见官方文档以及这篇文章。

Object-Oriented Programming

Const

几种不同的const含义：

// 指向整型常量的指针(可修改指针本身，不可修改指针指向的对象)
const int* a;
// or:
int const* a;

// 指向整形的常量指针(不可修改指针本身，可修改指针指向的对象)
int* const a;

// 根据《cpp Primer》，this指针默认为指向非常量对象的常量指针，
// 此操作将this指针设定为指向常量对象的常量指针
void func() const

Why initialization-list?

加入我们将对象定义为const类型，那么在声明之后，对象就不可以再改变了，这意味着一般的构造函数初始化方法会出现问题（先建立对象，再挨个初始化其元素）。而initialization list在建立对象的同时立即初始化其所有元素：

test(int num1, double str1): num(num1), str(str) {};

我们也可以直接使用大括号初始化列表（brace-init-list），编译器也会为我们选择合适的对应的构造函数（如果需要的话）：

class foo {
public:
    foo(size_t size): 
        size{size},
        vec{size, nullptr} {}
private:
    vector<int*> vec;
    size_t size;
};

friend

类的友元函数是定义在类外部，但有权访问类的所有私有（private）成员和保护（protected）成员。尽管友元函数的原型有在类的定义中出现过，但是友元函数并不是成员函数。

友元可以是一个函数，该函数被称为友元函数；友元也可以是一个类，该类被称为友元类，在这种情况下，整个类及其所有成员都是友元。

相同class的各个objects互为友元：

Mutual friends class

在完成HashMap作业的过程中，出现了Container与Iterator类需要互为友元的问题，这一问题在模板的章节中已有提到，但是对于这种特殊的Mutual friends class行为并未作出过多的解释。

当A, B两个类互为友元时，我们称这两个类为Mutual Friends Classes。为了解决这个问题，我们首先要知道，当一个类仅有声明，而没有定义时，类为不完整类型。我们仅能够使用指向该类的指针、引用或者将类作为形参和返回值出现在函数声明中。

one file

当这两个类位于同一文件中时：

1. 作类B的前置声明（forward declaration），告知类A存在一个名为B的类；
2. 定义类A，在类A中将类B声明为友元，对于需要用到类B的函数，仅提供函数声明，因为此时我们还不知道B的具体定义；
3. 定义类B，提供完整定义；
4. 将类A中需要调用B的方法定义补充完整

// Forward Declaration
class B;
 
// Class A
class A {
 
    // Member of class A
    int data;
 
public:
    // Make B as a friend of class A
    friend class B;
 
    // Constructor to initialise member
    // of class A
    A(int d) { data = d; }
 
    // Function to get data of friend
    // class B
    void get_data_B(B objb);
};
 
// Class B
class B {
 
    // Member of class B
    int dataB;
 
public:
    // Making A a friend of class B
    friend class A;
 
    // Constructor to initialise member of
    // class B
    B(int d) { dataB = d; }
 
    // Function to get the data of
    // friend class A
    void get_data_A(A obja)
    {
        cout << "Data of A is: "
             << obja.data;
    }
};
 
// Function for accessing friend class
// B's object
void A::get_data_B(B objb)
{
    cout << "Data of B is: "
         << objb.dataB;
}

separate file

当类A与类B分别定义在不同的文件中时，我们需要注意应当避免出现头文件递归包含额情况，也就是说我们不可以在A.h中包含了B.h的同时反过来也同时包含另一个文件。

假定我们现在B.h包含了A.h，那么在文件A.h中，我们应当使用先前提到的策略：做一个类B的前置声明，并且同样地不可以在类A内部提供类B的内部信息：

• A.h

/* This is called a "forward declaration".  We use it to tell the compiler that
   the identifier "B" will from now on stand for a class, and this class will be
   defined later.  We will not be able to make any use of "B" before it has been
   defined, but we will at least be able to declare pointers to it. */
class B;

class A
{
    /* We cannot have a field of type "B" here, because it has not yet been
       defined. However, with the forward declaration we have told the compiler
       that "B" is a class, so we can at least have a field which is a pointer 
       to "B". */
    B* pb; 
}

• B.h

#include "A.h"

class B
{
   /* the compiler now knows the size of "A", so we can have a field
      of type "A". */
   A a;
}

template mutual friends

在hashmap的作业里，我们看到了这种用法：两个文件hashmap.h与hashmap_iterator.h中，前一个文件对后一个文件，即提供了迭代器类的文件做了包含，但是在hashmap_iterator.h中我们发现，即使不提供HashMap的前置声明，运行也不会报错，这是为什么呢？

这是因为在hashmap_iterator.h中，我们对iterator做了模板类的定义，在模板参数中包含了HashMap类型，这允许我们直接通过作用于运算符::来获取（不需要提供其他任何参数，因为在hashmap_iterator模板类被实例化之后，我们便得到了其模板参数HashMap的具体类型）：

1. HashMap中的类型别名定义
2. HashMap的静态成员

于是这里出现一个问题，如果我们要用到HashMap中的非静态成员变量、函数怎么办呢？这些内容我们无法直接通过::的方法获取，而因为我们是把container class name放到了template parameter中更是无法直接在此类中给出实例化类名的代码从而通过成员访问运算符获取非静态内容。

我们可以通过如下手段解决此问题：首先把需要使用的容器非静态类成员转化成使用类型别名表示的形式，之后在友元类中使用::获取其类型，定义一个该类型的指针，并将指针初始化指向容器成员：

// friend class, class type foo as template parameter
template<typename foo>
class foo_1 {
    // since foo will be a complete type even if it's a template class,
    // we can directly write 'foo'
    friend foo;
    // the type of vector, defined in the hashmap class
    // since it's a type, we can directly use :: to get it here!
    using bucket_array_type = foo::bucket_array_type;
    
    // thyen, make a pointer!
    bucket_array_type* _buckets_array;
    
    // in iterator class, we shall use private constructor
    // iterator's constructor, we will use it in the 
    // hashmap class
    foo_1(bucket_array_type* _buckets_array):
    	_buckets_array(_buckets_array) {}
    
public:
	// some member functions
};

class foo {
private:
    vector<node*> _buckets_array;
    
    using bucket_array_type = decltype(_buckets_array);
    // foo_1's template specialization of <foo> type
    friend class foo_1<foo>;
    
public:
    foo(/* */);
    foo_1 begin() {
        // call iterator constructor here
        /** give the address of the vector to initialize the
         * pointer pointing to vector<> type in the iterator
         * class */
        return {&_buckets_array};
    }
};