I created a class that does just about everything a set does in C++, such as insertion, deletion, and searching but I used OpenMP to make it run in parallel so that all of those actions are faster. I just wanted to share what I did here and get your thoughts and criticism on whether this would ever be useful to someone. This was for a research project at my universities research foundation.
The project is here on my github, it includes a documentation that explains what all of the functions do:
The basic idea is that it uses a vector of sets where each cpu thread manages one tree, so a cpu with 4 threads will have a vector of size 4 containing one tree in each position.
I used what I called "breakpoints" to determine where to insert each element. When inserting an element each thread would check to see if the element belongs in its tree, if it does then it would go ahead and insert.
I added a re balancing function that re balances the trees by adjusting the breakpoints and moving the necessary elements to the correct trees after inserting so that it doesn't end up turning into a standard set if everything being inserted falls into the same tree.
Deleting and searching for elements works the same, where each thread will determine if it needs the element is in its tree then proceed with the deletion or search if necessary.
I also made it possible to insert, delete, or search for multiple elements at a time by passing a vector into the function rather than a single element.
After testing all of the functions on my PC (with 4 threads), inserting, deleting, and searching for elements was always about three times as fast because the threads had smaller trees to go through to complete the task.
I used a template so you should be able to use any data type that you can use with the standard set as long as it has the division (/) operator.
I have a document explaining what the functions are and a program that tests the speed against the standard C++ set by generating a million random doubles.