I actually find standard set containers to be mostly useless myself and prefer to just use arrays but I do it in a different way.
To compute set intersections, I iterate through the first array and mark elements with a single bit. Then I iterate through the second array and look for marked elements. Voila, set intersection in linear time with far less work and memory than a hash table, e.g. Unions and differences are equally simple to apply using this method. It does help that my codebase revolves around indexing elements rather than duplicating them (I duplicate indices to elements, not the data of the elements themselves) and rarely needs anything to be sorted, but I haven't used a set data structure in years as a result.
I also have some evil bit-fiddling C code I use even when the elements offer no data field for such purposes. It involves using the memory of the elements themselves by setting the most significant bit (which I never use) for the purpose of marking traversed elements. That's pretty gross, don't do that unless you're really working at near-assembly level, but just wanted to mention how it can be applicable even in cases when elements don't provide some field specific for traversal if you can guarantee that certain bits will never be used. It can compute a set intersection between 200 million elements (bout 2.4 gigs of data) in less than a second on my dinky i7. Try doing a set intersection between two
std::set instances containing a hundred million elements each in the same time; doesn't even come close.
However, I could also do that by adding each elemento to another
vector and checking if the element already exists.
That checking to see if an element already exists in the new vector is generally going to be a linear time operation, which will make the set intersection itself a quadratic operation (explosive amount of work the bigger the input size). I recommend the technique above if you just want to use plain old vectors or arrays and do it in a way that scales wonderfully.
Basically: what kinds of algorithms require a set and shouldn't be
done with any other container type?
None if you ask my biased opinion if you're talking about it at the container level (as in a data structure specifically implemented to provide set operations efficiently), but there are plenty that require set logic at the conceptual level. For example, let's say you want to find the creatures in a game world which are capable of both flying and swimming, and you have flying creatures in one set (whether or not you actually use a set container) and ones that can swim in another. In that case, you want a set intersection. If you want creatures that can either fly or are magical, then you use a set union. Of course you don't actually need a set container to implement this, and the most optimal implementation generally doesn't need or want a container specifically designed to be a set.
Going Off Tangent
All right, I got some nice questions from JimmyJames regarding this set intersection approach. It's kinda veering off subject but oh well, I'm interested in seeing more people use this basic intrusive approach to set intersection so that they're not building whole auxiliary structures like balanced binary trees and hash tables just for the purpose of set operations. As mentioned the fundamental requirement is that the lists shallow copy elements so that they are indexing or pointing to a shared element that can be "marked" as traversed by the pass through the first unsorted list or array or whatever to then pick up on the second pass through the second list.
However, this can be accomplished practically even in a multithreading context without touching the elements provided that:
- The two aggregates contain indices to the elements.
- The range of indices is not too large (say [0, 2^26), not billions or more) and are reasonably densely occupied.
This allows us to use a parallel array (just one bit per element) for the purpose of set operations. Diagram:
Thread synchronization only needs to be there when acquiring a parallel bit array from the pool and releasing it back to the pool (done implicitly when going out of scope). The actual two loops to perform the set operation need not involve any thread syncs. We don't even need to use a parallel bit pool if the thread can just allocate and free the bits locally, but the bit pool can be handy to generalize the pattern in codebases that fit this kind of data representation where central elements are often referenced by index so that each thread doesn't have to bother with efficient memory management. Prime examples for my area are entity-component systems and indexed mesh representations. Both frequently need set intersections and tend to refer to everything stored centrally (components and entities in ECS and vertices, edges, and polygons in indexed meshes) by index.
If the indices are not densely occupied and sparsely scattered, then this is still applicable with a reasonable sparse implementation of the parallel bit/boolean array, like one which only stores memory in 512-bit chunks (64 bytes per unrolled node representing 512 contiguous indices) and skips allocating completely vacant contiguous blocks. Chances are you are already using something like this if your central data structures are sparsely occupied by the elements themselves.
... similar idea for a sparse bitset to serve as a parallel bit array. These structures also lend themselves towards immutability since it's easy to shallow copy chunky blocks which don't need to be deep copied to create a new immutable copy.
Again set intersections between hundreds of millions of elements can be done in under a second using this approach on a very average machine, and that's within a single thread.
It can also be done in under half the time if the client doesn't need a list of elements for the resulting intersection, like if they only want to apply some logic to the elements found in both lists, at which point they can just pass a function pointer or functor or delegate or whatever to be called back to process ranges of elements that intersect. Something to this effect:
// 'func' receives a range of indices to
parallel_bits = bit_pool.acquire()
// Mark the indices found in the first list.
for each index in list1:
parallel_bits[index] = 1
// Look for the first element in the second list
// that intersects.
first = -1
for each index in list2:
if parallel_bits[index] == 1:
first = index
// Look for elements that don't intersect in the second
// list to call func for each range of elements that do
for each index in list2 starting from first:
if parallel_bits[index] != 1:
first = index
If first != list2.num-1:
... or something to this effect. The most expensive part of the pseudocode in the first diagram is
intersection.append(index) in the second loop, and that applies even for
std::vector reserved to the size of the smaller list in advance.
What If I Deep Copy Everything?
Well, stop that! If you need to do set intersections, it implies that you are duplicating data to intersect against. Chances are that even your tiniest objects aren't smaller than a 32-bit index. It is very possible to reduce the addressing range of your elements to 2^32 (2^32 elements, not 2^32 bytes) unless you actually need more than ~4.3 billion elements instantiated, at which point a totally different solution is needed (and that definitely isn't using set containers in memory).
How about cases where we need to do set operations where the elements aren't identical but could have matching keys? In that case, same idea as above. We just need to map each unique key to an index. If the key is a string, for example, then interned strings can do just that. In those cases a nice data structure like a trie or a hash table is called for to map string keys to 32-bit indices, but we don't need such structures in order to do the set operations on the resulting 32-bit indices.
A whole lot of very cheap and straightforward algorithmic solutions and data structures open up like these when we can work with indices to elements in a very reasonable range, not the full addressing range of the machine, and so it's often more than worth it to be able to obtain a unique index for each unique key.
I Love Indices!
I love indices just as much as pizza and beer. When I was in my 20s, I got really into C++ and started designing all kinds of fully standard-compliant data structures (including the tricks involved to disambiguate a fill ctor from a range ctor at compile-time). In retrospect that was a large waste of time.
If you revolve your database around storing elements centrally in arrays and indexing them rather than storing them in a way that's fragmented and potentially across the entire addressable range of the machine, then you can end up exploring a world of algorithmic and data structure possibilities by just designing containers and algorithms that revolve around plain old
int32_t. And I found the end result to be so much more efficient and easy to maintain where I wasn't constantly transferring elements from one data structure to another to another to another.
Some example use cases when you can just assume that any unique value of
T has a unique index and will have instances residing in a central array:
Multithreaded radix sorts which work well with unsigned integers for indices. I actually have a multithreaded radix sort which takes about 1/10th of the time to sort a hundred million elements as Intel's own parallel sort, and Intel's is already 4 times faster than
std::sort for such large inputs. Of course Intel's is much more flexible since it's a comparison-based sort and can sort things lexicographically, so it's comparing apples to oranges. But here I often only need oranges, like I might do a radix sort pass just to achieve cache-friendly memory access patterns or filter out duplicates quickly.
Ability to build linked structures like linked lists, trees, graphs, separate chaining hash tables, etc. without heap allocations per node. We can just allocate the nodes in bulk, parallel to the elements, and link them together with indices. The nodes themselves just become a 32-bit index to the next node and stored in a big array, like so:
Friendly for parallel processing. Often linked structures aren't so friendly for parallel processing, since it's awkward at the very least to try to achieve parallelism in tree or linked list traversal as opposed to, say, just doing a parallel for loop through an array. With the index/central array representation, we can always go to that central array and process everything in chunky parallel loops. We always have that central array of all elements we can process this way, even if we only want to process some (at which point you might process the elements indexed by a radix-sorted list for cache-friendly access through the central array).
Can associate data to each element on the fly in constant-time. As with the case of the parallel array of bits above, we can easily and extremely cheaply associate parallel data to elements for, say, temporary processing. This has use cases beyond temporary data. For example, a mesh system might want to allow users to attach as many UV maps to a mesh as they want. In such a case, we can't just hard-code how many UV maps there will be in every single vertex and face using an AoS approach. We need to be able to associate such data on the fly, and parallel arrays are handy there and so much cheaper than any kind o sophisticated associative container, even hash tables.
Of course parallel arrays are frowned upon due to their error-prone nature of keeping parallel arrays in sync with each other. Whenever we remove an element at index 7 from the "root" array, for example, we likewise have to do the same thing for the "children". However, it's easy enough in most languages to generalize this concept to a general-purpose container so that the tricky logic to keep parallel arrays in sync with each other only need exist in one place throughout the entire codebase, and such a parallel array container can use the sparse array implementation above to avoid wasting lots of memory for contiguous vacant spaces in the array to be reclaimed upon subsequent insertions.
More Elaboration: Sparse Bitset Tree
All right, I got a request to elaborate some more which I think was sarcastic, but I'm gonna do so anyway cause it's so much fun! If people want to take this idea to whole new levels, then it is possible to perform set intersections without even linearly looping through N+M elements. This is my ultimate data structure which I've been using for ages and basically models
The reason it can perform set intersections without even inspecting each element in both lists is because a single set bit at the root of the hierarchy can indicate that, say, a million contiguous elements are occupied in the set. By just inspecting one bit, we can know that N indices in the range,
[first,first+N) are in the set, where N could be a very large number.
I actually use this as a loop optimizer when traversing occupied indices, because let's say there are 8 million indices occupied in the set. Well, normally we would have to access 8 million integers in memory in that case. With this one, it can potentially just inspect a few bits and come up with index ranges of occupied indices to loop through. Further, the ranges of indices it comes up with are in sorted order which makes for very cache-friendly sequential access as opposed to, say, iterating through an unsorted array of indices used to access the original element data. Of course this technique fares worse for extremely sparse cases, with the worst-case scenario being like every single index being an even number (or every one being odd), in which case there are no contiguous regions whatsoever. But in my use cases at least, that practically never happens.