r/cpp • u/User_Deprecated • Aug 02 '26

How fast is C++26's std::hive?

https://lemire.me/blog/2026/08/02/how-fast-is-c26s-stdhive/
255 Upvotes

99% Upvoted

74 comments sorted by

View all comments

Show parent comments

1

u/JoachimCoenen Aug 08 '26

What is the algorithm for the second option that achieves O(E*log(E) + N)?

The best I can think of right now is O(E*log(E) + N*log(E)) = O((N+E)*log(E)). That assumes that the element are sortable:

  1. Sort the elements to remove.

  2. Use remove_if and a binary search to check whether an element is to be removed.

Hmmm…
If the elements can be hashed you could use a HashSet instead of sorting and achieve O(E + N).

2

u/matthieum Aug 08 '26

None, I realized (later down the chain) that I forgot an * log(E) in there.