如何借助STL或兼容库兼顾两种集合交集算法的性能优势？

Great question! I’ve run into this exact scenario before—balancing between the linear-time std::set_intersection and the lookup-based approach without manual size checks is tricky, but there’s a clever way to leverage STL features you might have missed, plus a clean way to automate the optimal strategy.

First: The STL Feature You Overlooked #

Did you know that std::set and std::map have a hint-aware find overload (available since C++11)? The signature looks like this:

iterator find(const key_type& k, iterator hint);

When the hint iterator points near where the key k should reside (which it will, if you’re iterating through an ordered container in sequence), this operation runs in amortized O(1) time instead of the usual O(log n). This is a game-changer for the lookup-based approach.

A STL-Only Solution That Automates Optimal Strategy #

Instead of manually checking container sizes, we can write a lightweight template function that automatically picks the smaller container to iterate through, then uses the hint-aware find to collect intersections efficiently. This combines the best of both worlds:

• For large, similarly-sized containers, it’s competitive with std::set_intersection
• For lopsided size ratios (e.g., a tiny set and a huge map), it’s way faster than either naive approach

Here’s the code:

#include <algorithm>
#include <set>
#include <map>
#include <iterator>

template <typename OrderedContainer1, typename OrderedContainer2, typename OutputIterator>
OutputIterator efficient_intersection(const OrderedContainer1& c1, const OrderedContainer2& c2, OutputIterator result) {
    // Automatically pick the smaller container to iterate
    const auto& smaller = (c1.size() <= c2.size()) ? c1 : c2;
    const auto& larger = (c1.size() <= c2.size()) ? c2 : c1;

    auto hint = larger.begin();
    for (const auto& elem : smaller) {
        // Use the previous find result as a hint for the next lookup
        hint = larger.find(elem, hint);
        if (hint != larger.end()) {
            *result++ = *hint;
        }
    }
    return result;
}

Why This Works #

• No manual size checks: The ternary operator handles picking the smaller container automatically.
• Amortized O(min(n1, n2)) time: Because we’re iterating through an ordered container, each subsequent find hint is positioned near the next element we’re looking for, making each lookup nearly constant time.
• STL-only: No external dependencies—this uses standard std::set, std::map, and their built-in find overload.

When to Use std::set_intersection vs. This Function #

If your containers are very close in size, std::set_intersection (O(n1 + n2)) is still slightly optimal. But if you want a one-size-fits-all solution that adapts to any size ratio, the above function is perfect. For extra polish, you could add a threshold check (e.g., if the smaller container is more than 10% the size of the larger one, fall back to std::set_intersection), but that’s optional and depends on your performance testing.

Are There Prebuilt Library Functions? #

If you don’t want to write your own template, most modern STL-compatible libraries (like Boost) don’t have a direct out-of-the-box function for this exact use case—but the template above is minimal, easy to maintain, and fully compliant with standard C++.

内容的提问来源于stack exchange，提问作者Hans Olsson