Well, this is just precious. When the first C++ recommendation turned out to be not applicable, the answer is:

1) He can solve the issue by requiring C++11 (!!)

2) Just rely on cache-effects making it pseudo-O(1), unless (insert various cases where it might blow).

Sure, he can jump through 200 hoops to use C++, special features, rely on CPU cache behavior, finetune to death, etc -- or, you know, he can use C and be done with it...