C++中如何将back_inserter与变换结合？包装输出迭代器实现插入前处理

好问题！要给back_inserter_iterator这类输出迭代器加上变换逻辑，同时记录插入元素的地址或迭代器，咱们可以分两部分来解决，下面是具体的实现方案：

一、给输出迭代器添加变换操作 #

你可以通过自定义迭代器适配器或者变通使用标准库算法来实现。前者更适合直接在std::set_difference这类算法中使用，后者则更简单易读。

方法1：自定义变换输出迭代器 #

我们可以写一个轻量的迭代器适配器，它会把底层的输出迭代器和变换函数打包在一起，每次赋值时先对元素应用变换，再传给底层迭代器插入容器。

代码示例：

#include <iterator>
#include <functional>

template <typename OutputIt, typename TransformFunc>
class TransformOutputIterator {
public:
    // 输出迭代器必须的类型定义
    using iterator_category = std::output_iterator_tag;
    using value_type = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;

    // 构造函数：接收底层迭代器和变换函数
    TransformOutputIterator(OutputIt it, TransformFunc func)
        : m_it(std::move(it)), m_func(std::move(func)) {}

    // 核心逻辑：赋值时先应用变换再插入
    template <typename T>
    TransformOutputIterator& operator=(const T& value) {
        *m_it = m_func(value);
        ++m_it;
        return *this;
    }

    // 输出迭代器要求的空操作（只是为了符合迭代器接口）
    TransformOutputIterator& operator*() { return *this; }
    TransformOutputIterator& operator++() { return *this; }
    TransformOutputIterator operator++(int) { return *this; }

private:
    OutputIt m_it;
    TransformFunc m_func;
};

// 辅助函数：简化适配器的创建（不用手动写模板参数）
template <typename OutputIt, typename TransformFunc>
auto make_transform_output_iterator(OutputIt it, TransformFunc func) {
    return TransformOutputIterator<OutputIt, TransformFunc>(std::move(it), std::move(func));
}

使用的时候直接把它传给std::set_difference就行，比如应用自由函数f(double)：

// 示例自由函数：把输入值乘2
double f(double val) {
    return val * 2.0;
}

int main() {
    std::vector<double> xx = {1.0, 3.0, 5.0};
    std::vector<double> yy = {2.0, 4.0};
    std::vector<double> diff;

    // 创建带变换的插入迭代器
    auto transformed_inserter = make_transform_output_iterator(std::back_inserter(diff), f);
    std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(), transformed_inserter);

    // 此时diff中的元素是：2.0、6.0、10.0
    return 0;
}

方法2：变通方案——先用临时容器再变换 #

如果不想写自定义迭代器，也可以先让std::set_difference输出到临时容器，再用std::transform把变换后的元素插入目标容器。缺点是会多一次内存拷贝，但胜在简单：

std::vector<double> temp;
std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(), std::back_inserter(temp));
// 把变换后的元素插入diff
std::transform(temp.begin(), temp.end(), std::back_inserter(diff), f);

二、安全存储元素的地址/迭代器 #

这里要敲个黑板：std::vector在元素数量超过当前容量时会自动扩容，扩容后之前保存的迭代器、指针和引用都会失效。所以要安全存储，有两种靠谱方案：

方案1：预先预留足够空间 #

在调用set_difference之前，先预估diff的最大可能大小（比如xx.size()，因为set_difference的结果最多和第一个输入序列一样长），然后调用reserve预留空间，这样插入过程中就不会触发扩容：

diff.reserve(xx.size()); // 预留足够空间，避免扩容
auto transformed_inserter = make_transform_output_iterator(std::back_inserter(diff), f);
std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(), transformed_inserter);

// 现在可以放心存储地址或迭代器了
std::vector<double*> elem_ptrs;
for (auto& elem : diff) {
    elem_ptrs.push_back(&elem);
}

// 或者存储迭代器
std::vector<std::vector<double>::iterator> elem_its;
for (auto it = diff.begin(); it != diff.end(); ++it) {
    elem_its.push_back(it);
}

方案2：在自定义迭代器中实时记录 #

如果不想提前预留空间，也可以修改自定义迭代器，让它在每次插入元素后，立即获取该元素的迭代器/地址并存储起来。因为std::back_inserter插入元素后，容器的end()迭代器指向新元素的下一个位置，所以新元素的迭代器就是prev(diff.end())：

修改后的迭代器代码：

template <typename OutputIt, typename TransformFunc, typename Storage>
class TransformAndStoreIterator {
public:
    // 类型定义同上...

    TransformAndStoreIterator(OutputIt it, TransformFunc func, Storage& storage)
        : m_it(std::move(it)), m_func(std::move(func)), m_storage(storage) {}

    template <typename T>
    TransformAndStoreIterator& operator=(const T& value) {
        *m_it = m_func(value);
        // 获取刚插入元素的迭代器（m_it.base()返回底层vector的end()，prev就是新元素的位置）
        auto elem_it = std::prev(m_it.base());
        m_storage.push_back(elem_it); // 存储迭代器，换成&(*elem_it)就是存储地址
        ++m_it;
        return *this;
    }

    // 其他空操作同上...
};

// 辅助函数
template <typename OutputIt, typename TransformFunc, typename Storage>
auto make_transform_store_iterator(OutputIt it, TransformFunc func, Storage& storage) {
    return TransformAndStoreIterator<OutputIt, TransformFunc, Storage>(std::move(it), std::move(func), storage);
}

使用示例：

std::vector<double> xx = {1.0, 3.0, 5.0};
std::vector<double> yy = {2.0, 4.0};
std::vector<double> diff;
std::vector<std::vector<double>::iterator> elem_iterators; // 用来存迭代器的容器

auto inserter = make_transform_store_iterator(std::back_inserter(diff), f, elem_iterators);
std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(), inserter);

// 此时elem_iterators里保存了diff中每个元素的迭代器
// 注意：如果后续diff扩容，这些迭代器会失效，所以如果需要长期使用，还是建议提前reserve

针对函数g(std::vector<double>::iterator)的特殊处理 #

如果你的变换函数g需要接收元素的迭代器（而不是元素值），那逻辑要调整：必须先插入原始元素，再获取迭代器传给g修改元素。

示例代码（基于自定义迭代器）：

// 示例函数g：接收迭代器，修改元素值
void g(std::vector<double>::iterator it) {
    *it = *it * 3.0; // 把元素乘3
}

// 自定义迭代器：先插入原始值，再调用g修改
template <typename OutputIt, typename IterFunc, typename Storage>
class InsertThenTransformIterator {
public:
    // 类型定义同上...

    InsertThenTransformIterator(OutputIt it, IterFunc func, Storage& storage)
        : m_it(std::move(it)), m_func(std::move(func)), m_storage(storage) {}

    template <typename T>
    InsertThenTransformIterator& operator=(const T& value) {
        *m_it = value; // 先插入原始值
        auto elem_it = std::prev(m_it.base());
        m_func(elem_it); // 调用g处理迭代器
        m_storage.push_back(elem_it); // 存储迭代器
        ++m_it;
        return *this;
    }

    // 其他空操作同上...
};

// 辅助函数
template <typename OutputIt, typename IterFunc, typename Storage>
auto make_insert_then_transform_iterator(OutputIt it, IterFunc func, Storage& storage) {
    return InsertThenTransformIterator<OutputIt, IterFunc, Storage>(std::move(it), std::move(func), storage);
}

// 使用方式
auto inserter = make_insert_then_transform_iterator(std::back_inserter(diff), g, elem_iterators);
std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(), inserter);

这样就能完美适配g函数的需求了。

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