高级农民
- 积分
- 2737
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-6-18
- 最后登录
- 1970-1-1
|
最近终于有空把这个坑填上...
这个题目主要难度在于:
(1) 怎么在编译时记录每个TreeNode的每个member信息
(2) 怎么根据所记录的信息去生成对应的代码去处理各个member
处理(1)和(2)的技术一般称为模板元编程(template metaprogramming)
对于(1)来说,有两种可选方案:
(1.a) 使用C++提供的std::tuple作为载体
(1.b) 自己写一个可变长编译时数组(数组元素类型为"C++类型")作为载体 —— 这种数组一般被称为TypeList
对于(2)来说,我们需要根据采集的TreeNode的信息在Codec类内"注入"对应于不同member类型的序列化函数,这一"注入"一般有两种处理方式:
(2.a) 模板参数化多继承,也叫做Policy-based design,结合CRTP(curiously recurring template pattern)使用
(2.b) 借助TypeList提供的一些便利,用expression SFINAE
下面是一份参考代码,用了(1.b) + (2.b)
- #include <cstddef>
- #include <cstdint>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <string>
- #include <vector>
- namespace meta {
- // TypeList: 编译时可变长数组,其元素为"C++类型"
- template <typename ...Ts> struct TypeList;
- // IntegerSequence: 编译时可变长数组,其元素为整数
- template <std::size_t ...s> struct IntegerSequence;
- } // namespace meta
- ////////////////////////////////////////////////////////////////////////////////
- ///////////////////////////////////// Macros ///////////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- #define M_L meta::TypeList
- #define M_S meta::IntegerSequence
- #define M_D(t,x) decltype(t::x)
- #define M_O(t,x) offsetof(t,x)
- #define ENTRY_A(T,a) \
- M_L<T,M_L<M_D(T,a)>, \
- M_S<M_O(T,a)>>
- #define ENTRY_B(T,a,b) \
- M_L<T,M_L<M_D(T,a),M_D(T,b)>, \
- M_S<M_O(T,a),M_O(T,b)>>
- #define ENTRY_C(T,a,b,c) \
- M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c)>, \
- M_S<M_O(T,a),M_O(T,b),M_O(T,c)>>
- #define ENTRY_D(T,a,b,c,d) \
- M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c),M_D(T,d)>, \
- M_S<M_O(T,a),M_O(T,b),M_O(T,c),M_O(T,d)>>
- #define ENTRY_E(T,a,b,c,d,e) \
- M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c),M_D(T,d),M_D(T,e)>, \
- M_S<M_O(T,a),M_O(T,b),M_O(T,c),M_O(T,d),M_O(T,e)>>
- #define ENTRY_F(T,a,b,c,d,e,f) \
- M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c),M_D(T,d),M_D(T,e),M_D(T,f)>, \
- M_S<M_O(T,a),M_O(T,b),M_O(T,c),M_O(T,d),M_O(T,e),M_O(T,f)>>
- #define ENTRY_G(T,a,b,c,d,e,f,g) \
- M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c),M_D(T,d),M_D(T,e),M_D(T,f),M_D(T,g)>, \
- M_S<M_O(T,a),M_O(T,b),M_O(T,c),M_O(T,d),M_O(T,e),M_O(T,f),M_O(T,g)>>
- #define ENTRY_H(T,a,b,c,d,e,f,g,h) \
- M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c),M_D(T,d),M_D(T,e),M_D(T,f),M_D(T,g),M_D(T,h)>, \
- M_S<M_O(T,a),M_O(T,b),M_O(T,c),M_O(T,d),M_O(T,e),M_O(T,f),M_O(T,g),M_O(T,h)>>
- #define M_GET(_T,_a,_b,_c,_d,_e,_f,_g,_h,NAME,...) NAME
- // 用于获取一个TreeNode的每个member的类型(decltype)与位移量(offsetof)信息
- // 并将这些信息打包为一个TypeList
- #define ENTRY(...) \
- M_GET(__VA_ARGS__, \
- ENTYR_H,ENTRY_G,ENTRY_F,ENTRY_E, \
- ENTRY_D,ENTRY_C,ENTRY_B,ENTRY_A)(__VA_ARGS__)
- ////////////////////////////////////////////////////////////////////////////////
- /////////////////////////////// Codec Synthesizer //////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- // 用于选出对应于NodeType的TreeNode信息
- template <typename NodeType>
- struct MetaInfoSelector {
- template <typename MetaInfo>
- using type = std::is_same<typename MetaInfo::head, NodeType>;
- };
- // 用于合并一个TreeNode内每个member的decltype和offsetof信息
- template <typename MetaInfo>
- struct MetaInfoZipper {
- using Ts = typename MetaInfo::template at<1>;
- using Os = typename MetaInfo::template at<2>
- ::template bind_to<meta::TypeList>;
- using type = meta::TypeList<typename MetaInfo::head,
- typename Ts::template zip<Os>>;
- };
- template <typename ...MetaInfo>
- class CodecSynthesizer {
- private:
- // 所有TreeNode的信息放在一个TypeList里
- using MetaInfoTable = typename meta::TypeList<MetaInfo...>
- ::template map<MetaInfoZipper>;
- using TopLevelNode = typename MetaInfoTable::head::head;
- public:
- // Encodes a tree to a single string.
- std::string serialize(const TopLevelNode* root) const {
- std::string data;
- serialize(root, &data);
- return data;
- }
- // Decodes your encoded data to tree.
- TopLevelNode* deserialize(const std::string &data) {
- const char *it = data.c_str();
- return deserialize<TopLevelNode>(&it);
- }
- private:
- // 序列化:如果当前member是基础类型(例如int),那么直接取underlying bytes
- template <typename FieldType>
- void serializeField(const FieldType *field, std::string *data,
- std::enable_if_t<std::is_pod<FieldType>::value &&
- !std::is_pointer<FieldType>::value> * = 0) const {
- data->append(reinterpret_cast<const char*>(field), sizeof(FieldType));
- }
- // 序列化:如果当前member是指针类型,那么递归序列化其指向的object
- template <typename FieldType>
- void serializeField(const FieldType *field, std::string *data,
- std::enable_if_t<std::is_pod<FieldType>::value &&
- std::is_pointer<FieldType>::value> * = 0) const {
- if (*field == nullptr) {
- data->push_back(0);
- } else {
- data->push_back(1);
- serialize(*field, data);
- }
- }
- // 序列化:如果当前member是string类型,那么取其长度信息与具体数据
- template <typename FieldType>
- void serializeField(const FieldType *field, std::string *data,
- std::enable_if_t<std::is_same<FieldType, std::string>::value> * = 0) const {
- const std::size_t len = field->length();
- data->append(reinterpret_cast<const char*>(&len), sizeof(len));
- data->append(field->c_str(), len);
- }
- // 递归展开并序列化一个TreeNode所打包的所有member信息
- template <typename Fields>
- void serializeFieldList(const void *node, std::string *data,
- std::enable_if_t<Fields::length != 0> * = 0) const {
- using FieldInfo = typename Fields::head;
- using FieldType = typename FieldInfo::head;
- const FieldType *field = reinterpret_cast<const FieldType*>(
- reinterpret_cast<const char*>(node) + FieldInfo::tail::head::value);
- serializeField<FieldType>(field, data);
- serializeFieldList<typename Fields::tail>(node, data);
- }
- // 递归展开终止
- template <typename Fields>
- void serializeFieldList(const void *node, std::string *data,
- std::enable_if_t<Fields::length == 0> * = 0) const {
- // NO-OP
- }
- // 序列化一个TreeNode的入口函数
- template <typename Node>
- void serialize(const Node *node, std::string *data) const {
- using Fields = typename MetaInfoTable::template filter<MetaInfoSelector<Node>::template type>
- ::head::template at<1>;
- serializeFieldList<Fields>(node, data);
- }
- // 反序列化:与序列化类似,根据member类型分情况处理
- template <typename FieldType>
- void deserializeField(FieldType *field, const char **data,
- std::enable_if_t<std::is_pod<FieldType>::value &&
- !std::is_pointer<FieldType>::value> * = 0) const {
- const char *&it = *data;
- std::memcpy(field, it, sizeof(FieldType));
- it += sizeof(FieldType);
- }
- template <typename FieldType>
- void deserializeField(FieldType *field, const char **data,
- std::enable_if_t<std::is_pod<FieldType>::value &&
- std::is_pointer<FieldType>::value> * = 0) const {
- const char *&it = *data;
- if (*it++ == 0) {
- *field = nullptr;
- } else {
- *field = deserialize<typename std::remove_pointer<FieldType>::type>(data);
- }
- }
- template <typename FieldType>
- void deserializeField(FieldType *field, const char **data,
- std::enable_if_t<std::is_same<FieldType, std::string>::value> * = 0) const {
- const char *&it = *data;
- std::size_t len;
- std::memcpy(&len, it, sizeof(len));
- it += sizeof(len);
- new (field) std::string(it, len);
- it += len;
- }
- template <typename Fields>
- void deserializeFieldList(void *node, const char **data,
- std::enable_if_t<Fields::length != 0> * = 0) const {
- using FieldInfo = typename Fields::head;
- using FieldType = typename FieldInfo::head;
- FieldType *field = reinterpret_cast<FieldType*>(
- reinterpret_cast<char*>(node) + FieldInfo::tail::head::value);
- deserializeField<FieldType>(field, data);
- deserializeFieldList<typename Fields::tail>(node, data);
- }
- template <typename Fields>
- void deserializeFieldList(void *node, const char **data,
- std::enable_if_t<Fields::length == 0> * = 0) const {
- // NO-OP
- }
- // 反序列化一个TreeNode的入口函数
- template <typename Node>
- Node* deserialize(const char **data) const {
- using Fields = typename MetaInfoTable::template filter<MetaInfoSelector<Node>::template type>
- ::head::template at<1>;
- // NOTE: It requires extra handling of constructors to use "new" operator.
- Node *node = static_cast<Node*>(std::malloc(sizeof(Node)));
- deserializeFieldList<Fields>(node, data);
- return node;
- }
- };
- ////////////////////////////////////////////////////////////////////////////////
- ////////////////////////// TypeList的一个minimal实现 /////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- namespace meta {
- template <std::size_t ...s>
- struct IntegerSequence {
- template <template <typename ...> class Host>
- using bind_to = Host<std::integral_constant<std::size_t, s>...>;
- };
- template <typename ...Ts>
- struct TypeList;
- namespace internal {
- using EmptyList = TypeList<>;
- // ---------------------------------------------------------------------------
- // TypeList meta functions.
- // TypeList::at
- template <typename TL, typename PosTL, typename Enable = void>
- struct ElementAtImpl;
- template <typename TL, typename PosTL>
- struct ElementAtImpl<TL, PosTL, std::enable_if_t<PosTL::length == 0>> {
- using type = TL;
- };
- template <typename TL, typename PosTL>
- struct ElementAtImpl<TL, PosTL, std::enable_if_t<PosTL::length != 0>>
- : ElementAtImpl<typename std::tuple_element<
- PosTL::head::value,
- typename TL::template bind_to<std::tuple>>::type,
- typename PosTL::tail> {};
- // TypeList::filter
- template <typename Out, typename Rest, template <typename ...> class Op,
- typename Enable = void>
- struct FilterImpl;
- template <typename Out, typename Rest, template <typename ...> class Op>
- struct FilterImpl<Out, Rest, Op, std::enable_if_t<Rest::length == 0>> {
- using type = Out;
- };
- template <typename Out, typename Rest, template <typename ...> class Op>
- struct FilterImpl<Out, Rest, Op, std::enable_if_t<Op<typename Rest::head>::value>>
- : FilterImpl<typename Out::template push_back<typename Rest::head>,
- typename Rest::tail, Op> {};
- template <typename Out, typename Rest, template <typename ...> class Op>
- struct FilterImpl<Out, Rest, Op, std::enable_if_t<!Op<typename Rest::head>::value>>
- : FilterImpl<Out, typename Rest::tail, Op> {};
- // TypeList::zip
- template <typename Out, typename RestL, typename RestR, typename Enable = void>
- struct ZipImpl;
- template <typename Out, typename RestL, typename RestR>
- struct ZipImpl<Out, RestL, RestR,
- std::enable_if_t<RestL::length == 0 || RestR::length == 0>> {
- static_assert(RestL::length == 0 && RestR::length == 0,
- "Zip failed: TypeLists have unequal lengths");
- using type = Out;
- };
- template <typename Out, typename RestL, typename RestR>
- struct ZipImpl<Out, RestL, RestR,
- std::enable_if_t<RestL::length != 0 && RestR::length != 0>>
- : ZipImpl<typename Out::template push_back<
- TypeList<typename RestL::head, typename RestR::head>>,
- typename RestL::tail, typename RestR::tail> {};
- // ---------------------------------------------------------------------------
- // End of meta functions.
- template <typename ...Ts>
- struct TypeListBase {
- static constexpr std::size_t length = sizeof...(Ts);
- using type = TypeList<Ts...>;
- using self = type;
- // ---------------------------------------------------------------------------
- // Meta-methods.
- template <template <typename ...> class Host>
- using bind_to = Host<Ts...>;
- template <std::size_t ...pos>
- using at = typename ElementAtImpl<
- self, TypeList<std::integral_constant<std::size_t, pos>...>>::type;
- template <typename T>
- using push_back = TypeList<Ts..., T>;
- template <template <typename ...> class Op>
- using map = TypeList<typename Op<Ts>::type...>;
- template <template <typename ...> class Op>
- using filter = typename FilterImpl<EmptyList, self, Op>::type;
- template <typename TL>
- using zip = typename ZipImpl<EmptyList, self, TL>::type;
- };
- } // namespace internal
- template <typename T, typename ...Ts>
- struct TypeList<T, Ts...> : public internal::TypeListBase<T, Ts...> {
- public:
- using head = T;
- using tail = TypeList<Ts...>;
- };
- template <>
- struct TypeList<> : public internal::TypeListBase<> {};
- } // namespace meta
- ////////////////////////////////////////////////////////////////////////////////
- ///////////////////////////// 测试数据:三种TreeNode /////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- struct TreeNodeA;
- struct TreeNodeB;
- struct TreeNodeC;
- struct TreeNodeA {
- int x, y;
- TreeNodeB *left;
- TreeNodeC *right;
- TreeNodeA(const int xi, const int yi)
- : x(xi), y(yi), left(nullptr), right(nullptr) {}
- };
- struct TreeNodeB {
- double x;
- TreeNodeB *next;
- TreeNodeB(const double xi)
- : x(xi), next(nullptr) {}
- };
- struct TreeNodeC {
- std::string x, y;
- TreeNodeA *left;
- TreeNodeA *right;
- TreeNodeC(const std::string &xi, const std::string &yi)
- : x(xi), y(yi), left(nullptr), right(nullptr) {}
- };
- // 用于验证结果的Print函数
- void Print(TreeNodeA *node, const int indent);
- void Print(TreeNodeB *node, const int indent);
- void Print(TreeNodeC *node, const int indent);
- std::string Spaces(const int n) {
- return std::string(n, ' ');
- }
- void Print(TreeNodeA *node, const int indent) {
- std::cout << Spaces(indent) << "TreeNodeA("
- << node->x << "," << node->y << ")\n";
- std::cout << Spaces(indent) << "left = \n";
- if (node->left != nullptr) {
- Print(node->left, indent + 2);
- }
- std::cout << Spaces(indent) << "right = \n";
- if (node->right != nullptr) {
- Print(node->right, indent + 2);
- }
- }
- void Print(TreeNodeB *node, const int indent) {
- std::cout << Spaces(indent) << "TreeNodeB(" << node->x << ")\n";
- std::cout << Spaces(indent) << "next = \n";
- if (node->next != nullptr) {
- Print(node->next, indent + 2);
- }
- }
- void Print(TreeNodeC *node, const int indent) {
- std::cout << Spaces(indent) << "TreeNodeC("
- << node->x << "," << node->y << ")\n";
- std::cout << Spaces(indent) << "left = \n";
- if (node->left != nullptr) {
- Print(node->left, indent + 2);
- }
- std::cout << Spaces(indent) << "right = \n";
- if (node->right != nullptr) {
- Print(node->right, indent + 2);
- }
- }
- ////////////////////////////////////////////////////////////////////////////////
- ////////////////////////// 使用CodecSynthesizer生成Codec ////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- using Codec = CodecSynthesizer<ENTRY(TreeNodeA, x, y, left, right),
- ENTRY(TreeNodeB, x, next),
- ENTRY(TreeNodeC, x, y, left, right)>;
- ////////////////////////////////////////////////////////////////////////////////
- ///////////////////////////////////// main函数 //////////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- int main(int argc, char *argv[]) {
- TreeNodeA *a = new TreeNodeA(1, 2);
- TreeNodeB *b1 = new TreeNodeB(0.1);
- TreeNodeB *b2 = new TreeNodeB(0.2);
- b1->next = b2;
- TreeNodeB *b3 = new TreeNodeB(0.3);
- TreeNodeA *aa = new TreeNodeA(3, 4);
- aa->left = b3;
- TreeNodeC *c = new TreeNodeC("hello", "world");
- c->left = aa;
- a->left = b1;
- a->right = c;
- Codec codec;
- std::string data = codec.serialize(a);
- std::cout << "data length = " << data.length() << "\n\n";
- TreeNodeA *result = codec.deserialize(data);
- Print(result, 0);
- return 0;
- }
复制代码 |
|