如何在C++11的两个非重叠集合上实现无需合并的双指针技术？

嘿，这个想法真的很赞！既然两个std::set已经有严格的大小关系——第一个集合的所有元素都小于第二个的，那完全没必要合并，直接用两个迭代器模拟双指针就搞定了，效率还更高呢。

核心原理 #

因为std::set本身是有序容器（默认按升序排列），再加上题目给的“第一个集合所有元素 < 第二个集合所有元素”的前提，我们可以直接用两个迭代器分别指向两个集合的起始（或特定）位置，然后根据你的具体需求（比如找元素对、顺序遍历等）来移动迭代器，逻辑和合并后的双指针完全一致，而且不需要额外的内存存储合并后的集合。

代码示例1：寻找和为目标值的元素对 #

这是双指针最常用的场景之一，我们可以让第一个迭代器从s1的最小元素开始，第二个迭代器从s2的最大元素开始，通过比较和与目标值的大小来调整指针位置：

#include <iostream>
#include <set>

int main() {
    std::set<int> s1 = {1, 3, 5, 6};
    std::set<int> s2 = {8, 10, 12, 15};
    const int target = 14;

    // 初始化双指针：it1指向s1最小元素，it2指向s2最大元素
    auto it1 = s1.begin();
    auto it2 = s2.rbegin(); // 反向迭代器，从末尾（最大元素）开始

    while (it1 != s1.end() && it2 != s2.rend()) {
        const int current_sum = *it1 + *it2;
        
        if (current_sum == target) {
            std::cout << "找到配对：" << *it1 << " + " << *it2 << " = " << target << "\n";
            ++it1;
            ++it2; // 元素互不相同，找到后同时移动两个指针
        } else if (current_sum < target) {
            ++it1; // 和太小，需要更大的元素，移动s1的指针
        } else {
            ++it2; // 和太大，需要更小的元素，移动s2的反向指针（相当于向前移动）
        }
    }

    return 0;
}

代码示例2：模拟合并后的顺序遍历 #

如果你的需求是按升序遍历两个集合的所有元素，因为已知s1的元素都小于s2，逻辑可以更简洁：

#include <iostream>
#include <set>

int main() {
    std::set<int> s1 = {1, 3, 5};
    std::set<int> s2 = {7, 9, 11};

    auto it1 = s1.begin();
    auto it2 = s2.begin();

    // 先遍历完s1的所有元素（因为都小于s2）
    while (it1 != s1.end()) {
        std::cout << *it1 << " ";
        ++it1;
    }
    // 再遍历s2的所有元素
    while (it2 != s2.end()) {
        std::cout << *it2 << " ";
        ++it2;
    }

    return 0;
}

当然，如果是通用场景（比如不确定两个集合的大小关系，但这里题目明确了），也可以保留经典双指针的判断逻辑，不过在这个特定场景下完全可以简化。

关键注意点 #

• std::set的迭代器是双向迭代器，支持++和--操作，但不支持随机访问（不能用it + n），不过这完全不影响双指针的逻辑。
• 因为题目明确两个集合元素互不相同，所以找到配对后可以直接同时移动两个指针，不用考虑重复元素的问题。

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