📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: magicsets
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
fentoyal 2017-12-9 10:18:51 | 只看该作者
全局:
diyer 发表于 2017-12-9 06:56
向楼主学习了,meta-programming绝对是造轮子的好东西,不过个人觉得这毕竟是编程语言,除了高效性稳定性以 ...

同意。。所以也就上学时写着玩玩(我上学时听痴迷这个的),真上班了不会碰这些的。找工作也没人看的。
回复

使用道具 举报

🔗
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. }
复制代码
回复

使用道具 举报

🔗
fentoyal 2017-12-9 10:34:56 | 只看该作者
全局:
本帖最后由 fentoyal 于 2017-12-9 10:43 编辑

说到应用场景,我以前实现过一个arbitrary dimension, dynamic, continuous memory space, array allocator, 还是挺实用的,动机是当时实验室的需要处理大量3,4维数据,所以这个后来被用到了项目里(这个版本内部结构是native的高维指针,所以有性能问题,被后来一个更好的方案替代了,这里不展开了),大概实现了个这么个事:
  1. //定义数组:
  2.         size_t sizes[] = {4, 5, 6, 2};//4 is the highest dimesion
  3.         Foo ****arr = IdealArrBuilder<Foo, 4>::inew(sizes);
  4. //使用:
  5. (****arr).i = 5;
  6.         (***arr)->j = 6;
  7.         arr[2][3][0][0].i = 3;
  8.         arr[2][3][0][1].i = 4;
  9.         const auto &arrref = arr;
  10.         cout<<(****arrref).j<<endl;
  11.         cout<<arrref[2][3][0]->i<<endl;
  12.         cout<<arrref[2][3][0][1].i<<endl;
  13.         cout<<(***arrref)[157].i<<endl; //157 = 2*5*6*2 + 3*6*2 + 0*2 + 1
  14.         cout<<(**arrref)[78][1].i<<endl; // 78 = 2*5*6 + 3*6
  15.         cout<<(*arrref)[13][0][1].i<<endl; // 13 = 2*5 + 3
  16.         cout<<(*arr[2][3])[1].i<<endl;//*arr[2][3] <=> arr[2][3][0]
  17.         cout<<(*(*arr)[13])[1].i<<endl;//(*arr)[13] <=> arr[2][3]
复制代码
其实就是可以在一个连续空间上创造一个native的高维数组。支持所有的native的指针到index的转换/降维操作。比如例子里的arrref[2][3][0][1] 等价 (***arrref)[157]等价(**arrref)[78][1]。
回复

使用道具 举报

🔗
F119PW100 2018-3-7 15:04:04 | 只看该作者
全局:
楼主不会是谷歌开发protobuf的吧,我们公司以前系统用过这个东西,我们是用轮子的,楼主是造轮子的,档次高了一个档次
回复

使用道具 举报

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

本版积分规则

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