Black Eye Galaxy

Google C++风格指南

发表于 2021-03-24 更新于 2023-06-18 分类于 C++ 阅读次数： Valine：

头文件

self-contained头文件

头文件需要自给自足，头文件本身应当是能编译的（个人理解时在没有源文件.cxx的情况也能编译通过）。

头文件应当用#define保护，并包含其所需要的所有其他头文件。

模板和内联函数的定义和声明应当处于同一文件内。

define保护

所有头文件都应该使用#define防止文件被多重包含，并且为了保证唯一性，宏命名应当基于所在项目源码的全路径，格式应当为<PROJECT>_<PATH>_<FILE>_H_。

引入所有使用的头文件

不要依赖于include传递，如果foo.cxx文件使用了bar.h中的符号，就应当在foo.cxx中引入bar.h，即使在bar.h已经引入了。

也就是说，尽量在源文件中引入库，而不是在对应的头文件中引入，目的是为了减少引入依赖。例如当A.cxx依赖于B.h时，对B.h的任何修改都会导致A.cxx的重新构建，而此时B.cxx依赖于C.h，那么我们现在有两个选择，一是在B.cxx中引入C.h，二是在B.h中引入C.h。若选择第二种，我们对C.h的任何修改都会导致A.cxx的重新构建，若选择第一种，则不会触发A.cxx的重新构建。

前置声明

前置声明是指类、函数和模板不带有定义的纯粹声明，应当避免使用前置声明，将声明放在头文件中，然后#include。

优点
- 前置声明能够节省编译时间。
- 前置声明能节省不必要的重新编译时间，使用#include会使得代码由于头文件中无关改动而被重新编译。
缺点
- 前置声明隐藏依赖关系，头文件改动时，源文件会跳过必要的重新编译过程。
- 前置声明可能被库的后续更改所破坏。
- 前置声明来自std::中的符号时，行为未定义。
- 前置声明甚至会改变代码含义。
- 重构代码更为复杂和困难。

内联函数

经验：
- 只有函数不多于10行时才将其定义为内联函数
- 不要内联包含循环和switch的函数
- 不要内联递归函数
- 即使声明为内联函数，编译器也不一定会接受
- 类声明内定义的函数默认为内联函数

include的路径和顺序

避免使用.和..，按照项目源码路径完整include。

内联顺序：
1. 同名头文件
2. C系统文件
3. C++系统文件
4. 其他库.h
5. 本项目.h

这种优先顺序保证了当.h文件遗漏某些库时，源文件的构建会立刻终止。

不同类型的头文件空格分隔。

例外情况，条件编译绝对是否引入库，如不同平台。

作用域

命名空间

C++中的全局函数和全局变量的作用域是整个项目，为了限制其作用域，一种做法是使用static关键字修饰，另一种是使用命名空间。

在不需要外部访问的情况下，C++标准提倡使用匿名命名空间，禁止使用using引入命名空间，禁止使用内联命名空间。

namespace X{
    inline namespace Y{
        void foo();
    }
}

// 别名
namespace baz = ::foo::bar::baz;

在内联命名空间中，X::Y::foo()与X::foo()等价，其目的主要是用来兼容跨版本API。

命名空间使用策略：

遵循命名空间命名规范
命名空间结束时，使用注释
命名空间应当在头文件、gflag声明与定义、其他空间的类前置声明之后
禁止在std内声明任何东西，属于未定义行为，导致不可移植
禁止在头文件中使用命名空间别名，除非限制在内部命名空间中使用
禁止使用using引入命名空间
禁止使用内联命名空间

匿名命名空间与静态变量

在cxx中定义不需要被外部引用的符号时，可以放在匿名命名空间或声明为static，但不要在头文件中这样做。

非成员函数、静态成员函数、全局函数

使用静态成员或命名空间内的非成员函数，不要使用裸的全局函数，不要用类的静态方法模拟命名空间效果，类的静态方法应当与类的实例或静态数据密切相关。

非成员函数置于命名空间避免污染全局作用域。

局部变量

将函数变量尽可能放在最小作用域内，在变量声明时进行初始化。

除非变量是一个对象，每次进入作用域都需要调用构造函数，退出作用域调用析构函数。

静态和全局变量

静态生存周期的对象，包括全局变量、静态变量、静态类成员、函数静态变量，必须是原生数据类型(POD, Plain Old Data)。

在多编译单元中，静态变量的构造、析构和初始化顺序在C++中只有部分是明确的，甚至随着构建发生变化，导致难以发现的bug，禁止使用类的静态存储周期变量。

在同一编译单元中顺序是明确的，静态初始化优于动态初始化、初始化顺序按照声明顺序进行，逆序销毁，不同编译单元内，属于未明确行为。

多线程时，静态生存周期不要使用非POD的对象以及STL容器。

类

构造函数

不要在构造函数中调用虚函数，也不要在无法报错时进行可能失败的初始化。

构造函数内调用自身的虚函数并不会重定向到子类的虚函数实现。

如果执行失败，可能会得到一个初始化失败的对象，这个对象可能无法进入到正常状态。

如果对象需要进行初始化，通过定义Init()方法或工厂方法进行创建并初始化。

隐式类型转换

一脸懵比

可拷贝类型和可移动类型

如果不需要，禁用隐式生成的拷贝和移动构造函数。

结构体/类

仅当只有数据成员和重载运算符时使用struct，其他一概使用class。

TODO

函数

参数顺序

输入参数在前，输出参数在后。

简短函数

优先编写简短函数，若行数超过四十行考虑分离。

引用参数

引用必须用const，对变量进行修改传指针。除非特殊要求，如swap()。

函数重载

函数重载尽量能够简单明了，尽量不要改变相同数量的参数类型来进行重载。可以考虑在函数名中加入类型信息。

缺省参数

只允许在非虚函数中使用缺省参数，尽可能使用函数重载而非缺省参数。

优点：

降低代码量，降低代码修改时的工作量，函数重载需要修改多个函数。

缺点：

虚函数调用的缺省参数取决于目标对象的静态类型，无法保证给定函数的所有重载声明的都是同样的缺省参数。
缺省参数会干扰函数指针，导致函数签名与调用点签名不一致。
缺省参数每次调用都需要重新求值,导致生成的代码膨胀。

函数返回类型后置语法

只有常规写法不便于书写或阅读时才使用返回类型后置语法。

1 2	int foo(int x); auto foo(int x) -> int;

优点：

后置返回类型是显示指定Lambda表达式返回值类型的唯一方式，通常情况下编译器能够自动推导出Lambda表达式的返回类型，但并不是所有情况。

缺点：

陌生，与原始代码看起来不协调（黑人问号？）

G式奇淫技巧

所有权与智能指针

C++11后时代C++程序员的常识题，不要使用std::auto_ptr，使用std::unique_ptr或std::shared_ptr，倾向于前者。

Cpplint

风格检查cpplint.py

命名规范

通用命名规则

描述性命名，如果你也曾被前人项目中的缩写整懵比那就少用缩写，如果实在需要，请在声明位置加注释。

文件命名

全部小写，下划线_连接。不要与/usr/include下的文件重名。

内联函数放在.h文件中。

类型命名

类、结构体、类型定义、枚举、类型模板参数。每个单词首字母大写，不应包含下划线。

变量命名

变量与数据成员一律小写，单词之间用下划线连接，类的成员变量用下划线结尾，结构体变量与普通变量一致，无需加下划线。

常量命名

声明为constexpr和const的变量，或在程序运行i期间其值始终保持不变的以k开头，大小写混合。

函数命名

常规函数大小写混合，取值或设值要求与变量名匹配，如set_num()，get_num()。

对于函数名中出现的单词缩写倾向于全部用大写StartRPC()。

命名空间命名

命名空间以小写字母命名，最高级命名空间取决于项目名称或团队名，避免嵌套命名空间与上层命名空间之间存在冲突。

命名空间中的代码，应当存放于与命名空间的名字匹配的文件夹或其子文件夹中。

不要使用缩写。

枚举命名

枚举命名与常量或宏保持一致kEnumName、ENUM_NAME。优先采用常量命名方式。

宏命名

参见不要用宏，如果不得不适用，全部大写，下划线连接。

注释风格

项目统一风格//或/* */

写好TODO、FIX、DEPRECATED

我是不可能写注释的，告辞

attribute那些事

发表于 2021-03-24 更新于 2023-06-18 阅读次数： Valine：

C++宏定义的那些事

发表于 2021-03-23 更新于 2023-06-18 分类于 C++相关阅读次数： Valine：

宏定义

宏定义将一个标识符定义为一个字符串，源代码中的标识符将被指定的字符串替换，这个过程发生在预处理阶段。
发方
C++程序的完整编译过程包括预处理、编译、汇编、链接四个步骤。其中预处理阶段进行宏展开、条件编译等。

在C语言中，通过宏来定义简单函数，可以降低函数调用过程中的开销，而在c++中，可以用inline来声明内联函数来降低函数调用过程的开销。

也可以通过宏来定义一些常量，但由于宏替换发生在预处理阶段，因此如果在编译过程中产生错误，很难进行错误的定位和溯源。

简单的宏定义

//第一种
#define PI2 3.1415926
#define Add(x) x+1 //错误示范
#define Double(x) (x*2) //错误示范
// Add(x) * 2 ==> x + 1 * 2
#define Add(x) ((x)+1)
#define Double(x) ((x)*2)


//第二种
#ifndef SOURCE_H
#define SOURCE_H

#define TEST
#ifdef TEST
std::cout << "this is a TEST " << endl;
#ifndef TEST
std::cout << "there are not TEST" << endl;
#endif

宏的两种简单用法如上所示，第一种用法将PI全部替换为3.1415926，这里的替换是直接展开的，如错误示范中所示，因此我们在使用宏定义时，要利用括号保证其在展开时不会产生错误。

第二种用法通过宏定义来实现条件编译、避免头文件的重复引入。

宏的高阶用法

#、##、#@三种可以称之为宏的高阶用法，可以实现许多高级特性。

#define STRING(msg) #msg
char* str = "hello";
char* str = STRING(hello);  //二者等价


#define CHAR(ch) #@ch
char ch = 'a';
char ch = CHAR(a); //二者等价

#define

当宏中遇到#和##时，是不能够进行嵌套替换的，不会对#和##之后宏进行展开。

可变参数宏

#define VARGS_(_10, _9, _8, _7, _6, _5, _4, _3, _2, _1, N, ...) N
#define VARGS(...) VARGS_(__VA_ARGS__, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)


#define CONCAT_(a, b) a ### b
#define CONCAT(a, b) CONCAT_(a, b) // 由于##会阻止宏的展开，因此两次宏替换解决宏的嵌套问题

#define FUNC_3(prefix, name, n) func(prefix, name, n)
#define FUNC_2(prefix, name) FUNC_3(prefix, name, 1)

#define FUNC(...) CONCAT("FUNC_", VARGS(__VA_ARGS__))(__VA_ARGS__)


// 从而实现如下变参宏
FUNC(prefix, name, 4)
FUNC(prefix, name)

工厂宏

class Any {
public:
    Any() : _var_ptr(NULL) {}
    template<typename T>
    Any(const T& value) : _var_ptr(new Type<T>(value)) {}
    Any(const Any& other) : _var_ptr(other._var_ptr ? other._var_ptr->clone() : NULL) {}
    ~Any() {
        delete _var_ptr;
    }
    template<typename T>
    T* any_cast() {
        return _var_ptr ? &static_cast<Type <T>*>(_var_ptr)->_var : NULL;
    }

private:
    class Typeless {
    public:
        virtual ~Typeless() {}
        virtual Typeless* clone() const = 0;
    };
    /// @brief Type calss template to hold a specific type
    template<typename T>
    class Type : public Typeless {
    public:
        explicit Type(const T& value) : _var(value) {}
        virtual Typeless* clone() const {
            return new Type(_var);
        }
        T _var;             ///< The real variable of a specific type
    };
    Typeless* _var_ptr;     ///< Typeless variable pointer
};

struct ConcreteFactory {
    typedef Any (* FactoryIntf)();  /// a Function Pointer 

    FactoryIntf get_instance;      ///< Function pointer to get instance
    FactoryIntf get_singleton;     ///< Function pointer to get singleton
};

typedef std::map<std::string, ConcreteFactory> FactoryMap;
typedef std::map<std::string, FactoryMap> BaseClassMap;

BaseClassMap& g_factory_map() {
    static BaseClassMap base_class_map;    
    return base_class_map;
}

#define REGISTER_FACTORY(base_class) \
    class base_class ### Factory { \
    public: \
        static base_class *get_instance(const ::std::string &name) { \
            FactoryMap &map = g_factory_map()[#base_class]; \
            FactoryMap::iterator iter = map.find(name); \
            if (iter == map.end()) { \
                return NULL; \
            } \
            Any object = iter->second.get_instance(); \
            return *(object.any_cast<base_class*>()); \
        } \
        static base_class* get_singleton(const ::std::string& name) { \
            FactoryMap& map = g_factory_map()[#base_class]; \
            FactoryMap::iterator iter = map.find(name); \
            if (iter == map.end()) { \
                return NULL; \
            }\
            Any object = iter->second.get_singleton(); \
            return *(object.any_cast<base_class*>()); \
        } \
        static const ::std::string get_uniq_instance_name() { \
            FactoryMap &map = g_factory_map()[#base_class]; \
            if (map.empty() || map.size() != 1) { \
                return ""; \
            } \
            return map.begin()->first; \
        } \
        static base_class *get_uniq_instance() { \
            FactoryMap &map = g_factory_map()[#base_class]; \
            if (map.empty() || map.size() != 1) { \
                return NULL; \
            } \
            Any object = map.begin()->second.get_instance(); \
            return *(object.any_cast<base_class*>()); \
        } \
        static bool is_valid(const ::std::string &name) { \
            FactoryMap &map = g_factory_map()[#base_class]; \
            return map.find(name) != map.end(); \
        } \
        static std::vector<std::string> list_class() {\
            std::vector<std::string> ret; \
            auto &m = g_factory_map()[#base_class]; \
            for (auto& iter : m) { \
              ret.emplace_back(iter.first);\
            }\
            return ret;\
        }\
    }; \


#define REGISTER_CLASS(base_class, sub_class) \
    namespace { \
    Any sub_class##get_instance() { \
        return Any(new sub_class()); \
    } \
    Any sub_class##get_singleton() { \
        return Any(Singleton<sub_class>::get()); \
    } \
    __attribute__((constructor)) void register_factory_##sub_class() { \
        FactoryMap &map = g_factory_map()[#base_class]; \
        if (map.find(#sub_class) == map.end()) { \
            ConcreteFactory factory = {&sub_class##get_instance, \
                                                 &sub_class##get_singleton}; \
            map[#sub_class] = factory; \
        } \
    } \
    }

1	typedef char (*func)(int); //函数指针

tf serving源码阅读

发表于 2021-03-21 更新于 2023-06-18 分类于源码阅读阅读次数： Valine：

TF-Serving简介

TensorFlow Serving是一个用于在生产环境中部署机器学习模型的应用系统，原生集成了TensorFlow模型，也可以扩展以应用其他类型的模型和数据。

TF-Serving架构

Servables
Loaders
Sources
Managers
Core

Servable

Servable是TF-Serving核心的对模型的抽象，Servable的大小和粒度都很灵活，任何能提供算法或数据查询的实体都可以抽象为Servable，服务可以是任何类型和接口。Servable不负责管理自己的生命周期，而是交由Manager管理。

典型的Servables包括：

TesnorFlow SavedModelBundle
Embeddings查找表或词查找表

Servable相关的数据结构

tensorflow.serving.ServableId

struct ServableId{
    string name;
    int64 version;
    string DebugString(){}
};

tensorflow.serving.ServableData

template<typename T>
class ServableData{
public:
    ServableData(const ServableId&, T data);
    T& DataorDie();
    T ConsumeDataorDie();
private:
    ServableData()=delete;
    const ServableId id_;
    const Status status_;
    T data_;
};

tensorflow.serving.ServableHandle

class UntypedServableHandle{
public:
    virtual const ServableId& id()const = 0;
    virtual AnyPtr servable()=0;
};

template <typename T>
class ServableHandle{
public:
    const ServableId& id() const {return untyped_handle_->id();}
    T& operator*() const {return *get();}
    T* operator->() const {return get();}
    T* get() const {return servalbe_;}
private:
    friend class Manager;
    std::unique_ptr<UntypedServableHandle> Untyped_handle_;
    T* servable_ = nullptr;
};

class SharedPtrHandle: public UntypedServableHandle{
public:
    ~SharedPtrHandle() override = default;
    explicit SharedPtrHandle(const ServableId& id, std::shared_ptr<Loader> loader)
        : id_(id), loader_(std::move(loader)) {}
    AnyPtr servable() override { return loader_->servable(); }
    const ServableId& id() const override { return id_; }

private:
    const ServableId id_;
    std::shared_ptr<Loader> loader_;
};

tensorflow.serving.ServableState

struct ServableState{
    ServableId id;
    enum class ManagerState : int {
        kStart, kLoading, kAvailable, kUnloading, kEnd,
    };
    static string ManagerStateString(ManagerState state){...}
    MangerState manager_state;
    Status health;
    string DebugString() const {...}
};

Loader

Loader对Servable的生命周期进行控制，包括load/unload接口、资源预估接口等，加载后的Servable也存在Loader里面。Loader也用于扩展算法和数据后端（Tensorflow是其中一种）。当我们要添加一个新的backends时（如Pytorch等），需要为其实现一个新的Loader，以用于加载、卸载模型。

//表示一个从storage加载的一个SavedModel
class SavedModelBundleInterface{
public:
    virtual ~SavedModelBundleInterface();
    virtual Session* GetSession()=0;
    virtual const protobuf::Map<string, SignatureDef>& GetSignatures()=0;
};

struct SavedModelBundle: public SavedModelBundleInterface{
    ~SavedModelBundle();
    SavedModelBundle();
    Session* GetSession(){return session.get();}
    protobuf::Map<string, SignatureDef>& GetSignatures(){return meta_graph_def.signature_der();}

    std::unique_ptr<Session> session;
    MetaGraphDef meta_graph_def;
    std::unique_ptr<GraphDebugInfo> debug_info;
};

LoaderHarness

LoaderHarness是对Loader的封装，LoaderHarness负提供Loader的状态跟踪，ServingMap和ManagedMap里面保存的都是LoaderHarness对象，只有通过LoaderHarness才能访问Loader的接口。

Source

Source是对Servable的来源的抽象，Source监控外部资源，发现新的模型版本，并通知Target。Source为其提供的Servable的每个可用版本都提供一个Loader实例。

Source可以是：

文件系统，本地或者HDFS
RPC

template<typename T>
class Source{
public:
    virtual ~Source() = default;
    using AspiredVersionsCallback = std::function<void(
      const StringPiece servable_name, std::vector<ServableData<T>> versions)>;
    // 提供要使用的AspiredVersionCallback
    virtual void SetAspiredVersionsCallback(AspiredVersionsCallback callback)=0;
};

class StaticStoragePathSource : public Source<StoragePath>{
public:
    static Status Create(const StaticStoragePathSourceConfig& config,   std::unique_ptr<StaticStoragePathSource>* result){
        auto raw_result = new StaticStoragePathSource;
        raw_result->config_ = config;
        result->reset(raw_result);
        return Status::Ok();
    }
    ~StaticStoragePathSource() override = default;
    void SetAspiredVersionsCallback(AspiredVersionsCallback callback){
        const ServableId id = {config_.servable_name(), config_.version_num()};
        LOG(INFO) << "Aspiring servable" << id;
        callback(configt_.servable_name(), {CreateServableData(id, confg_.version_path())});
    }
private:
    StaticStoragePathSource() = default;
    StaticStoragePathSourceConfig config_;
    TF_DISALLOW_COPY_AND_ASSIGN(StaticStoragePathSource);
};


class FileSystemStoragePathSource : public Source<StoragePath>{
public:
    static Status Create(const FileSystemStoragePathSourceConfig& config, std::unique_ptr<FileSystemStoragePathSource>* result);
    
    ~FileSystemStoragePathSource() override;
    Status UpdateConfig(const FileSystemStoragePathSourceConfig& config);

    void SetAspiredVersionsCallback(AspiredVersionCallback callback) override;

    FileSystemStoragePathSource config() const{
        mutex_lock l(mu_);
        return config_;
    }
private:
    friend class internal::FileSystemStoragePathSourceTestAccess;
    FileSystemStoragePathSource() = default;

    Status PollFileSystemAndInvokeCallback();

    Status UnaspireServables(const std::set<string>& servable_name) TF_EXCLUSIVE_LOCKS_REQUIRED(mu_);

    template<typename... Args>
    void CallAspiredVersionsCallback(Args&&... args){
        ...;
    }
    void SetAspiredVersionsCallbackNotifier(std::function<void()> fn) {
    mutex_lock l(mu_);
    aspired_versions_callback_notifier_ = fn;
    }

    mutable mutex mu_;
    FileSystemStoragePathSourceConfig config TF_GUARDED_BY(mu_);
    AspiredVersionsCallback aspired_versions_callback_ TF_GUARDED_BY(mu_);
    std::function<void()> aspired_versions_callback_notifier_ TF_GUARDED_BY(mu_);
    using ThreadType = absl::variant<absl::monostate, PeriodicFunction, std::unique_ptr<Thread>>;
    std::unique_ptr<ThreadType> fs_polling_thread_ TF_GUARDED_BY(mu_);
    TF_DISALLOW_COPY_AND_ASSIGN(FileSystemStoragePathSource);
}

Adapter

Adapter是为了Source转成Loader而引入的抽象，这样server core的实现和具体的平台解耦，server core只需要调用LoaderHarness中的方法管理Servable（访问、加载、卸载等）。

SourceRouter

Adapter是平台相关的，每个平台一个Adapter，这里的平台指的是TF、Pytorch等。而Source是与Servable相关的，这样在Adapter和Source之间存在一对多的关系，Router负责维护这些对应关系。（这里似乎有些问题，需要仔细看下）

ServerCore

服务系统的创建和维护，建立HTTP REST Server、GRPC Server和模型管理部分(AspiredVersionManger)之间的关系。

AspiredVersionManager

模型管理的上层控制部分，负责执行Source发出的模型管理指令，一部分通过回调的方式由Source调用，一部分由独立线程执行。

BasicManager

负责Servable的管理，包括加载、卸载、状态查询、资源跟踪，对外提供如下接口：

ManageServable
LoadServable
UnloadServable
StopManagerServable

提供接口查询servableHandle(GetUntypeServableHandle)，也就是加载好的模型，供http rest或grpc server调用进行推理。

所有受管理的servable都放在ManagedMap里，已经正常加载的servable同时也放在ServingMap进行管理，提供查询接口。

Target

Target是和Source对应的抽象概念，AspiredVersionManager、Router都是Target。

模型加载

tensorflow_serving/model_servers/BUILD中配置，可知，tensorflow_model_server的入口位于tensorflow_serving/model_servers/main.cc

大致流程

int main(int argc, char** argv){
    Options option;
    vector<Flag> flag_list;
    // cmd_line可以指定单个模型，多个模型需要配置config_file
    usage = Flags::Usage(argv[0], flag_list);
    // Usage 使用命令行cmdline返回用法消息，并返回标志flag_list中的用法文本字符串。
    Flags::Parse(&argc, argv, flag_list);
    // Parser 解析cmdline输入参数
    port::InitMain(argv[0], &argc, &argv);
    // InitMain 实现为空，我瞎了？？？？
    Server server;
    status = server.BuildAndStart(options);
    server.WaitForTermination();
    return 0;
}

BuildAndStart(options){
    SOME_CHECK_AND_PROCESS(options);
    ServerCore::Create(move(options), &server_core_);
    ::grpc::ServerBuilder builder;
    builder.AddListeningPort();
    builder.RegeisterService(xxx);
    //注册服务，model_service/prediction_service/profiler_service
    grpc_server = builder.BuildAndStart();
    // 启动grpc服务 
    return ;
}
Status ServerCore::Create(Options options, ServerCore* servercore){
    options.servable_state_monitor_creator;
    ServerRequestLogger::Create(nullptr, options.server_request_logger);
    aspired_version_policy = move(options.aspired_version_policy);
    server_core.reset(new ServerCore(move(options)));
    (*server_core)->Initialize(std::move(aspired_version_policy));
    return (*server_core)->ReloadConfig(model_server_config);
    // ReloadConfig 加载模型
}

Initialize(){
    
}

Status ServerCore::ReloadConfig(ModelServerConfig& new_config){
    mutex_lock l(config_mu);
}

Trie树

发表于 2021-03-21 更新于 2023-06-18 分类于算法，数据结构阅读次数： Valine：

Trie树的定义

Trie树，又被称为字典树、单词查找树，是一种哈希树变种。常用于统计、排序和保存大量的字符串，如搜索引擎系统中的文本词频统计、拼写的智能补全、字符串排序、最长公共前缀等。优点在于，利用字符串的公共前缀减少查询时间，查找效率比哈希树高。

Trie树的实现

Trie树结构

对于Trie树的每一个节点，应当有一个标志位表示从根节点到当前节点的字符串是否存在，每个节点应当有26个儿子节点（与字符数量相同）。

class TrieNode{
private:
    bool isEnd;
    TrieNode* next[26];
public:
    void TrieNode();
    void insert(string str);
    bool search(string str);
    bool startWith(string prefix);
}

Init

初始化一个Trie树，树的根节点应为空。

void TrieNode(){
    isEnd = false;
    memset(next, 0, sizeof(next));
}

Insert

void insert(string str){
    Trie* node = this;
    for(char ch: str){
        if(node->next[ch-'a'] == nullptr)
            node->next[ch-'a'] = new Trie();
        node = node->next[ch-'a'];
    }
    node->isEnd = true;
}

Search

bool search(string str){
    Trie* node = this;
    for(char ch: str){
        node = node->next[ch-'a'];
        if(node == nullptr)
            return false;
    }
    return node->isEnd;
}

StartWith

bool StartWith(string str){
    Trie* node = this;
    for(char ch: str){
        node = node->next[ch-'a'];
        if(node == nullptr)
            return false;
    }
    return true;
}

哈希树

哈希树（HashTree）是一种持久性数据结构，用于实现集合和映射。通过质数分辨法建立哈希树，从第二层开始，每层的节点数为连续质数(2,3,5,7…)，从左至右分别为对于该质数的余数。