之前做的项目，我就把总结相关的东西复制过来，偏面试向

字典树原理

leetcode简单的字典树实现

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Trie {
public:
    vector<Trie*> children;
    bool isEnd;
    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

    Trie(): children(26), isEnd(false) {

    }
    
    void insert(string word) {
        Trie* node = this;
        for(auto ch:word){
            ch-='a';
            if(node->children[ch]==nullptr){
                node->children[ch]=new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }
    
    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};

具体的代码本系列都不讲，就突出一个面向面试

C++11特性

因为字典树这块用了不少C++11的新语法，这里介绍一下比较经典的

智能指针

介绍智能指针之前我们先介绍一下RALL，智能指针是为了RALL服务的

RALL

RAII（Resource Acquisition Is Initialization）是一种利用对象生命周期来控制程序资源（如内存、文件句柄、网络连接、互斥量等等）的简单技术。

在对象构造时获取资源，接着控制对资源的访问使之在对象的生命周期内始终保持有效，最后在对象析构的时候释放资源。借此，我们实际上把管理一份资源的责任托管给了一个对象。这种做法有两大好处：

• 不需要显式释放资源
• 所需资源在其生命周期内始终保持有效

概念

在c++中，动态内存的管理式通过一对运算符来完成的：

new,在动态内存中为对象分配空间并返回一个指向该对象的指针，我们可以选择对对象进行初始化；

delete，接受一个动态对象的指针，销毁该对象，并释放与之关联的内存。

动态内存的使用很容易出现问题，因为确保在正确的时间释放内存是极其困难的。有时使用完对象后，忘记释放内存，造成内存泄漏的问题。

所谓的智能指针本质就是一个类模板，它可以创建任意的类型的指针对象，当智能指针对象使用完后，对象就会自动调用析构函数去释放该指针所指向的空间

实现

下面是智能指针的基本框架，所有的智能指针类模板中都需要包含一个指针对象，构造函数和析构函数。

当程序结束时，此时ptr1和ptr2指针被销毁时，对象ptr1和ptr2会自动调用析构函数去释放所指向的资源，这是智能指针特点。

C++库中的智能指针

auto_ptr

auto_ptr是c++98版本库中提供的智能指针，该指针解决上诉的问题采取的措施是管理权转移的思想，也就是原对象拷贝给新对象的时候，原对象就会被设置为nullptr，此时就只有新对象指向一块资源空间。

如果auto_ptr调用拷贝构造函数或者赋值重载函数后，如果再去使用原来的对象的话，那么整个程序就会崩溃掉（因为原来的对象被设置为nullptr)，这对程序是有很大的伤害的.所以很多公司会禁用auto_ptr智能指针。

unique_ptr

unique_ptr是c++11版本库中提供的智能指针,它直接将拷贝构造函数和赋值重载函数给禁用掉，因此，不让其进行拷贝和赋值。

shared_ptr

share_ptr是c++11版本库中的智能指针，shared_ptr允许多个智能指针可以指向同一块资源，并且能够保证共享的资源只会被释放一次，因此是程序不会崩溃掉。

原理：

shared_ptr采用的是引用计数原理来实现多个shared_ptr对象之间共享资源：

• shared_ptr在内部会维护着一份引用计数，用来记录该份资源被几个对象共享。
• 当一个shared_ptr对象被销毁时（调用析构函数），析构函数内就会将该计数减1。
• 如果引用计数减为0后，则表示自己是最后一个使用该资源的shared_ptr对象，必须释放资源。
• 如果引用计数不是0，就说明自己还有其他对象在使用，则不能释放该资源，否则其他对象就成为野指针。

weak_ptr 和shared_ptr的循环引用问题

上网查一下

右值引用

C++11新增了右值引用，我们这里可以扩展相关概念

左值右值

概念1

左值：可以放在等号左边的叫左值

右值：不可以放在等号左边的叫右值

概念2

左值：可以取地址并且有名字的东西就是左值。

右值：不能取地址的没有名字的东西就是右值。

举例：

1

int a = b + c; 

a为左值，(b + c)为右值

左值一般有：

• 函数名和变量名
• 返回左值引用的函数调用
• 前置自增自减表达式++i、—i
• 由赋值表达式或赋值运算符连接的表达式(a=b, a += b等)
• 解引用表达式*p

纯右值、将亡值

纯右值

运算表达式产生的临时变量、不和对象关联的原始字面量、非引用返回的临时变量、lambda表达式等都是纯右值。

• 除字符串字面值外的字面值
• 返回非引用类型的函数调用
• 后置自增自减表达式i++、i—
• 算术表达式(a+b, a*b, a&&b, a==b等)
• 取地址表达式等(&a)

将亡值

将亡值是指C++11新增的和右值引用相关的表达式，通常指将要被移动的对象、T&&函数的返回值、std::move函数的返回值、转换为T&&类型转换函数的返回值，将亡值可以理解为即将要销毁的值，通过“盗取”其它变量内存空间方式获取的值，在确保其它变量不再被使用或者即将被销毁时，可以避免内存空间的释放和分配，延长变量值的生命周期，常用来完成移动构造或者移动赋值的特殊任务。

左值引用、右值引用

根据名字大概就可以猜到意思，左值引用就是对左值进行引用的类型，右值引用就是对右值进行引用的类型，他们都是引用，都是对象的一个别名，并不拥有所绑定对象的堆存，所以都必须立即初始化。

1
2

type &name = exp; // 左值引用
type &&name = exp; // 右值引用

左值引用

1
2
3
4
5

int a = 5;
int &b = a; // b是左值引用
b = 4;
int &c = 10; // error，10无法取地址，无法进行引用
const int &d = 10; // ok，因为是常引用，引用常量数字，这个常量数字会存储在内存中，可以取地址

可以得出结论：对于左值引用，等号右边的值必须可以取地址，如果不能取地址，则会编译失败，或者可以使用const引用形式，但这样就只能通过引用来读取输出，不能修改数据，因为是常量引用。

右值引用

1
2
3

int a = 4;
int &&b = a; // error, a是左值
int &&c = std::move(a); // ok

如果使用右值引用，那表达式等号右边的值需要时右值，可以使用std::move函数强制把左值转换为右值。

移动语义

深拷贝 浅拷贝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class A {
public:
    A(int size) : size_(size) {
        data_ = new int[size];
    }
    A(){}
    A(const A& a) {
        size_ = a.size_;
        data_ = a.data_;
        cout << "copy " << endl;
    }
    ~A() {
        delete[] data_;
    }
    int *data_;
    int size_;
};
int main() {
    A a(10);
    A b = a;
    cout << "b " << b.data_ << endl;
    cout << "a " << a.data_ << endl;
    return 0;
}

上面代码中，两个输出的是相同的地址，a和b的data_指针指向了同一块内存，这就是浅拷贝，析构时data内存会被释放两次，会崩溃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class A {
public:
    A(int size) : size_(size) {
        data_ = new int[size];
    }
    A(){}
    A(const A& a) {
        size_ = a.size_;
        data_ = new int[size_];
        // need memcpy
        cout << "copy " << endl;
    }
    ~A() {
        delete[] data_;
    }
    int *data_;
    int size_;
};
int main() {
    A a(10);
    A b = a;
    cout << "b " << b.data_ << endl;
    cout << "a " << a.data_ << endl;
    return 0;
}

深拷贝就是再拷贝对象时，如果被拷贝对象内部还有指针引用指向其它资源，自己需要重新开辟一块新内存存储资源，而不是简单的赋值。

移动语义

移动语义，可以理解为转移所有权，之前的拷贝是对于别人的资源，自己重新分配一块内存存储复制过来的资源，而对于移动语义，类似于转让或者资源窃取的意思，对于那块资源，转为自己所拥有，别人不再拥有也不会再使用，通过C++11新增的移动语义可以省去很多拷贝负担，怎么利用移动语义呢，是通过移动构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class A {
public:
    A(int size) : size_(size) {
        data_ = new int[size];
    }
    A(){}
    A(const A& a) {
        size_ = a.size_;
        data_ = new int[size_];
        // need memcpy
        cout << "copy " << endl;
    }
    A(A&& a) {
        this->data_ = a.data_;
        a.data_ = nullptr;
        cout << "move " << endl;
    }
    ~A() {
        if (data_ != nullptr) {
            delete[] data_;
        }
    }
    int *data_;
    int size_;
};
int main() {
    A a(10);
    A b = a;
    A c = std::move(a); // 调用移动构造函数
    return 0;
}

完美转发

完美转发指可以写一个接受任意实参的函数模板，并转发到其它函数，目标函数会收到与转发函数完全相同的实参，转发函数实参是左值那目标函数实参也是左值，转发函数实参是右值那目标函数实参也是右值。那如何实现完美转发呢，答案是使用std::forward()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void PrintV(int &t) {
    cout << "lvalue" << endl;
}

void PrintV(int &&t) {
    cout << "rvalue" << endl;
}

template<typename T>
void Test(T &&t) {
    PrintV(t);
    PrintV(std::forward<T>(t));

    PrintV(std::move(t));
}

int main() {
    Test(1); // lvalue rvalue rvalue
    int a = 1;
    Test(a); // lvalue lvalue rvalue
    Test(std::forward<int>(a)); // lvalue rvalue rvalue
    Test(std::forward<int&>(a)); // lvalue lvalue rvalue
    Test(std::forward<int&&>(a)); // lvalue rvalue rvalue
    return 0;
}

• Test(1)：1是右值，模板中T &&t这种为万能引用，右值1传到Test函数中变成了右值引用，但是调用PrintV()时候，t变成了左值，因为它变成了一个拥有名字的变量，所以打印lvalue，而PrintV(std::forward(t))时候，会进行完美转发，按照原来的类型转发，所以打印rvalue，PrintV(std::move(t))毫无疑问会打印rvalue。
• Test(a)：a是左值，模板中T &&这种为万能引用，左值a传到Test函数中变成了左值引用，所以有代码中打印。
• Test(std::forward(a))：转发为左值还是右值，依赖于T，T是左值那就转发为左值，T是右值那就转发为右值。