如何高效查找std::set中data_a处于指定范围的相邻元素？

利用std::set的成员函数lower_bound和upper_bound，结合自定义辅助键类型，就能在不知道B类型最小值/最大值的情况下，精准定位目标区间的边界。核心思路是让辅助键仅参与data_a的比较，忽略data_b的影响，从而匹配所有data_a处于[min_a, max_a]范围内的元素。

修改后的代码实现 #

template<typename A, typename B>
class overall_type {
public:
    // 返回区间内元素的迭代器对（左闭右开）
    auto find(A min_a, A max_a) {
        // 定义辅助键，仅用于匹配data_a的边界
        struct lower_key { A val; };
        struct upper_key { A val; };

        // 重载比较运算符，让辅助键仅与contained_type的data_a比较
        friend bool operator<(const contained_type& elem, const lower_key& key) {
            return elem.data_a < key.val;
        }
        friend bool operator<(const lower_key& key, const contained_type& elem) {
            return key.val < elem.data_a;
        }

        friend bool operator<(const contained_type& elem, const upper_key& key) {
            return elem.data_a < key.val;
        }
        friend bool operator<(const upper_key& key, const contained_type& elem) {
            return key.val < elem.data_a;
        }

        // 定位区间左右边界
        auto left = internal_data.lower_bound(lower_key{min_a});
        auto right = internal_data.upper_bound(upper_key{max_a});
        return std::make_pair(left, right);
    }

    // 其他成员函数保持不变

private:
    struct contained_type {
        A data_a;
        B data_b;

        auto operator<(contained_type const& other) -> bool {
            if (data_a < other.data_a) {
                return true;
            }
            if (data_a > other.data_a) {
                return false;
            }
            return data_b < other.data_b;
        }
    };

    std::set<contained_type> internal_data;
};

原理说明 #

1. 辅助键的作用：

   • lower_key用于定位左边界：lower_bound会返回第一个data_a >= min_a的元素，完全忽略data_b的取值。
   • upper_key用于定位右边界：upper_bound会返回第一个data_a > max_a的元素，同样不考虑data_b。
     两个迭代器之间的元素就是所有符合(min_a, -∞) <= e <= (max_a, ∞)条件的元素。

2. 时间复杂度：
   std::set的lower_bound和upper_bound均为O(log n)时间复杂度，满足项目对最坏情况性能的要求，避免了std::vector插入时的O(n)开销。

3. 模板兼容性：
   无需知晓A或B的具体类型细节，只要A支持<比较运算符即可，完全适配模板设计。

使用示例 #

比如要查找所有data_a为b的元素，只需调用：

auto [begin, end] = obj.find(b, b);
for (auto it = begin; it != end; ++it) {
    // 处理元素的data_a和data_b
}

内容的提问来源于stack exchange，提问作者Maddy Guthridge