c++ - 如何获取类型的唯一序列 c++ : (A, B, A, B, C) =>(A, B, C)

Question

我需要排除双重实例化，因此我需要从类型序列中排除相同的类型。

#define ENTITY_SEQ (A)(B)(C)(A)(C)
||
\/
#define UNIQUE_ENTITY_SEQ (A)(B)(C)

我想使用 boost 预处理器来处理它。可以这样做吗？

Answer 1

据我所知，没有办法检查两个未知标识符的相等性。 但是，如果您提前知道标识符列表，那么这当然是可能的。

今天我花了一些时间来实现这个简单的 O(n^2) 算法，尽管您可能可以做得更好。我希望这个顺序对你来说并不重要，因为我决定不尝试保留它。

#define CATe(a,b) CAT(a,b)
#define CAT(a,b) a##b
#define LPAREN (

#define CHECK(p,t,f) TUPLE_AT_2(p t,f,)
#define TUPLE_AT_2(a,b,...) b

#define EQ_0end_0end ,

// transform seq to guide
// (1)(2)(0end) -> 1)2)0end)
#define SEQ_TO_GUIDE_A(x) x)CHECK(EQ_0end_##x,,SEQ_TO_GUIDE_B)
#define SEQ_TO_GUIDE_B(x) x)CHECK(EQ_0end_##x,,SEQ_TO_GUIDE_A)


// insert without creating a duplicate
#define DEDUPE1_SCAN(...) __VA_ARGS__
#define DEDUPE1(seq,x) DEDUPE1_SCAN(DEDUPE1_A LPAREN x,SEQ_TO_GUIDE_A seq(0end))

#define DEDUPE1_A(x,y) CHECK(EQ_0end_##y,DEDUPE1_END,DEDUPE1_DO)(DEDUPE1_B,x,y)
#define DEDUPE1_B(x,y) CHECK(EQ_0end_##y,DEDUPE1_END,DEDUPE1_DO)(DEDUPE1_A,x,y)

// always insert (x) at the end
#define DEDUPE1_END(n,x,y) (x)

// keep (y) when x == y
#define DEDUPE1_DO(n,x,y) CHECK(EQ_##x##_##y,DEDUPE1_1,DEDUPE1_0)(n,x,y)
#define DEDUPE1_0(n,x,y) (y) n(x,
#define DEDUPE1_1(n,x,y) n(x,


// successively apply DEDUPE1 on seq with every element of seq
#define DEDUPE_SCAN(...) __VA_ARGS__
#define DEDUPE(seq) DEDUPE_SCAN(DEDUPE_A LPAREN seq,SEQ_TO_GUIDE_A seq(0end))
#define DEDUPE_A(seq,x) CHECK(EQ_0end_##x,DEDUPE_END,DEDUPE_DO)(DEDUPE_B,seq,x)
#define DEDUPE_B(seq,x) CHECK(EQ_0end_##x,DEDUPE_END,DEDUPE_DO)(DEDUPE_A,seq,x)

#define DEDUPE_DO(n,seq,x) n(DEDUPE1(seq,x),
#define DEDUPE_END(n,seq,x) seq



#define EQ_A_A ,
#define EQ_B_B ,
#define EQ_C_C ,
#define EQ_D_D ,
#define EQ_E_E ,

DEDUPE((A)(B)(A)(A)(C)(E)(A)(B)(C)(E)(A))
// expands to: (B)(C)(E)(A)

// 7500 elements with A B C D E took ~1 second 

基本思想是将序列 ((1)(2)(3)) 转换为终止引导 (1)2)3)0end)) ，它允许使用上下文进行迭代。 此上下文在 DEDUPE1(seq,x) 中用于删除 seq 中出现的所有 x 并追加 x之后到 seq 的末尾。 DEDUPE(seq) 使用 seq 本身作为上下文，迭代 seq 的所有元素，并使用 DEDUPE1( 更新迭代上下文seq,x)。

以上适用于任何大小的序列，但 it is implementation defined if this type of sequence iteration works 。幸运的是，基本上所有预处理器都支持它。

---

更新:这是一个 O(n) 版本，该版本较短，但每个额外支持的标识符需要更多代码:

#define LPAREN (

#define CHECK(p,t,f) TUPLE_AT_2(p t,f,)
#define TUPLE_AT_2(a,b,...) b

#define EQ_0end_0end ,
#define EQ_0_0 ,

// transform seq to guide
// (1)(2)(0end) -> 1)2)0end)
#define SEQ_TO_GUIDE_A(x) x)CHECK(EQ_0end_##x,,SEQ_TO_GUIDE_B)
#define SEQ_TO_GUIDE_B(x) x)CHECK(EQ_0end_##x,,SEQ_TO_GUIDE_A)


// SET_INSERT for every of seq
#define DEDUPE_SCAN(...) __VA_ARGS__
#define DEDUPE(seq) DEDUPE_SCAN(DEDUPE_A LPAREN SET_EMPTY,SEQ_TO_GUIDE_A seq(0end))
#define DEDUPE_A(set,x) CHECK(EQ_0end_##x,DEDUPE_END,DEDUPE_DO)(DEDUPE_B,set,x)
#define DEDUPE_B(set,x) CHECK(EQ_0end_##x,DEDUPE_END,DEDUPE_DO)(DEDUPE_A,set,x)

#define DEDUPE_DO(n,set,x) n(SET_INS_##x set,
#define DEDUPE_END(n,set,x) SET_TO_SEQ set

#define SET_EMPTY (0,0,0,0,0)
#define SET_INS_A(a,...) (A,__VA_ARGS__)
#define SET_INS_B(a,b,...) (a,B,__VA_ARGS__)
#define SET_INS_C(a,b,c,...) (a,b,C,__VA_ARGS__)
#define SET_INS_D(a,b,c,d,e) (a,b,c,D,e)
#define SET_INS_E(a,b,c,d,e) (a,b,c,d,E)

#define SET_TO_SEQ1(x) CHECK(EQ_0_##x,,(x))
#define SET_TO_SEQ(...) SET_TO_SEQ_(SET_TO_SEQ1,__VA_ARGS__)
#define SET_TO_SEQ_(F,a,b,c,d,e)  F(a)F(b)F(c)F(d)F(e)


DEDUPE((A)(B)(A)(A)(C)(E)(A)(B)(C)(E)(A))
// expands to: (A)(B)(C)(E)

// 80000 elements with A B C D E took ~1 second

编辑:我更新了 CHECK 宏，因为我意识到我一直在使用不太理想的实现。