How to get unique sequence of types c++: (A, B, A, B, C) =>(A, B, C)

Question

I need to exclude double instantiation, therefore I need to exclude the same types from the sequence of types.

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

I want to process it using a boost preprocessor. Is it possible to do that?

Answer 1

There is, to my knowledge, no way to check the equality of two unknown identifiers. But, if you know the list of identifiers ahead of time, then it is certainly is possible.

I had some time to implement the trivial O(n^2) algorithm today, although you could probably do better. I hope the order isn't important to you, because I decided against trying to keep it.

#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 

The basic idea is to transform the sequence ((1)(2)(3)) into a terminated guide (1)2)3)0end)), which allows for iteration with a context. This context is used in DEDUPE1(seq,x) to remove all occurrences of x in seq and append x to the end of seq afterwards. DEDUPE(seq) uses seq itself as the context and iterates through all elements of seq, and updates the iteration context with DEDUPE1(seq,x).

The above works for sequences of any size, but it is implementation defined if this type of sequence iteration works. Luckily, essentially all preprocessors support it.

---

Update: Here is a O(n) version, that is shorter, but requires more code for each extra supported identifier:

#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

Edit: I updated the CHECK macro, because I realized that I've been using a less ideal implementation.