📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4623| 回复: 13
跳转到指定楼层
上一主题 下一主题
收起左侧

一道比较高级的C++题目

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
这个题目是最近遇到的一些问题加上LeetCode 297合成而来的,觉得很有挑战性也能提升不少的C++能力,所以分享一下...

首先基础题目LC 297叫做“Serialize and Deserialize Binary Tree”,具体内容在这里:
https://leetcode.com/problems/se ... y-tree/description/

原题是要serialize/deserialize一个树结构,它对树节点的定义是:
  1. struct TreeNode {
  2.   int val;
  3.   TreeNode *left;
  4.   TreeNode *right;
  5. };
复制代码
原题就不仔细说了。现在,如果稍微增加一点难度的话,我们可以将题目改为有多种树节点,每个节点存储不同的信息,例如:
  1. struct TreeNodeX;
  2. struct TreeNodeY;

  3. struct TreeNode {
  4.   int val;
  5.   TreeNodeX *left;
  6.   TreeNodeY *right;
  7. };

  8. struct TreeNodeX {
  9.   double val1;
  10.   int val2, val3;
  11.   TreeNodeX *left;
  12.   TreeNodeY *mid;
  13.   TreeNodeX *right;
  14. };

  15. struct TreeNodeY {
  16.   std::string val;
  17.   TreeNode *left;
  18.   TreeNode *right;
  19. };
复制代码
然后给定TreeNode *root,要求写一个Codec类可以serialize/deserialize这个root。

以上仅仅是增加一些实现上的复杂度,并不是很特别.. 但是注意到一个问题:对于各种不同的TreeNode定义,我们都需要重写一份(很长的)Codec代码。


现在是题目中比较“高级”的部分了——我们需要提供一个模板库,对于任意树节点的组合,用户只需要几行代码,就可以自动生成用于serialize/deserialize的Codec类。

也就是说,我们希望类似如下的一行代码即可生成LC 297的Codec类:
  1. using Codec = MakeCodec<ENTRY<TreeNode, val, left, right>>;
复制代码
而对于上面稍微复杂一点的有TreeNode,TreeNodeX,TreeNodeY三个类的情况,希望类似如下的三行代码即可生成对应的Codec类:
  1. using Codec = MakeCodec<ENTRY<TreeNode, val, left, right>,
  2.                         ENTRY<TreeNodeX, val1, val2, val3, left, mid, right>,
  3.                         ENTRY<TreeNodeY, val, left, right>>;
复制代码
注意到这里的MakeCodec/ENTRY只是一种可能的模板接口,也可以有其它的方案。

其它:
1. 为了限制复杂性,我们假定每个TreeNode里的member只可能是int,double,string或是其它TreeNode的指针,然后member个数不超过8个。
2. 对于C++版本没有要求,也可以使用第三方库例如boost/folly,不过C++11其实就已经可以了。
3. 不可以修改各个TreeNode本身的定义,例如在里面加一些method什么的(LeetCode做题时也是不可以修改TreeNode定义的)。
4. 题目的难度主要在于C++没有动态反射,所以需要在编译时生成处理所有TreeNode的所有member的代码。

评分

参与人数 1大米 +5 收起 理由
cynthiazhxu + 5 给你点个赞!

查看全部评分


上一篇:LeetCode前400题总结
下一篇:Facebook面筋问题!!!

本帖被以下淘专辑推荐:

  • · CS|主题: 243, 订阅: 30
推荐
 楼主| magicsets 2017-12-8 04:50:11 | 只看该作者
全局:
最近终于有空把这个坑填上...

这个题目主要难度在于:
(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)

  1. #include <cstddef>
  2. #include <cstdint>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <string>
  7. #include <vector>

  8. namespace meta {

  9. // TypeList: 编译时可变长数组,其元素为"C++类型"
  10. template <typename ...Ts> struct TypeList;

  11. // IntegerSequence: 编译时可变长数组,其元素为整数
  12. template <std::size_t ...s> struct IntegerSequence;

  13. }  // namespace meta

  14. ////////////////////////////////////////////////////////////////////////////////
  15. ///////////////////////////////////// Macros ///////////////////////////////////
  16. ////////////////////////////////////////////////////////////////////////////////

  17. #define M_L meta::TypeList
  18. #define M_S meta::IntegerSequence
  19. #define M_D(t,x) decltype(t::x)
  20. #define M_O(t,x) offsetof(t,x)

  21. #define ENTRY_A(T,a) \
  22.   M_L<T,M_L<M_D(T,a)>, \
  23.         M_S<M_O(T,a)>>

  24. #define ENTRY_B(T,a,b) \
  25.   M_L<T,M_L<M_D(T,a),M_D(T,b)>, \
  26.         M_S<M_O(T,a),M_O(T,b)>>

  27. #define ENTRY_C(T,a,b,c) \
  28.   M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c)>, \
  29.         M_S<M_O(T,a),M_O(T,b),M_O(T,c)>>

  30. #define ENTRY_D(T,a,b,c,d) \
  31.   M_L<T,M_L<M_D(T,a),M_D(T,b),M_D(T,c),M_D(T,d)>, \
  32.             M_S<M_O(T,a),M_O(T,b),M_O(T,c),M_O(T,d)>>

  33. #define ENTRY_E(T,a,b,c,d,e) \
  34.   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)>, \
  35.         M_S<M_O(T,a),M_O(T,b),M_O(T,c),M_O(T,d),M_O(T,e)>>

  36. #define ENTRY_F(T,a,b,c,d,e,f) \
  37.   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)>, \
  38.         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)>>

  39. #define ENTRY_G(T,a,b,c,d,e,f,g) \
  40.   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)>, \
  41.         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)>>

  42. #define ENTRY_H(T,a,b,c,d,e,f,g,h) \
  43.   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)>, \
  44.         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)>>


  45. #define M_GET(_T,_a,_b,_c,_d,_e,_f,_g,_h,NAME,...) NAME

  46. // 用于获取一个TreeNode的每个member的类型(decltype)与位移量(offsetof)信息
  47. // 并将这些信息打包为一个TypeList
  48. #define ENTRY(...) \
  49.   M_GET(__VA_ARGS__, \
  50.         ENTYR_H,ENTRY_G,ENTRY_F,ENTRY_E, \
  51.         ENTRY_D,ENTRY_C,ENTRY_B,ENTRY_A)(__VA_ARGS__)


  52. ////////////////////////////////////////////////////////////////////////////////
  53. /////////////////////////////// Codec Synthesizer //////////////////////////////
  54. ////////////////////////////////////////////////////////////////////////////////

  55. // 用于选出对应于NodeType的TreeNode信息
  56. template <typename NodeType>
  57. struct MetaInfoSelector {
  58.   template <typename MetaInfo>
  59.   using type = std::is_same<typename MetaInfo::head, NodeType>;
  60. };

  61. // 用于合并一个TreeNode内每个member的decltype和offsetof信息
  62. template <typename MetaInfo>
  63. struct MetaInfoZipper {
  64.   using Ts = typename MetaInfo::template at<1>;
  65.   using Os = typename MetaInfo::template at<2>
  66.                               ::template bind_to<meta::TypeList>;
  67.   using type = meta::TypeList<typename MetaInfo::head,
  68.                               typename Ts::template zip<Os>>;
  69. };

  70. template <typename ...MetaInfo>
  71. class CodecSynthesizer {
  72. private:
  73.   // 所有TreeNode的信息放在一个TypeList里
  74.   using MetaInfoTable = typename meta::TypeList<MetaInfo...>
  75.                                      ::template map<MetaInfoZipper>;
  76.   using TopLevelNode = typename MetaInfoTable::head::head;

  77. public:
  78.   // Encodes a tree to a single string.
  79.   std::string serialize(const TopLevelNode* root) const {
  80.     std::string data;
  81.     serialize(root, &data);
  82.     return data;
  83.   }

  84.   // Decodes your encoded data to tree.
  85.   TopLevelNode* deserialize(const std::string &data) {
  86.     const char *it = data.c_str();
  87.     return deserialize<TopLevelNode>(&it);
  88.   }

  89. private:
  90.   // 序列化:如果当前member是基础类型(例如int),那么直接取underlying bytes
  91.   template <typename FieldType>
  92.   void serializeField(const FieldType *field, std::string *data,
  93.                       std::enable_if_t<std::is_pod<FieldType>::value &&
  94.                                        !std::is_pointer<FieldType>::value> * = 0) const {
  95.     data->append(reinterpret_cast<const char*>(field), sizeof(FieldType));
  96.   }

  97.   // 序列化:如果当前member是指针类型,那么递归序列化其指向的object
  98.   template <typename FieldType>
  99.   void serializeField(const FieldType *field, std::string *data,
  100.                       std::enable_if_t<std::is_pod<FieldType>::value &&
  101.                                        std::is_pointer<FieldType>::value> * = 0) const {
  102.     if (*field == nullptr) {
  103.       data->push_back(0);
  104.     } else {
  105.       data->push_back(1);
  106.       serialize(*field, data);
  107.     }
  108.   }

  109.   // 序列化:如果当前member是string类型,那么取其长度信息与具体数据
  110.   template <typename FieldType>
  111.   void serializeField(const FieldType *field, std::string *data,
  112.                       std::enable_if_t<std::is_same<FieldType, std::string>::value> * = 0) const {
  113.     const std::size_t len = field->length();
  114.     data->append(reinterpret_cast<const char*>(&len), sizeof(len));
  115.     data->append(field->c_str(), len);
  116.   }

  117.   // 递归展开并序列化一个TreeNode所打包的所有member信息
  118.   template <typename Fields>
  119.   void serializeFieldList(const void *node, std::string *data,
  120.                           std::enable_if_t<Fields::length != 0> * = 0) const {
  121.     using FieldInfo = typename Fields::head;
  122.     using FieldType = typename FieldInfo::head;
  123.     const FieldType *field = reinterpret_cast<const FieldType*>(
  124.         reinterpret_cast<const char*>(node) + FieldInfo::tail::head::value);
  125.     serializeField<FieldType>(field, data);
  126.     serializeFieldList<typename Fields::tail>(node, data);
  127.   }

  128.   // 递归展开终止
  129.   template <typename Fields>
  130.   void serializeFieldList(const void *node, std::string *data,
  131.                           std::enable_if_t<Fields::length == 0> * = 0) const {
  132.     // NO-OP
  133.   }

  134.   // 序列化一个TreeNode的入口函数
  135.   template <typename Node>
  136.   void serialize(const Node *node, std::string *data) const {
  137.     using Fields = typename MetaInfoTable::template filter<MetaInfoSelector<Node>::template type>
  138.                                          ::head::template at<1>;
  139.     serializeFieldList<Fields>(node, data);
  140.   }

  141.   // 反序列化:与序列化类似,根据member类型分情况处理
  142.   template <typename FieldType>
  143.   void deserializeField(FieldType *field, const char **data,
  144.                         std::enable_if_t<std::is_pod<FieldType>::value &&
  145.                                          !std::is_pointer<FieldType>::value> * = 0) const {
  146.     const char *&it = *data;
  147.     std::memcpy(field, it, sizeof(FieldType));
  148.     it += sizeof(FieldType);
  149.   }

  150.   template <typename FieldType>
  151.   void deserializeField(FieldType *field, const char **data,
  152.                         std::enable_if_t<std::is_pod<FieldType>::value &&
  153.                                          std::is_pointer<FieldType>::value> * = 0) const {
  154.     const char *&it = *data;
  155.     if (*it++ == 0) {
  156.       *field = nullptr;
  157.     } else {
  158.       *field = deserialize<typename std::remove_pointer<FieldType>::type>(data);
  159.     }
  160.   }

  161.   template <typename FieldType>
  162.   void deserializeField(FieldType *field, const char **data,
  163.                         std::enable_if_t<std::is_same<FieldType, std::string>::value> * = 0) const {
  164.     const char *&it = *data;
  165.     std::size_t len;
  166.     std::memcpy(&len, it, sizeof(len));
  167.     it += sizeof(len);
  168.     new (field) std::string(it, len);
  169.     it += len;
  170.   }

  171.   template <typename Fields>
  172.   void deserializeFieldList(void *node, const char **data,
  173.                             std::enable_if_t<Fields::length != 0> * = 0) const {
  174.     using FieldInfo = typename Fields::head;
  175.     using FieldType = typename FieldInfo::head;
  176.     FieldType *field = reinterpret_cast<FieldType*>(
  177.         reinterpret_cast<char*>(node) + FieldInfo::tail::head::value);
  178.     deserializeField<FieldType>(field, data);
  179.     deserializeFieldList<typename Fields::tail>(node, data);
  180.   }

  181.   template <typename Fields>
  182.   void deserializeFieldList(void *node, const char **data,
  183.                             std::enable_if_t<Fields::length == 0> * = 0) const {
  184.     // NO-OP
  185.   }

  186.   // 反序列化一个TreeNode的入口函数
  187.   template <typename Node>
  188.   Node* deserialize(const char **data) const {
  189.     using Fields = typename MetaInfoTable::template filter<MetaInfoSelector<Node>::template type>
  190.                                          ::head::template at<1>;
  191.     // NOTE: It requires extra handling of constructors to use "new" operator.
  192.     Node *node = static_cast<Node*>(std::malloc(sizeof(Node)));
  193.     deserializeFieldList<Fields>(node, data);
  194.     return node;
  195.   }
  196. };


  197. ////////////////////////////////////////////////////////////////////////////////
  198. ////////////////////////// TypeList的一个minimal实现 /////////////////////////////
  199. ////////////////////////////////////////////////////////////////////////////////

  200. namespace meta {

  201. template <std::size_t ...s>
  202. struct IntegerSequence {
  203.   template <template <typename ...> class Host>
  204.   using bind_to = Host<std::integral_constant<std::size_t, s>...>;
  205. };

  206. template <typename ...Ts>
  207. struct TypeList;

  208. namespace internal {

  209. using EmptyList = TypeList<>;

  210. // ---------------------------------------------------------------------------
  211. // TypeList meta functions.

  212. // TypeList::at
  213. template <typename TL, typename PosTL, typename Enable = void>
  214. struct ElementAtImpl;

  215. template <typename TL, typename PosTL>
  216. struct ElementAtImpl<TL, PosTL, std::enable_if_t<PosTL::length == 0>> {
  217.   using type = TL;
  218. };

  219. template <typename TL, typename PosTL>
  220. struct ElementAtImpl<TL, PosTL, std::enable_if_t<PosTL::length != 0>>
  221.     : ElementAtImpl<typename std::tuple_element<
  222.                         PosTL::head::value,
  223.                         typename TL::template bind_to<std::tuple>>::type,
  224.                     typename PosTL::tail> {};

  225. // TypeList::filter
  226. template <typename Out, typename Rest, template <typename ...> class Op,
  227.           typename Enable = void>
  228. struct FilterImpl;

  229. template <typename Out, typename Rest, template <typename ...> class Op>
  230. struct FilterImpl<Out, Rest, Op, std::enable_if_t<Rest::length == 0>> {
  231.   using type = Out;
  232. };

  233. template <typename Out, typename Rest, template <typename ...> class Op>
  234. struct FilterImpl<Out, Rest, Op, std::enable_if_t<Op<typename Rest::head>::value>>
  235.     : FilterImpl<typename Out::template push_back<typename Rest::head>,
  236.                  typename Rest::tail, Op> {};

  237. template <typename Out, typename Rest, template <typename ...> class Op>
  238. struct FilterImpl<Out, Rest, Op, std::enable_if_t<!Op<typename Rest::head>::value>>
  239.     : FilterImpl<Out, typename Rest::tail, Op> {};

  240. // TypeList::zip
  241. template <typename Out, typename RestL, typename RestR, typename Enable = void>
  242. struct ZipImpl;

  243. template <typename Out, typename RestL, typename RestR>
  244. struct ZipImpl<Out, RestL, RestR,
  245.                std::enable_if_t<RestL::length == 0 || RestR::length == 0>> {
  246.   static_assert(RestL::length == 0 && RestR::length == 0,
  247.                 "Zip failed: TypeLists have unequal lengths");
  248.   using type = Out;
  249. };

  250. template <typename Out, typename RestL, typename RestR>
  251. struct ZipImpl<Out, RestL, RestR,
  252.                std::enable_if_t<RestL::length != 0 && RestR::length != 0>>
  253.     : ZipImpl<typename Out::template push_back<
  254.                   TypeList<typename RestL::head, typename RestR::head>>,
  255.               typename RestL::tail, typename RestR::tail> {};

  256. // ---------------------------------------------------------------------------
  257. // End of meta functions.

  258. template <typename ...Ts>
  259. struct TypeListBase {
  260.   static constexpr std::size_t length = sizeof...(Ts);

  261.   using type = TypeList<Ts...>;
  262.   using self = type;

  263.   // ---------------------------------------------------------------------------
  264.   // Meta-methods.

  265.   template <template <typename ...> class Host>
  266.   using bind_to = Host<Ts...>;

  267.   template <std::size_t ...pos>
  268.   using at = typename ElementAtImpl<
  269.       self, TypeList<std::integral_constant<std::size_t, pos>...>>::type;

  270.   template <typename T>
  271.   using push_back = TypeList<Ts..., T>;

  272.   template <template <typename ...> class Op>
  273.   using map = TypeList<typename Op<Ts>::type...>;

  274.   template <template <typename ...> class Op>
  275.   using filter = typename FilterImpl<EmptyList, self, Op>::type;

  276.   template <typename TL>
  277.   using zip = typename ZipImpl<EmptyList, self, TL>::type;
  278. };

  279. }  // namespace internal

  280. template <typename T, typename ...Ts>
  281. struct TypeList<T, Ts...> : public internal::TypeListBase<T, Ts...> {
  282. public:
  283.   using head = T;
  284.   using tail = TypeList<Ts...>;
  285. };

  286. template <>
  287. struct TypeList<> : public internal::TypeListBase<> {};

  288. }  // namespace meta



  289. ////////////////////////////////////////////////////////////////////////////////
  290. ///////////////////////////// 测试数据:三种TreeNode /////////////////////////////
  291. ////////////////////////////////////////////////////////////////////////////////

  292. struct TreeNodeA;
  293. struct TreeNodeB;
  294. struct TreeNodeC;

  295. struct TreeNodeA {
  296.   int x, y;
  297.   TreeNodeB *left;
  298.   TreeNodeC *right;
  299.   TreeNodeA(const int xi, const int yi)
  300.       : x(xi), y(yi), left(nullptr), right(nullptr) {}
  301. };

  302. struct TreeNodeB {
  303.   double x;
  304.   TreeNodeB *next;
  305.   TreeNodeB(const double xi)
  306.       : x(xi), next(nullptr) {}
  307. };

  308. struct TreeNodeC {
  309.   std::string x, y;
  310.   TreeNodeA *left;
  311.   TreeNodeA *right;
  312.   TreeNodeC(const std::string &xi, const std::string &yi)
  313.       : x(xi), y(yi), left(nullptr), right(nullptr) {}
  314. };

  315. // 用于验证结果的Print函数
  316. void Print(TreeNodeA *node, const int indent);
  317. void Print(TreeNodeB *node, const int indent);
  318. void Print(TreeNodeC *node, const int indent);

  319. std::string Spaces(const int n) {
  320.   return std::string(n, ' ');
  321. }
  322. void Print(TreeNodeA *node, const int indent) {
  323.   std::cout << Spaces(indent) << "TreeNodeA("
  324.             << node->x << "," << node->y << ")\n";
  325.   std::cout << Spaces(indent) << "left = \n";
  326.   if (node->left != nullptr) {
  327.     Print(node->left, indent + 2);
  328.   }
  329.   std::cout << Spaces(indent) << "right = \n";
  330.   if (node->right != nullptr) {
  331.     Print(node->right, indent + 2);
  332.   }
  333. }
  334. void Print(TreeNodeB *node, const int indent) {
  335.   std::cout << Spaces(indent) << "TreeNodeB(" << node->x << ")\n";
  336.   std::cout << Spaces(indent) << "next = \n";
  337.   if (node->next != nullptr) {
  338.     Print(node->next, indent + 2);
  339.   }
  340. }
  341. void Print(TreeNodeC *node, const int indent) {
  342.   std::cout << Spaces(indent) << "TreeNodeC("
  343.             << node->x << "," << node->y << ")\n";
  344.   std::cout << Spaces(indent) << "left = \n";
  345.   if (node->left != nullptr) {
  346.     Print(node->left, indent + 2);
  347.   }
  348.   std::cout << Spaces(indent) << "right = \n";
  349.   if (node->right != nullptr) {
  350.     Print(node->right, indent + 2);
  351.   }
  352. }


  353. ////////////////////////////////////////////////////////////////////////////////
  354. ////////////////////////// 使用CodecSynthesizer生成Codec ////////////////////////
  355. ////////////////////////////////////////////////////////////////////////////////

  356. using Codec = CodecSynthesizer<ENTRY(TreeNodeA, x, y, left, right),
  357.                                ENTRY(TreeNodeB, x, next),
  358.                                ENTRY(TreeNodeC, x, y, left, right)>;

  359. ////////////////////////////////////////////////////////////////////////////////
  360. ///////////////////////////////////// main函数 //////////////////////////////////
  361. ////////////////////////////////////////////////////////////////////////////////


  362. int main(int argc, char *argv[]) {
  363.   TreeNodeA *a = new TreeNodeA(1, 2);

  364.   TreeNodeB *b1 = new TreeNodeB(0.1);
  365.   TreeNodeB *b2 = new TreeNodeB(0.2);
  366.   b1->next = b2;

  367.   TreeNodeB *b3 = new TreeNodeB(0.3);
  368.   TreeNodeA *aa = new TreeNodeA(3, 4);
  369.   aa->left = b3;

  370.   TreeNodeC *c = new TreeNodeC("hello", "world");
  371.   c->left = aa;

  372.   a->left = b1;
  373.   a->right = c;

  374.   Codec codec;
  375.   std::string data = codec.serialize(a);
  376.   std::cout << "data length = " << data.length() << "\n\n";

  377.   TreeNodeA *result = codec.deserialize(data);
  378.   Print(result, 0);

  379.   return 0;
  380. }
复制代码

评分

参与人数 2大米 +8 收起 理由
Sai_L + 3 很有用的信息!
2011051305 + 5 大神的帖子一定要点赞赞赞!

查看全部评分

回复

使用道具 举报

推荐
fentoyal 2017-12-9 10:28:01 | 只看该作者
全局:
magicsets 发表于 2017-12-9 09:06
写了一个LC 13  在这里:https://github.com/jqdocshare/docs/blob/master/roman_to_int.cpp

...

赞。
我当时设计的接口是用的constexpr static char [] = "MCDLXXIV" ,的方式来输入的,而非用type list,稍微短点:
  1. #include <iostream>

  2. class R2I {
  3.     const static int DIG;
  4. public:
  5.     constexpr static char IN [] = "MCDLXXIV"; //INPUT HERE
  6.     const static int OUT;
  7. };

  8. template <char C> struct ID {};
  9. template <> struct ID <'I'> {static const int I = 0; static const int V = 1;};
  10. template <> struct ID <'V'> {static const int I = 1; static const int V = 5;};
  11. template <> struct ID <'X'> {static const int I = 2; static const int V = 10;};
  12. template <> struct ID <'L'> {static const int I = 3; static const int V = 50;};
  13. template <> struct ID <'C'> {static const int I = 4; static const int V = 100;};
  14. template <> struct ID <'D'> {static const int I = 5; static const int V = 500;};
  15. template <> struct ID <'M'> {static const int I = 6; static const int V = 1000;};
  16. template <bool A, bool B, int I0, int I1>
  17. struct DiffHelper{ static const int D = -9;}; //-9 means it hits the end of R2I::IN. It's a valid state.
  18. template<int I0, int I1>
  19. struct DiffHelper <true, true, I0, I1>{
  20.      static const int VAL0 = ID<R2I::IN[I0]>::I;
  21.      static const int VAL1 = ID<R2I::IN[I1]>::I;
  22.      //The only possible Diff between Pos0 and Pos1 can be -2(IX), -1(IV), 0(II), 1(VI), 2+ (MI), -3 - is not possible
  23.      //To reduce the states, I combined 1 and 2+, becasue 1 is only used to transfer to state 6, so I did a calc at state 5 for it.
  24.      static const int D = (VAL0 -  VAL1 <= -3) ? -3 : (( VAL0 -  VAL1 >= 1) ? 1 : (VAL0 -  VAL1));
  25. };
  26. //Diff Caculate the Difference of the indices.
  27. template <int I0, int I1> struct Diff {static const int D = DiffHelper<(I0 < sizeof(R2I::IN) - 1), (I1 < sizeof(R2I::IN) - 1), I0, I1>::D;};
  28. ///////////// General ones
  29. template <int N, int D, int P> struct State {const static int DIG = -4000;};//Not accepted;  The largest in Roman is 3999.
  30. template <int P, int N>    struct State<N, -9, P>  {const static int DIG = ID<R2I::IN[P]>::V;}; //End of R2I::IN, return what it is.
  31. //////////  State 9: IX XC CM
  32. template <int P>    struct State<9, 1, P>    {const static int DIG = ID<R2I::IN[P]>::V * 4/5 + State<(ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I) % 2, Diff<P+1, P+2>::D, P+1>::DIG; };
  33. template <int P>    struct State<9, -9, P>   {const static int DIG = ID<R2I::IN[P]>::V * 4/5;};
  34. //////////// State 6: VI LX DC This state can be merged with II
  35. template <int P>    struct State<6, 1, P>    {const static int DIG = ID<R2I::IN[P]>::V + State<(ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I) % 2, Diff<P+1, P+2>::D, P+1>::DIG; };
  36. template <int P>    struct State<6, 0, P>    {const static int DIG = ID<R2I::IN[P]>::V + State<2, Diff<P+1, P+2>::D, P+1>::DIG;};
  37. //////////// State 4: IV XL CD, Note it is different from 9 as it ends with V. So the odd/even is opposite for Diff
  38. template <int P>    struct State<4, 1, P>    {const static int DIG = ID<R2I::IN[P]>::V * 3/5 + State<(ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I + 1) % 2, Diff<P+1, P+2>::D, P+1>::DIG; };
  39. template <int P>    struct State<4, -9, P>   {const static int DIG = ID<R2I::IN[P]>::V * 3/5;};
  40. //////// State 3: III XXX CCC MMM
  41. template <int P>    struct State<3, 1, P>    {const static int DIG = ID<R2I::IN[P]>::V + State<(ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I) % 2 , Diff<P+1, P+2>::D, P+1>::DIG; };
  42. /////// State 2: II XX CC MM
  43. template <int P>    struct State<2, 1, P>    {const static int DIG = ID<R2I::IN[P]>::V + State<(ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I) % 2 , Diff<P+1, P+2>::D, P+1>::DIG; };
  44. template <int P>    struct State<2, 0, P>    {const static int DIG = ID<R2I::IN[P]>::V + State<3, Diff<P+1, P+2>::D, P+1>::DIG; };
  45. ////////////// State 5: V L D
  46. template <int P>    struct State<1, 1, P>    {const static int DIG = ID<R2I::IN[P]>::V +
  47.     State<(ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I==1)*6 + (ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I + 1) % 2, Diff<P+1, P+2>::D, P+1>::DIG;};
  48. ///////////////State 1: I X C M ; Look into  Diff<P+1, P+2> to calculate what Difference the next stage is facing.
  49. template <int P>    struct State<0, 1, P>    {const static int DIG = ID<R2I::IN[P]>::V + State<(ID<R2I::IN[P]>::I - ID<R2I::IN[P+1]>::I) % 2 , Diff<P+1, P+2>::D, P+1>::DIG; };
  50. template <int P>    struct State<0, 0, P>    {const static int DIG = ID<R2I::IN[P]>::V + State<2, Diff<P+1, P+2>::D, P+1>::DIG; };
  51. template <int P>    struct State<0, -1, P>   {const static int DIG = ID<R2I::IN[P]>::V + State<4, Diff<P, P+2>::D, P+1>::DIG;}; //Use Diff<P, P+2> on purpose for situation XL;
  52. template <int P>    struct State<0, -2, P>   {const static int DIG = ID<R2I::IN[P]>::V + State<9, Diff<P, P+2>::D, P+1>::DIG;};
  53. ///////////////////////
  54. const int R2I::DIG = State<ID<R2I::IN[0]>::I % 2 , Diff<0, 1>::D, 0>::DIG;
  55. const int R2I::OUT = DIG > 0 ? DIG : 0;
  56. using namespace std;
  57. int main()
  58. {
  59.     cout<<R2I::OUT<<endl;
  60. }
复制代码
回复

使用道具 举报

🔗
LeeYYY 2017-11-4 10:55:16 | 只看该作者
全局:
本帖最后由 LeeYYY 于 2017-11-4 10:56 编辑

你说的这题和serialization of trie有点像。trie的结构也比你给的例子里要复杂一些。我玩了一把可以上stack。用stack来连。挺好的。
回复

使用道具 举报

🔗
2011051305 2017-11-4 11:50:14 | 只看该作者
全局:
mark一下 今天发烧了 明天退烧来写~
回复

使用道具 举报

🔗
vikingpanzer 2017-11-5 14:22:57 | 只看该作者
全局:
我仔细看看
回复

使用道具 举报

🔗
2011051305 2017-12-8 06:39:34 | 只看该作者
全局:
magicsets 发表于 2017-12-8 04:50
最近终于有空把这个坑填上...

这个题目主要难度在于:

啊啊啊 magicsets大神的帖子必须要点赞加大米!

话说。。。 我发现我面试用C++写的很长 有时候写不完。。。 正在动摇要不要换Java
TT
回复

使用道具 举报

🔗
fentoyal 2017-12-9 04:12:11 | 只看该作者
全局:
mark下,之前上学的时候也曾经痴迷过meta-programming,但可惜周围没有遇到懂我的人。。。后来上班后就没机会再“玩”这个了。
lz应该也有同感吧?我看这个论坛上好像懂lz的也寥寥无几。。

好多年不弄了,看到lz这个帖子心痒痒了。周末如果没事可能会做一下。

其实LC好些题目都能metaprogramming做,我给lz留几道我以前玩的题目:
元编程实现:
LC 13 - Roman to Integer
LC 65 - Valid number
LC 485 - Max Consecutive Ones
最好不要用任何额外库(boost等)

还有一个非常有挑战的是自己实现 bind,我之前实现过bind3, general的bind也是搁置了好几年都没来得及花时间研究。

评分

参与人数 1大米 +5 收起 理由
2011051305 + 5 fentoyal大神的帖子 看到必加米!

查看全部评分

回复

使用道具 举报

🔗
diyer 2017-12-9 06:56:20 | 只看该作者
全局:
向楼主学习了,meta-programming绝对是造轮子的好东西,不过个人觉得这毕竟是编程语言,除了高效性稳定性以外,易读性也很重要,我自己平时也就用用using, boost_variant和apply_visitor,再复杂的不敢用,毕竟大部分时候我们的代码都和造轮子没关系。
回复

使用道具 举报

🔗
 楼主| magicsets 2017-12-9 08:08:09 | 只看该作者
全局:
2011051305 发表于 2017-12-8 06:39
啊啊啊 magicsets大神的帖子必须要点赞加大米!

话说。。。 我发现我面试用C++写的很长 有时候写不完 ...

感谢大米
回复

使用道具 举报

🔗
 楼主| magicsets 2017-12-9 09:06:38 | 只看该作者
全局:
fentoyal 发表于 2017-12-9 04:12
mark下,之前上学的时候也曾经痴迷过meta-programming,但可惜周围没有遇到懂我的人。。。后来上班后就没机 ...

写了一个LC 13 在这里:https://github.com/jqdocshare/docs/blob/master/roman_to_int.cpp

其实TypeList已经是很通用的数据结构了,functional programming的那套抽象都可以搬过来(比如Haskell Data.List所支持的各种函数),比起早期enum大法,用TypeList做可以方便很多

meta-programming所适用的场景确实比较少,而且可读性比较低... 我发这个帖子也是觉得这个场景有一些意义(一个接口比较fancy的序列化的库)

但现实中确实是有一些非常需要meta-programming的情况的,比如说既需要性能又有很高多态复杂性的场景,我见过的一是Rcpp的源代码,里面有大量的policy-based design:http://www.rcpp.org ;另一个是某并行OLAP数据库系统,里面有几大模块需要多态:
(1) 类型:int, long, double, char, ...
(2) 函数:+, -, *, /, sum, avg, ...
(3) 存储:row-store, column-store, compressed-store, ...
既要处理这种复杂性,又要避免虚函数调用而浪费性能(会慢2到3倍),又要具有高可扩展性(添加新的类型、函数、存储),那么就必须要用meta-programming了

写bind确实感觉很有意思~ 我有空试一下
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表