I am not sure that I understand the problem correctly, but it seems that the lookup will be slower on std::vector
/std::find
, but iteration might be faster than with std::unordered_set
. If that is the case, and you are not limited by memory constraints, you can mix both approaches:
Maintain both a std::unordered_set
and a std::vector
with the elements. Lookup inside the std::unordered_set
to determine whether the element is already there, if it is not, add it to both containers. At the end iterate over the std::vector
.
Note that you can provide hints to both containers regarding the 'expected' number of elements that they will contain, and that will reduce the number of memory allocations/rehashing.