C++erいる(;´Д`)？
std::set<int>のようなもので
挿入ｺｽﾄは高くついてもいいから
int保持する内部形式がﾘﾆｱになってて
set内の有無を集中的に参照する場合にｷｬｯｼｭに乗って高速ですよ
みたいなｺﾝﾃﾅのﾗｲﾌﾞﾗﾘありませんか(;´Д`)？

動く処理的には配列をﾊﾞｲﾅﾘｻｰﾁするような感じだと良いです
やっぱ素直にAllocator自作っすかね？