Using a map (as in C++ std::map) would be one easy and obvious way of reducing "must iterate every element" to "must only touch log2(n) elements".
Another easy way (a hack, but nevertheless) would be to use the object's memory address as ID. There's nothing to look up and nothing to search, and the ID is guaranteed to be unique.
Just make sure you don't free and immediately reuse an address (as it's the case with most allocators) and then assume that the client "magically" knows that this is now a different object. But hey, hacks almost always come with a little "gotcha".
One solution to this issue is, by the way, the same as you use in lockfree concurrent algorithms to combat the ABA problem: Exploit the fact that objects are aligned (most of the time to 8 or so bytes) so the lowest few bits are all zero and you can put a counter into these.