C++ 插入迭代器

C++插入迭代器

插入迭代器（Insert Iterators）是C++标准模板库(STL)中的一类特殊迭代器适配器，允许将元素插入到容器而非覆盖现有元素。它们与常规输出迭代器的关键区别在于：当通过插入迭代器赋值时，会触发容器的插入操作而非赋值操作。

基本概念

插入迭代器通过重载赋值运算符(operator=)和递增运算符(operator++)实现以下行为：

• 赋值操作转换为容器插入操作
• 递增操作通常为空操作（no-op）

STL提供三种标准插入迭代器：

类型	头文件	描述
back_insert_iterator	<iterator>	通过push_back()在容器尾部插入
front_insert_iterator	<iterator>	通过push_front()在容器头部插入
insert_iterator	<iterator>	在指定位置通过insert()插入

创建与使用

辅助函数

为方便创建插入迭代器，STL提供三个工厂函数：

• std::back_inserter()
• std::front_inserter()
• std::inserter()

#include <vector>
#include <deque>
#include <iterator>

int main() {
    std::vector<int> vec;
    std::deque<int> deq;
    
    // 创建插入迭代器
    auto back_it = std::back_inserter(vec);  // 使用push_back
    auto front_it = std::front_inserter(deq); // 使用push_front
    auto insert_it = std::inserter(vec, vec.begin()); // 在指定位置插入
    
    *back_it = 42;    // vec.push_back(42)
    *front_it = 10;   // deq.push_front(10)
    *insert_it = 7;   // vec.insert(vec.begin(), 7)
    
    return 0;
}

详细类型说明

back_insert_iterator

专为支持push_back()的容器设计（如vector, deque, list）

classDiagram class back_insert_iterator { -container* cont +back_insert_iterator(Container& x) +operator=(const typename Container::value_type& value) +operator*() → back_insert_iterator& +operator++() → back_insert_iterator& +operator++(int) → back_insert_iterator& }

示例：

#include <algorithm>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> src = {1, 2, 3};
    std::vector<int> dest;
    
    // 使用back_inserter复制元素
    std::copy(src.begin(), src.end(), std::back_inserter(dest));
    
    // dest现在包含：1, 2, 3
    return 0;
}

front_insert_iterator

用于支持push_front()的容器（如deque, list）

#include <list>
#include <algorithm>

int main() {
    std::list<int> lst;
    int arr[] = {1, 2, 3};
    
    // 将数组元素反向插入list头部
    std::copy(std::begin(arr), std::end(arr), 
              std::front_inserter(lst));
              
    // lst内容：3 → 2 → 1
    return 0;
}

insert_iterator

最通用的插入迭代器，适用于所有标准容器

#include <set>
#include <iterator>

int main() {
    std::set<int> s = {1, 2, 4, 5};
    auto it = s.find(2);
    
    // 在元素2后插入3
    std::insert_iterator<std::set<int>> insert_it(s, ++it);
    *insert_it = 3;
    
    // s现在包含：1, 2, 3, 4, 5
    return 0;
}

技术细节

插入迭代器的核心实现原理是重载赋值运算符： 解析失败 (语法错误): {\displaystyle \begin{align*} &\texttt{insert\_iterator\& operator=(const T\& value)} \{\\ &\quad \texttt{iter = container->insert(iter, value);}\\ &\quad \texttt{++iter;}\\ &\quad \texttt{return *this;}\\ &\} \end{align*} }

实际应用案例

案例1：合并多个容器

#include <vector>
#include <algorithm>

void merge_containers() {
    std::vector<int> part1 = {1, 3, 5};
    std::vector<int> part2 = {2, 4, 6};
    std::vector<int> full;
    
    // 合并并保持排序
    std::merge(part1.begin(), part1.end(),
               part2.begin(), part2.end(),
               std::back_inserter(full));
    
    // full包含：1, 2, 3, 4, 5, 6
}

案例2：转换并存储结果

#include <vector>
#include <algorithm>
#include <iterator>

void transform_example() {
    std::vector<int> src = {1, 2, 3};
    std::vector<int> squared;
    
    // 计算平方并存储
    std::transform(src.begin(), src.end(),
                   std::back_inserter(squared),
                   [](int x) { return x * x; });
    
    // squared包含：1, 4, 9
}

注意事项

• 性能考虑：频繁插入可能导致容器重新分配内存（特别是vector）
• 有效性：插入操作可能使所有迭代器失效（取决于容器类型）
• 兼容性：确保容器支持相应的插入操作（如front_inserter需要push_front）

参见

• C++标准模板库
• C++迭代器
• C++容器适配器