The most efficient and general-purpose solution I've come up with for this problem, and it works specifically for integers (though still widely applicable in my case since I refer to just about everything by index when using auxiliary data structures to accelerate searches), is what I call a "sparse bit tree". I don't know if there's a formal name for this data structure. It can perform set operations in better than linear time, without having to inspect all elements (bits) of both sets, since it can, say, skip over a million elements if it just finds a set bit (
1) at the root level in both sets and know immediately that both sets have a million elements in common with a test for a single bit.
As a result it has a best case performance of something like Log(N) / Log(64), where it can find the set intersection between two dense sets containing a million elements each in 3-4 iterations, with each iteration only having to check one bit. The worst case scenario is N * Log(N) / Log(64), where it might have to perform around 3 to 4 million iterations to determine the set intersection between both sets, but that's still linear-time and it doesn't happen unless the data is very awkwardly sparse with no contiguous indices (like a case where every integer in the set is an even number).
I wouldn't be surprised if someone else has already come up with the same idea long before me (if anyone knows the name if so, I'd much appreciate it). It's just something I made up and have been using for ages (the original version used 16-bit words and has evolved towards 64-bit).
It is not the most trivial data structure to implement, but has served me well as the backbone for so many projects. The diagram should give enough of an idea to implement for those who are interested. It can be used as an integer/index set with set operations. Unlike most sets, it can also be used to rapidly find an unused integer/index (rapidly find the first integer not in the set) using ffs instructions with the complement and figure out what index to to insert an element to in an array with "holes" in it to allow rapid removal and to avoid invalidating indices to other elements, etc.
I actually found it so useful that I think it has shaped the way I design codebases against it to the point where I now want to store indices to everything stored in central arrays and avoid pointers when possible. There's that whole tendency to see everything as a nail when you're wielding a hammer, but in this case it's an extremely efficient hammer that trivializes getting a performant solution. I ended up finding even more use for it than ever before after working my way towards entity-component systems which want to perform set intersections all the time ("find all entities that implement X,Y,Z components").
The rapid linear traversal as noted on the bottom right is a huge one for me, since I have many loops in many projects I've made where they inevitably can't do better than linear (
for each element in the set, do some light work type loops). This often makes the loop cheaper than iterating through an array of indices because it can often do it while accessing so little memory when a single bit set towards the top of the hierarchy can indicate that indices in the range,
[8388608,16777216) are in the set by just inspecting one bit, e.g., as opposed to over 8 million bits or, worse, over 8 million integers.
As a result I often use this structure even when I don't need a set as a replacement for, say, an array of integers (
vector<int> if I'm going to be looping over the result many times over. It serves as a loop accelerator when the indices consist predominantly of contiguous ranges since in those cases, it's much faster to iterate through than an array of integers. Even disregarding that, it also means the loop will access the original elements in sorted order which is typically the most cache-friendly access pattern as opposed to sporadic random access you might get by just looping through an array of unsorted indices.
And because it's reasonably well-suited for sparse data, you don't have to worry too much about hogging a boatload of memory if the indices/integers are very sparse and have a huge range (as long as it's not too huge, a range in the millions is perfectly fine, billions or trillions might call for something better suited for extremely sparse representations).
Now funnily enough to test the presence of a single integer, it has a worse algorithmic complexity with a worst case of something like log(N) / log(64) iterations (or bitwise operations) than a simple huge array of bits (bitset) for which you can test a specific bit in constant time with a single bit operation and some arithmetic (or a bit shift and a bitwise and). However, it tends to still be faster because of the temporal locality associated with being able to often determine whether an
nth bit is set without drilling down to the leaves, especially in cases which the indices are reasonably dense (for super sparse cases, you might just go straight to the leaf nodes and treat this like it's a gigantic array of bits instead of a tree).