我想我明白了：

std::set<int>::iterator it1 = set_1.begin();
std::set<int>::iterator it2 = set_2.begin();
while ( (it1 != set_1.end()) && (it2 != set_2.end()) ) {
    if (*it1 < *it2) {
        set_1.erase(it1++);
    } else if (*it2 < *it1) {
        ++it2;
    } else { // *it1 == *it2
            ++it1;
            ++it2;
    }
}
// Anything left in set_1 from here on did not appear in set_2,
// so we remove it.
set_1.erase(it1, set_1.end());

有人看到问题了吗？两个集合的大小似乎是O（n）。根据cplusplus.com，std：：set erase（position）是摊余常数，而erase（first，last）是O（log n）。

你可以很容易地遍历set_1，检查每个元素，看看它是否存在于set_2中，如果不存在，就擦除它。因为集合是排序的，你可以在线性时间内比较它们，使用迭代器擦除一个元素就是amortized constant time。我不指望它比你开始时更有效，如果你在乎的话，基准测试是明智的。

它没有直接回答这个问题，但也许有人觉得这很有帮助。
在std::vector的情况下，使用set_1.begin()作为输出迭代器的标准算法是不安全的（见下文），而clang/gcc/microsoft实现可以工作。注意，set_2 * 可以是任何东西 *，不仅仅是std::vector。

std::vector<int> set_1;  // With some elements
std::vector<int> set_2;  // With some other elements
auto end = std::set_intersection(
                     set_1.begin(), set_1.end(), 
                     set_2.begin(), set_2.end(), 
                     set_1.begin() // intersection is written in set_1
                    );
set_1.erase(end, set_1.end()); // erase redundant elements

更新：

感谢@基思，他发现C++标准（25.4.5.3）需要下一个：
结果范围不得与原始范围重叠
所以我最初的建议是错误的，但是在主要的STL实现中是可行的解决方案。如果你想安全起见，不想额外的分配，那么把你选择的实现复制到你的代码库中，用它代替std::set_intersection。我真的不明白这样限制的原因，如果你知道答案，请评论。