It has been answered, and according to the answer, there's an easy 20x-30x speedup to be had. Maybe your problem is not C++ per se. I wouldn't be surprised if

It has been answered, and according to the answer, there's an easy 20x-30x speedup to be had. Maybe your problem is not C++ per se. I wouldn't be surprised if std::unordered_set would yield further speedup. (It doesn't look like you need the order criterion). Other things worth trying are: * Not using a set at all - it seems most sets only have 3-4 elements. You might as well use a vector. * It doesn't look like your intervals overlap, and it looks like they're already ordered. interval_map may be unnecessary, and it might be worth keeping the data in a simple vector. * You don't want to copy object_set, either. A const-ref is more than enough * And finally, if you want to veer into nit-pick territory, you want to use range-based loops. It might or might not yield better compiled code. It's definitely much more readable. for (const auto& iter : map->equal_range(window)) for (const auto& obj: iter->second) f(iter->first->start, iter->first->end, obj.c_str(), opaque); I don't disagree with the abysmal error messages, or the thought that C++ is a beast to learn and control. But if there's one thing it does give you, it's decent performance, if used properly. Let's put it that way: The browser people don't write C++ because they think it's such an awesome language :)