All posts

Modern C++

C++测时模板

#include<iostream>
#include<chrono>
typedef std::chrono::high_resolution_clock Clock;

int main()
{
    auto start = Clock::now();
    //your test program
    auto end = Clock::now();
    std::cout << "Time taken: "
		<< std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count()
		<< " nanoseconds" << std::endl;
    //其他时间单位:std::chrono::seconds, std::chrono::milliseconds,
}

可以去https://ideone.com/ (geeks for geeks同款)运行程序,排除机器变量干扰。

C++矩阵运算(运算符重载)

Link

#include<iostream>

#include<vector>

class Matrix{

    private:

        int rows , cols ;

        std::vector<std::vector<int>> data ;

    public:

        Matrix(int rows, int cols , std::vector<std::vector<int>> data): rows(rows), cols(cols) , data(data){}



        int get_elem(int row , int col){

            return data[row][col];

        }

        void display(){

            for(int i = 0 ; i < rows ; i++){

                printf("\n");

                for(int j = 0 ; j < cols ; j++){

                    printf("%d  " , data[i][j]);

                }

            }

        }

        Matrix operator+(const Matrix& A) const{

            Matrix result(rows , cols , data);

            for(int i = 0 ; i < rows ; i++)

                for(int j = 0 ; j < cols ; j++){

                    result.data[i][j] += A.data[i][j];

                }

            return result;

        }



        Matrix operator-(const Matrix& A) const{

            Matrix result(rows , cols , data);

            for(int i = 0 ; i < rows ; i++)

                for(int j = 0 ; j < cols ; j++){

                    result.data[i][j] -= A.data[i][j];

                }

            return result;

        }



        Matrix operator*(const Matrix& A) const{

            if(cols != A.rows){

                std::cout << "Invalid matrix dimensions" << std::endl;

                exit(-1);

            }

            Matrix result(rows , A.cols , std::vector<std::vector<int>> (rows , std::vector<int>(A.cols,0)));

            for(int i = 0 ; i < rows ; i++)

                for(int j = 0 ; j < A.cols ; j++)

                    for(int k = 0 ; k < cols ; k++){

                        result.data[i][j] += data[i][k] * A.data[k][j];

                    }

            return result;

        }



        Matrix transpose()const{

            Matrix res(cols , rows , data);

            for(int i = 0 ; i < cols ; i++)

                for(int j = 0 ; j < rows ; j++){

                    res.data[i][j] = data[j][i];

                }

                return res;

        }

};



int main()

{

    std::vector<std::vector<int>> data = { {1,2,3} , {4,5,6} , {7,8,9}};

    std::vector<std::vector<int>> data1 = { {1,2,3} , {4,5,6} , {7,8,9} , {6,6,6}};

    std::vector<std::vector<int>> data2 = { {1,2,3,4} , {4,5,6,7} , {7,8,9,10}};

    Matrix A(3,4,data2);

    Matrix B(4,3,data1);

    Matrix C(3,3,data);

    // C = A + B;

    C = A * B;

    A.display();

    B.display();

    C.display();

    C.transpose().display();

}

C++11 tuple

Link

#include<iostream>
#include<tuple>
#include<string>

int main()
{
    std::string name = "Alice";
    int age = 21;
    double grade = 100.0;
    auto student_tuple = std::make_tuple(name , age , grade);

    std::string name_from_student = std::get<0>(student_tuple);
    int age_of_student = std::get<1>(student_tuple);
    double grade_of_student = std::get<2>(student_tuple);

    std::cout << "name : " << name_from_student << std::endl;
    std::cout << "age  : " << age_of_student    << std::endl;
    std::cout << "grade: " << grade_of_student  << std::endl;
    return 0;
}

自动补全背后的算法(字典树)

Link

Trie树(又称前缀树或字典树)是一种用于快速检索字符串数据集中的键的树形数据结构。这种结构非常适合处理字符串集合,特别是实现自动补全或拼写检查等功能。下面,我将通过一个具体的例子来解释Trie树的结构和工作原理。

假设我们有一个Trie树,我们要在其中存储单词“CAT”,“CAN”,和“BAT”。Trie树的结构将如下所示:

       Root
      /    \
     B      C
     |      |
     A      A
    / \    / \
   T   *  T   N
  /         /
 *         *  

在这个图形化表示中:

  • 每个节点代表一个字符。
  • 根节点(Root)不包含字符,它是所有单词的起始点。
  • 每条从根节点到某个标记为“”的节点的路径代表一个单词。例如,从根节点到第一个“”的路径是“BAT”。
  • 分支表示单词的不同字符。例如,“BAT”和“CAT”共享第一个字符,但第二个字符不同,因此在第二层分开。

现在,如果我们要添加另一个单词比如“CAR”,Trie树将会更新为:

       Root
      /    \
     B      C
     |      |
     A      A
    / \    / \
   T   *  T   R
  /       /   |
 *       *    *
              |
              *  

在这个新的结构中,“CAT”和“CAR”共享前两个字符“CA”,但第三个字符不同,在“CAR”中为“R”,因此在第三层分叉。

操作说明

  1. 插入:当插入一个新单词时,从根节点开始,为单词的每个字符创建一个新的子节点(除非该字符已经存在)。到达单词的最后一个字符时,标记这个节点表示一个单词的结束。
  2. 搜索:为了查找一个单词,从根节点开始,沿着单词的字符移动。如果能够在每一步都找到相应的字符,并且最后一个字符被标记为一个单词的结尾,那么该单词存在于Trie树中。
  3. 前缀搜索:前缀搜索与全词搜索类似,但不需要最后一个字符被标记为单词的结尾。如果能够顺着前缀的字符在树中移动到最后一个字符,那么这个前缀存在于树中。

Trie树在处理大量字符串,尤其是进行快速前缀查找和词汇自动补全时非常有效。由于它基于共享前缀来存储单词,因此相比于其他数据结构,它在空间效率上通常更优。

TrieNode 设计

TrieNode 用于表示Trie树中的每个节点。接下来详细解释这个代码片段,包括TrieNode的设计以及每个成员的作用。

class trie_node{
    public:
        bool is_end_of_word;
        std::unordered_map<char , trie_node*> children;

        trie_node(): is_end_of_word(false){}
};
  1. bool isEndOfWord;:这是一个布尔型成员变量,用于标记当前节点是否代表一个单词的结束。如果isEndOfWord为true,则表示从根节点到当前节点的路径构成一个完整的单词。
  2. unordered_map<char, TrieNode*> children;:这是一个无序映射(unordered_map),用于存储当前节点的子节点。Trie树的一个关键特性是每个节点可以有多个子节点,每个子节点对应一个字符。这个unordered_map允许我们将字符映射到相应的子节点。
  3. TrieNode() : isEndOfWord(false) {}:这是TrieNode类的构造函数。构造函数用于初始化新创建的TrieNode对象。在这里,构造函数将isEndOfWord初始化为false,表示节点默认不是单词的结束。

现在让我们通过一个示例来解释如何使用这个TrieNode类来构建Trie树:

假设我们要在Trie树中插入单词”CAT”,首先我们创建一个根节点。然后,我们从根节点开始,在每个字符位置上创建一个新的TrieNode对象,将isEndOfWord设置为false。在这个过程中,我们将字符映射到相应的子节点,如下所示:

  1. 创建根节点,isEndOfWord为false。
  2. 在根节点下创建字符’C’对应的子节点,isEndOfWord为false。
  3. 在字符’C’对应的子节点下创建字符’A’对应的子节点,isEndOfWord为false。
  4. 在字符’A’对应的子节点下创建字符’T’对应的子节点,isEndOfWord为true,因为”CAT”的最后一个字符表示单词的结束。

这就是如何使用TrieNode类来构建Trie树的一部分。这个类的设计允许我们轻松地在每个节点上附加字符和标记单词的结束。随着插入更多的单词,Trie树的结构会不断扩展。

完整代码

这段代码实现了一个称为“Trie”(也被称为前缀树或字典树)的数据结构:

#include<iostream>
#include<unordered_map>
#include<string>
class trie_node{
    public:
        bool is_end_of_word;
        std::unordered_map<char , trie_node*> children;

        trie_node(): is_end_of_word(false){}
};

class trie{
    private:
        trie_node* root;
        //Recursively cleans up memory
        void clear_memory(trie_node* node){
            for(auto pair : node->children)
                clear_memory(pair.second);
            delete node;
        }
    public:
        trie(){
            root = new trie_node;
        }

        void insert(std::string word){
            trie_node* current = root;
            for(char ch : word){
                if(current->children.find(ch) == current->children.end()){
                    current->children[ch] = new trie_node;
                }
                current = current->children[ch];
            }
            current->is_end_of_word = true;
        }
        //search whether word is in trie tree or not
        bool search(std::string word){
            trie_node* current = root;
            for(char ch : word){
                if(current->children.find(ch) == current->children.end())
                    return false;
                current = current->children[ch]; 
            }
            return current != nullptr && current->is_end_of_word;
        }

        //search whether prefix is the prefix of the word in trie tree or not
        bool start_with(std::string prefix){
            trie_node* current = root;
            for(char ch : prefix){
                if(current->children.find(ch) == current->children.end()){
                    return false;
                }
                current = current->children[ch];
            }
            return true;
        }


        ~trie(){
            clear_memory(root);
        }

};

int main()
{
    trie trie_tree;
    trie_tree.insert("nudt");
    trie_tree.insert("hust");
    std::cout << trie_tree.search("hust") << std::endl;
    std::cout << trie_tree.start_with("nud") << std::endl;
    return 0;
}

RAII and smart pointers

reference1

reference2

RAII即Resource Acquisition is Initialization , 中文翻译叫资源获取即初始化 .其实这种叫法很容易让人疑惑,摘一个stackoverflow上的回答:

It’s a really terrible name for an incredibly powerful concept, and perhaps one of the number 1 things that C++ developers miss when they switch to other languages. There has been a bit of a movement to try to rename this concept as Scope-Bound Resource Management, though it doesn’t seem to have caught on just yet.

叫Scope-Bound Resource Management可能更合适。(即范围限制资源管理)

When we say ‘Resource’ we don’t just mean memory - it could be file handles, network sockets, database handles, GDI objects… In short, things that we have a finite supply of and so we need to be able to control their usage. The ‘Scope-bound’ aspect means that the lifetime of the object is bound to the scope of a variable, so when the variable goes out of scope then the destructor will release the resource. A very useful property of this is that it makes for greater exception-safety. For instance, compare this:

资源的使用一般经历三个步骤a.获取资源 b.使用资源 c.销毁资源,但是资源的销毁往往是程序员经常忘记的一个环节,所以程序界就想如何在程序员中让资源自动销毁呢?c++之父给出了解决问题的方案:RAII,它充分的利用了C++语言局部对象自动销毁的特性来控制资源的生命周期。RAII就是一种编程思想,获取资源(例如声明指针,打开文件)必须在一个范围(生命周期)内,离开范围(生命周期)后需要释放资源。

举一个例子(虽然很生硬):

#include<iostream>
#include<cstdlib>
#include<random>
void fun(){
    int* array = new int[100];
    for(int i = 0 ; i < 100 ; i++)
        array[i] = rand();
    //use the numbers in array to do something.....
    //forget to delete array: delete[] array;
}
int main(){
    for(int i = 0 ; i < 1e6 ; i++)
        fun();
}

以上程序可能会发生内存泄露,原因是fun()内的指针array没有被释放,应该在fun()最后加一句delete array;

实际上,忘记释放资源的事在大规模程序中经常发生(在一些调用过程中甚至都意识不到)。如何去避免这种情况,一种便是如履薄冰,每次申请资源时便配套释放资源;一种则是让资源自动释放,即资源出了生命周期后便自动释放。

这种情景就类似于类的析构函数了,因此RAII的实现经常是借助类完成的,即构建一个资源类,离开生命周期后会自动调用析构函数释放资源。用RAII思想去重写以上代码:

#include<iostream>
#include<cstdlib>
#include<random>
void fun(){
    int* array = new int[100];
    for(int i = 0 ; i < 100 ; i++)
        array[i] = rand();
    //use the numbers in array to do something.....

}
class array{
    public:
        int* array_;
        array(){
            array_ = new int[100];
            for(int i = 0 ; i < 100 ; i++)
                array_[i] = rand();
        }

        void fun(){
            //use array_ do something

        }

        ~array(){
            if(array_ != nullptr){
                delete[] array_;
                array_ = nullptr;
            }
        }
};
int main(){
    for(int i = 0 ; i < 1e6 ; i++){
        //fun();//memory leak
        array _array;
        _array.fun();
    }

    return 0;  
}

smart pointer

c++11引入的智能指针就是RAII思想的最好体现

shared_ptr unique_ptr weak_ptr

以上示例函数fun()可以用智能指针重写为:

void _fun(){
    std::shared_ptr<int> arr(new int[100]);
    for(int i = 0 ; i < 100 ; i++){
        arr.get()[i] = rand();
    }
    //use arr to do something

    //delete arr automatically
}
  • 智能指针需要用.get()得到原来的指针(retrieve the raw pointer stored within a shared_ptr)
  • 智能指针包含在<memory>库中
  • 初次使用智能指针时Vscode解释器可能会检出错误,可能是Vscode检查器用的c++版本低于c++11,可以重新生成一下c_cpp_properties.json,检查其中的cppStandard
#include<iostream>
#include<memory>
class recangle{
    public:
        int length , breadth;
        recangle(int l , int b): length(l) , breadth(b){}

        int area(){
            return this->length * this->breadth ;
        }
};

class circle{
    public:
        int radius;
        circle(int r):radius(r){}

        int area(){ return 3.14 * this->radius * this->radius;}
};

int main(){
    std::shared_ptr<recangle> p1(new recangle(6,8));
    std::shared_ptr<recangle> p2(p1);
    std::weak_ptr<recangle> p2_(p2);
    std::cout << p2->area() << std::endl;
    std::cout << p2.use_count() << std::endl;

    std::unique_ptr<recangle> p3(new recangle(10,10));
    // std::unique_ptr<recangle> p4 = p3;//error:include\c++\bits\unique_ptr.h") cannot be referenced

    std::unique_ptr<recangle> p4 = move(p3);
    std::cout << p4->area() << std::endl;
    // std::shared_ptr<int> p5 = move(p4);//error:no suitable user-defined conversion from "std::unique_ptr<recangle, std::default_delete<recangle>>" to "std::shared_ptr<int>" existsC/C++(312)

}
  • unique_ptr声明的指针独自占有一段资源,不允许其他指针指向这段资源
  • 不能将unique_ptr的使用权转交给shared_ptr , 只能转给unique_ptr
  • 能用.use_count()得出资源被指向的指针数,即有几根shared_ptr指向该资源
  • weak_ptr提出的原因:

Weak_ptr is a smart pointer that holds a non-owning reference to an object. It’s much more similar to shared_ptr except it’ll not maintain a Reference Counter. In this case, a pointer will not have a stronghold on the object. The reason is if suppose pointers are holding the object and requesting for other objects then they may form a Deadlock.

weak_ptr指向资源而不占用资源,不增加reference counter (.use_count())

这是为了防止shared_ptr发生死锁(deadlock)

Deadlock:

死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。这种情况在多线程编程中尤为常见,当两个或更多的线程互相等待对方释放资源时,就可能发生死锁。

在C++中,shared_ptr智能指针可能会导致死锁,特别是当两个shared_ptr对象互相引用时。例如,假设我们有两个类A和B,它们互相持有对方的shared_ptr,这就可能导致死锁。因为每个shared_ptr都在等待对方释放资源,但由于它们都在等待,所以没有一个shared_ptr会释放资源,从而导致死锁

class A;
class B;

class A {
public:
    shared_ptr<B> pb_;
    //应修改成: weak_ptr<B> pb_;
};

class B {
public:
    shared_ptr<A> pa_;
};

void test() {
    shared_ptr<A> pa(new A());
    shared_ptr<B> pb(new B());
    pa->pb_ = pb;
    pb->pa_ = pa;
}

学了RAII后,想着去重构以前的项目,尽量用智能指针,但发现还是不能完全替代:

  • 智能指针一旦指向了某块资源,该智能指针也无法再修改。这意味着不能像裸指针一样可传入函数、返回参数。例如在写链表时用智能指针反而会有很多麻烦,因为你不知道什么时候智能指针就把你的结点释放了:joy: 基于此,智能指针不适合传入函数、被函数(或类)反复调用,因为你不知道什么时候他会被释放。
  • 尝试过后,仍然觉得C++的指针还是比较难控制的。所以尽量少用指针(尽量不用new )吧,用一些成熟的符合RAII规范的容器(link,vecter,string.et)与配套的迭代器代替.如果实在要用指针,一定慎之又慎。:cry: C++不喜欢菜鸟

PS:尝试用list实现链表(造链表轮子是内存泄漏的重灾区)

#include<iostream>
#include<list>
using namespace std;
template<typename T>
class linked_list{
    public:
        list<T> L;

        T operator[] (int idx){
            auto it = L.begin();
            advance(it,idx);
            return *it;
        }

        int _insert(T elem , int idx){
            if(idx < 0 || idx > L.size()){cout << "please input a valid idx\n"; return -1;}
            auto it = L.begin();
            advance(it,idx);
            L.insert(it,elem);
            return 0;
        }

        void push_back(T elem){
            L.push_back(elem);
        }

        bool is_empty(){
            return !L.size();
        }

        void delete_elem(T elem){
            L.remove(elem);
        }

        void clear(){
            L.clear();
        }

        void show(){
            for(auto i : L){
                cout << i << " ";
            }
            cout << endl;
        }
};
int main(){
    linked_list<int> _L;
    for(int i = 0 ; i < 30 ; ++i){
        _L.push_back(i);
    }

    _L._insert(666,16);
    _L.delete_elem(19);
    _L.show();
    cout << _L[6];

    return 0;
}

Virtual function & 多态

虚函数是实现类多态的一种方法:

// C++ program to illustrate
// concept of Virtual Functions

#include <iostream>
using namespace std;

class base {
public:
	virtual void print() { cout << "print base class\n"; }

	void show() { cout << "show base class\n"; }
};

class derived : public base {
public:
	void print() { cout << "print derived class\n"; }//对base类中的print方法进行重载

	void show() { cout << "show derived class\n"; }//base中show()方法不是虚函数,无法重载
};

int main()
{
	base* bptr = new derived;

	// Virtual function, binded at runtime
	bptr->print();//print derived class\n

	// Non-virtual function, binded at compile time
	bptr->show();//show base class\n

	return 0;
}
  • 每个包含虚函数的类都有一个虚函数表(vtable),这是为了支持运行时多态。虚函数表是一个指向函数指针的数组,这些函数指针对应于类中的每个虚函数。通过这个机制,程序可以在运行时根据对象的实际类型来调用正确的函数。
  • VTable & VPtr :
    1. 虚拟函数表(VTable):当一个类中声明了虚函数(virtual method),编译器会为这个类创建一个虚拟函数表(VTable)。这个表中存储了类中所有虚函数的地址。
    2. 虚拟指针(VPtr):编译器还会为每个类实例创建一个虚拟指针(VPtr),并将其初始化为指向该类的VTable。
    3. VTable的共享:一个类的VTable是所有该类实例共享的,也就是说,编译器只为这个类创建一个VTable实例,然后所有该类的对象都共享这个VTable。
    4. VPtr的独立性:尽管VTable是共享的,但每个类实例都有自己的VPtr。
    5. 类对象大小:如果一个类对象至少包含一个虚函数,那么这个对象的大小将是该类数据成员的大小加上VPtr的大小。在C++中,可以通过sizeof操作符来获取这个大小
  • 多态函数的解析是在运行时(runtime)完成的。(不像一般函数是在编译时完成解析。)
  • 虚函数不能是静态函数(static)
  • 应该使用基类类型的指针或引用来访问虚函数,以实现运行时多态性。
  • 指向derived的指针可以是base(基类)类型 (base* bptr = new derived;) , 在执行bptr->print()时首先会尝试执行base类中的print方法,当发觉base::print()函数是虚函数时,会从虚函数地址表中查找derived::print()的地址去执行derived::print()。而base::show()不是虚函数,编译器不会从虚函数表中查找derived::show()(虚函数表中也没有该地址),因此bptr->show执行的是base::show()。
  • 下面是一个体现运行时多态的便利性的例子:
#include <iostream>

// 基类 Shape
class Shape {
public:
    // 虚析构函数确保派生类的资源被正确释放
    virtual ~Shape() {}

    // 纯虚函数 Draw,定义了一个接口
    virtual void Draw() const = 0;
};

// 派生类 Circle
class Circle : public Shape {
public:
    void Draw() const override {
        std::cout << "Drawing a circle." << std::endl;
    }
};

// 派生类 Rectangle
class Rectangle : public Shape {
public:
    void Draw() const override {
        std::cout << "Drawing a rectangle." << std::endl;
    }
};
int main() {
    // 创建一个 Shape 指针数组
    Shape* shapes[2];
    shapes[0] = new Circle();
    shapes[1] = new Rectangle();

    // 通过 Shape 指针调用 Draw 函数
    for (auto shape : shapes) {
        shape->Draw();  // 动态绑定到正确的 Draw 实现
    }

    // 清理资源
    for (auto shape : shapes) {
        delete shape;
    }

    return 0;
}
  • 在 main 函数中,我们创建了一个 Shape 指针数组 shapes,并将 Circle 和 Rectangle 对象的地址存入其中。
  • 当我们通过 Shape 指针调用 Draw() 时,实际上会调用 Circle 或 Rectangle 中的 Draw() 方法。这是因为 Draw() 是虚函数,编译器会在运行时根据对象的实际类型来决定调用哪个版本的 Draw()
  • 如果将来需要添加新的图形类型(例如 Triangle),只需要创建一个新的派生类并实现 Draw() 方法即可。不需要修改现有的代码,就可以将新的图形类型加入到系统中。这种设计使得系统更加灵活和易于维护。

但虚函数带来的查表开销也是较大的,因此可以通过CRTP这种设计模式来避免

CRTP(Curiously recurring template pattern)

将派生类作为模板参数传入基类

reference

以下的例子展示了当虚函数被大量调用时所带来的开销:

// A simple C++ program to demonstrate run-time
// polymorphism
#include <chrono>
#include <iostream>
using namespace std;

typedef std::chrono::high_resolution_clock Clock;

// To store dimensions of an image
class Dimension {
public:
	Dimension(int _X, int _Y)
	{
		mX = _X;
		mY = _Y;
	}

private:
	int mX, mY;
};

// Base class for all image types
class Image {
public:
	virtual void Draw() = 0;//虚函数等于0,表示该类的任何派生类都要重新定义Draw()
	virtual Dimension GetDimensionInPixels() = 0;

protected:
	int dimensionX;
	int dimensionY;
};

// For Tiff Images
class TiffImage : public Image {
public:
	void Draw() {}
	Dimension GetDimensionInPixels()
	{
		return Dimension(dimensionX, dimensionY);
	}
};

// There can be more derived classes like PngImage,
// BitmapImage, etc

// Driver code that calls virtual function
int main()
{
	// An image type
	Image* pImage = new TiffImage;

	// Store time before virtual function calls
	auto then = Clock::now();

	// Call Draw 1000 times to make sure performance
	// is visible
	for (int i = 0; i < 1000; ++i)
		pImage->Draw();

	// Store time after virtual function calls
	auto now = Clock::now();

	cout << "Time taken: "
		<< std::chrono::duration_cast<std::chrono::nanoseconds>(now - then).count()
		<< " nanoseconds" << endl;

	return 0;
}

Output :

Time taken: 2613 nanoseconds

When a method is declared virtual, compiler secretly does two things for us:

  1. Defines a VPtr in first 4 bytes of the class object
  2. Inserts code in constructor to initialize VPtr to point to the VTable

采用CRTP方法来实现静态多态,减去虚函数表的动态开销 :

// Image program (similar to above) to demonstrate
// working of CRTP
#include <chrono>
#include <iostream>
using namespace std;

typedef std::chrono::high_resolution_clock Clock;

// To store dimensions of an image
class Dimension {
public:
	Dimension(int _X, int _Y)
	{
		mX = _X;
		mY = _Y;
	}

private:
	int mX, mY;
};

// Base class for all image types. The template
// parameter T is used to know type of derived
// class pointed by pointer.
template <class T>
class Image {
public:
	void Draw()
	{
		// Dispatch call to exact type
		static_cast<T*>(this)->Draw();
	}
	Dimension GetDimensionInPixels()
	{
		// Dispatch call to exact type
		static_cast<T*>(this)->GetDimensionInPixels();
	}

protected:
	int dimensionX, dimensionY;
};

// For Tiff Images
class TiffImage : public Image<TiffImage> {
public:
	void Draw()
	{
		// Uncomment this to check method dispatch
		// cout << "TiffImage::Draw() called" << endl;
	}
	Dimension GetDimensionInPixels()
	{
		return Dimension(dimensionX, dimensionY);
	}
};

// There can be more derived classes like PngImage,
// BitmapImage, etc

// Driver code
int main()
{
	// An Image type pointer pointing to Tiffimage
	Image<TiffImage>* pImage = new TiffImage;

	// Store time before virtual function calls
	auto then = Clock::now();

	// Call Draw 1000 times to make sure performance
	// is visible
	for (int i = 0; i < 1000; ++i)
		pImage->Draw();

	// Store time after virtual function calls
	auto now = Clock::now();

	cout << "Time taken: "
		<< std::chrono::duration_cast<std::chrono::nanoseconds>(now - then).count()
		<< " nanoseconds" << endl;

	return 0;
}

Output :

Time taken: 732 nanoseconds
  • Image<TiffImage>* pImage = new TiffImage;
  • 传入基类Image的模板参数为TiffImage,那么pImage的draw()函数为static_cast<TiffImage*>(this)->Draw();

执行pImage->Draw();时,编译器会先找Image类,执行Image::Draw() : static_cast<TiffImage*>(this)->GetDimensionInPixels();将this指针转成TiffImage*型,再去访问TiffImage::GetDimensionInPixels()

  • CRTP是静态绑定,它通过模板实现多态,在编译时就已经确定了要调用的具体函数,而不是在运行时。

CRTP实现类计数

#include<iostream>
template<typename CountedType>
class objectCounter{
public:
    inline static std::size_t count = 0;//必须加上inline才能在类中对静态变量赋值

    objectCounter(){
        ++count;
    }

    objectCounter(objectCounter<CountedType> const&){
        ++count;
    }

    objectCounter(objectCounter<CountedType> const&& ){
        ++count;
    }

    ~objectCounter(){
        --count;
    }

public:
    static std::size_t live(){
        return count;
    }
};

template<typename CharT>
class MyString : public objectCounter< MyString<CharT> >{
public:
    MyString(){}

    ~MyString(){}
};
int main(){
    MyString<char> s1, s2;

    MyString<char> s3(s2);

    MyString<wchar_t> ws1, ws2;
    
    std::cout << "num of MyString<char>: " << MyString<char>::live() << '\n';
    std::cout << "num of MyString<wchar_t>: " << MyString<wchar_t>::live() << '\n';
}

objectCounter是接受一个模板参数CountedType的计数器。它用于记录CountedType这个类的实例个数。

MyString是一个自定义的字符串class,接受一个字符类型CharT作为模板参数。它继承自objectCounter< MyString<CharT> >,使得objectCounter可以对MyString<CharT>进行计数。

模板的实例化:理解这个问题时, 可以想象编译器会实例化哪些模板。MyString<char>会实例化两个模板:objectCounter<MyString<char>> and MyString<char>。调用MyString<char>的构造函数后,会隐式调用objectCounter< MyString<char>>的构造函数,从而使MyString<char>>::count加一。

类的实例化:MyString<char>继承自objectCounter< MyString<char>> , 因此MyString<char>的构造函数、拷贝构造函数、移动构造函数、析构函数都会隐式调用父类相应的函数,从而实现类的实例计数。

模板参数不会被推导的情况

#include <iostream>
template<typename RT, typename T1, typename T2>
RT max(T1 a, T2 b){
	return a > b ? a : b;
}
int main() {
	int a = 2;
	double b = 3.14;
	std::cout << ::max(a, b) << std::endl;
}
prog.cpp:3:4: note:   template argument deduction/substitution failed:
prog.cpp:9:25: note:   couldn't deduce template parameter ‘RT’
std::cout << ::max(a, b) << std::endl;
                      ^

上面的例子中,RT的类型是T1 or T2,编译器无法推断:

In cases when there is no connection between template parameters(e.g. RT) and call parameters(e.g. a and b), the compiler can’t take the template parameters into account and also can’t deduce it.

RT与函数形参无关时,编译器不会去推断RT的类型。

编译器不是推断不出RT,而是根本不会去推断RT。把代码改成这样,编译器也不会去推断RT:

#include <iostream>
template<typename RT, typename T>
RT max(T a, T b){
	return a > b ? a : b;
}
int main() {
	int a = 2;
	int b = 3;
	std::cout << ::max(a, b) << std::endl;
}

尽管我们一眼可以看出RT肯定等于T,但编译器不会去推断。

正确示范

使用auto

#include <iostream>
template<typename T1, typename T2>
auto max(T1 a, T2 b){
	return a > b ? a : b;
}
int main() {
	int a = 2;
	double b = 3.14;
	std::cout << ::max(a, b) << std::endl;
}

auto会在编译期进行推断,例如a为int,b为double,在进行a>b比较时,a会隐式转换为double,那么auto会被推断为double.

显示指定

#include <iostream>
template<typename RT, typename T1, typename T2>
RT max(T1 a, T2 b){
	return a > b ? a : b;
}
int main() {
	int a = 2;
	double b = 3.14;
	std::cout << ::max<double>(a, b) << std::endl;
}

type trait 类型萃取

#include <iostream>
#include<type_traits>
template<typename T1, typename T2, typename RT = std::common_type_t<T1,T2>>
RT max(T1 a, T2 b){
	return a > b ? a : b;
}
int main() {
	int a = 2;
	double b = 3.14;
	std::cout << ::max<double>(a, b) << std::endl;
}

std::common_type_t<>会返回多个类型的公共类型。例如std::common_type_t<int,double>等于double,因为可以隐式转换int为double从而统一类型。

Concepts

在模板下添加requires

#include<concepts>

template <typename T>
requires std::totally_ordered<T> // 要求类型T可排序
T my_max(T a, T b) {
    return a > b ? a : b;
}

可以尝试去掉以下代码中的requires,看看报错信息有多么令人头疼。加上requires,报错信息更精确。

#include <iostream>
#include<vector>
#include<string>
#include <concepts>

class Person{
private:
    std::string name;
public:
    template<typename STR>
    requires std::is_convertible_v<STR,std::string>
    
    explicit Person(STR&& n): name(std::forward<STR>(n)){
        std::cout << "TMPL-CONSTR for " << name << "\n";
    }
};
int main(){
    Person p(123);
}

常见的约束:

概念(Concept) 用途 示例
std::integral<T> T 必须是整数类型(int, short 等) requires std::integral<T>
std::floating_point<T> T 必须是浮点类型(float, double) requires std::floating_point<T>
std::copyable<T> T 可拷贝(有拷贝构造函数和赋值运算符) requires std::copyable<T>
std::movable<T> T 可移动(有移动构造函数和赋值运算符) requires std::movable<T>
std::equality_comparable<T> T 支持 == 和 != requires std::equality_comparable<T>
std::totally_ordered<T> T 支持 <, <=, >, >= requires std::totally_ordered<T>
std::ranges::range<T> T 是范围(有 begin() 和 end()) requires std::ranges::range<T>
std::input_iterator<T> T 是输入迭代器 requires std::input_iterator<T>
std::invocable<F, Args...> F 可调用,参数为 Args... requires std::invocable<F, int, double>

Defining Concepts

检查成员函数是否存在

#include<concepts>
#include<vector>
#include<string>
#include<iostream>
template <typename T>
requires requires(T obj){
    obj.size();
    obj.clear();
}
void reset(T& obj){
    obj.clear();   
}

int main(){
    std::vector<int> v1{1,2};
    reset(v1);
    std::cout << v1.size() << std::endl;
    
    int a = 1;
    reset(a);//constraints not satisfied  
    return 0;
}

检查运算符

template<typename T>
requires requires(T a, T b) {
    { a + b } -> std::convertible_to<T>;  // 必须支持 + 运算且返回 T
}
T add(T a, T b) {
    return a + b;
}

Alias Template

template <typename T>
class MyContainer{
	......
}

template<typename T>
using MyIterator = typename MyContainer<T>::iterator;//需要指明typename

MyIterator<int> pos;

Nontype Template Parameters

模板参数不一定是type,也可以是constant integral values

#include<iostream>
#include<array>
#include<cassert>

template <typename T, int MaxSize>
class myStack{
private:
    std::array<T,MaxSize> elem;
    int num;

public:
    myStack();
    
    void push(const T& _elem);

    void pop();

    T top();

    int size();


};

template<typename T, int MaxSize>
myStack<T,MaxSize>::myStack(): num(0){}

template<typename T, int MaxSize>
void myStack<T,MaxSize>::push(const T& _elem){
    assert(num < MaxSize);
    elem[num++] = _elem;
}


template<typename T, int MaxSize>
void myStack<T, MaxSize>::pop(){
    assert(num>0);
    --num;
}

template<typename T, int MaxSize>
int myStack<T, MaxSize>::size(){
    return num;
}

template<typename T, int MaxSize>
T myStack<T, MaxSize>::top(){
    assert(num > 0);
    return elem[num-1];
}

Variadic Templates

通过variadic Templates实现可变参数:

#include<iostream>

void print(){}

template <typename T, typename... Types>
void print(T first, Types... args){
    
    std::cout << first << std::endl;
    print(args...);
}

int main(){
    print(1, 2.0, "Hello");
}

注意:要在模板前定义一个终止函数void print(){},否则模板展开时会反复调用print(arg...)导致爆栈。

实现and_all:

#include<iostream>


bool and_all(){
    return true;
}

template<typename T>
bool and_all(T one){
    return one;
}

template <typename T, typename... Types>
bool and_all(T first, Types... args){
    return first && and_all(args...);   
}

int main(){
    std::cout << and_all(1,1,1,1,1,0) << std::endl;
    std::cout << and_all(1) << std::endl;
}

Fold Expressions

折叠类型 语法 展开示例(参数包为 a, b, c)
一元左折叠 ( ... op args ) ((a op b) op c)
一元右折叠 ( args op ... ) (a op (b op c))
二元左折叠 ( init op ... op args ) (((init op a) op b) op c)
二元右折叠 ( args op ... op init ) (a op (b op (c op init)))
#include<iostream>

template <typename... Types>
bool and_all(Types... args){
    return (args && ...);   
}

template<typename... Types>
auto add_all(Types... args){
    return (0 + ... + args);// 而且括号不能少,不能写成0 + ... + args
}
int main(){
    std::cout << and_all(1,1,1,1,1,0) << std::endl;   
    std::cout << add_all(1, 3.14, 2u) << std::endl;
}
  • 不能写成 return (args + ...); 防止无参数调用,例如add_all()

  • 括号不能少,不能写成return 0 + ... + args

  • (0 + ... + args) 就是( init op ... op args ) 的形式

#include<iostream>

template <typename... Types>
void print_all(Types... args){
    
    ( (std::cout << args << "\n"), ... );   
}
int main(){
    print_all(1, "hello", 3.14, "world");
    
}
1
hello
3.14
world
  • ( (std::cout << args << "\n"), ... ) 是一元右折叠表达式.

args拼成了一个新的new_args = (std::cout << args << "\n"),new_args中有四个变量,分别是(std::cout << 1 << "\n"), (std::cout << "hello" << "\n"), (std::cout << 3.14 << "\n"), (std::cout << "world" << "\n")

  • (new_args , ...) 一元右折叠,op = ,
#include<iostream>

template <typename T1, typename... TN>
constexpr bool isHomogeneous(T1, TN...){//可以省略参数名
    return (std::is_same<T1,TN>::value && ...);
}
int main(){    
    std::cout << isHomogeneous(1, 2 , "hello") << std::endl;
    
    std::cout << isHomogeneous(1, 2 , 3) << std::endl;
}

Generic Template Parameter & Reference Collasing & Perfect Forwarding

add_all这样写更好:

#include<iostream>

template <typename... Args>
auto add_all(Args&&... args){
       return (0 + ... + std::forward<Args>(args));
}

int main(){ 
    int x = 6;
    std::cout << add_all(1, x, 2, 3.14, 'a') << std::endl;
}
  • Generic Template Parameter:使用Args&&...能够同时处理lvalue和rvalue
  • Reference Collasing: int&&&等价于int&, int&&&& -> int&&
  • Perfect Forwarding: 完美转发,不改变左值右值属性

当add_all被传入rvalue例如3.14时,Args推断为float, 完美转发后为float&& 3.14

当add_all被传入lvalue例如x时,Args推断为int&, 完美转发后为int&&& x = int& x

一个使用完美转发前后的性能对比实验:link

typename keyword

#include<iostream>
#include<string>
#include<vector>
#include<tuple>
// print elements of an STL container

template<typename T>
void printcoll (T const& coll){
    typename T::const_iterator pos;
    typename T::const_iterator end(coll.end());// end position

    for(pos = coll.begin(); pos != end; ++pos){
        std::cout << *pos << std::endl;
    }
}
int main(){
    std::vector<int> v1{1, 2, 3};
    std::vector<std::string> v2{"hello", "world"};   
    
    printcoll(v1);
    printcoll(v2);
}

Disable Templates with enable_if_t<>

语法:

template <typename T>
std::enable_if_v< bool_expr, type >  foo(){
    
}
  • 如果bool_expr为真,函数foo的返回值为type

  • 如果bool_expr为假,则foo不完成实例

  • type缺省为void

#include <iostream>
#include <type_traits>

// 整数打印
template<typename T>
std::enable_if_t<std::is_integral_v<T>, void>
    print(T value) {
        std::cout << "Integer: " << value << std::endl;
    }

// 浮点数打印
template<typename T>
    std::enable_if_t<std::is_floating_point_v<T>, void>
    print(T value) {
        std::cout << "Floating: " << value << std::endl;
    }

int main() {
    print(42);       // Integer
    print(3.14f);    // Floating
    print("hello"); // no matching function
    return 0;
}

可以使用默认模板参数+enable_if_t来对模板参数进行约束:

#include <type_traits>

template<typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
void foo() {
    std::cout << "T is integral" << std::endl;
}
int main() {
    foo<int>();    // ✅ 编译通过
    foo<double>(); // ❌ 编译失败(SFINAE 排除此版本)
    return 0;
}
  • 第一个模板参数是T,第二个模板参数typename = std::enable_if_t<std::is_integral_v<T>> , 通过第二个模板参数的推导来限制第一个模板参数T的类型
  • 如果T是整数类型,模板展开为
tempalte<typename T, typename = void>

第二个模板参数用不上,只是为了去约束T的。

concept

个人觉得concept相较于enable_if更加简洁清晰。但是concept在C++20进入标准,可能老代码还是得用enable_if.

template<typename STR>
requires std::is_convertible_v<STR,std::string>

PerSon(STR&& n):name(std::forward<STR>(n)) {
......
}