跳到主要内容

C++ 插入迭代器

什么是插入迭代器？​

插入迭代器（Insert Iterators）是一类特殊的迭代器，它们的主要功能是将赋值操作转换为插入操作。普通迭代器在赋值时会覆盖容器中已有的元素，而插入迭代器会在容器中添加新的元素，这使得我们能够在不指定容器大小的情况下动态添加元素。

C++ STL提供了三种主要的插入迭代器：

  1. back_inserter: 在容器尾部插入元素
  2. front_inserter: 在容器头部插入元素
  3. inserter: 在容器指定位置插入元素

为什么需要插入迭代器？​

在使用算法（如std::copy、std::transform等）时，我们常常需要将结果存储到一个容器中。如果目标容器大小不足，就会发生越界访问。插入迭代器解决了这个问题，它允许容器根据需要自动扩展。

插入迭代器的类型​

1. back_inserter​

back_inserter创建一个迭代器，该迭代器使用容器的push_back方法在容器尾部插入元素。

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination;
    
    // 使用back_inserter将source中的元素复制到destination
    std::copy(source.begin(), source.end(), std::back_inserter(destination));
    
    // 输出destination中的元素
    for (int num : destination) {
        std::cout << num << " ";
    }
    // 输出: 1 2 3 4 5
    
    return 0;
}
备注

back_inserter只能用于支持push_back操作的容器，如vector、deque和list。

2. front_inserter​

front_inserter创建一个迭代器，该迭代器使用容器的push_front方法在容器头部插入元素。

cpp
#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

int main() {
    std::list<int> source = {1, 2, 3, 4, 5};
    std::list<int> destination;
    
    // 使用front_inserter将source中的元素复制到destination
    std::copy(source.begin(), source.end(), std::front_inserter(destination));
    
    // 输出destination中的元素
    for (int num : destination) {
        std::cout << num << " ";
    }
    // 输出: 5 4 3 2 1
    
    return 0;
}
警告

注意输出结果的顺序！由于每次都在头部插入，所以结果是原序列的逆序。另外，front_inserter只能用于支持push_front操作的容器，如list和deque，但不能用于vector。

3. inserter​

inserter创建一个迭代器，该迭代器使用容器的insert方法在指定位置前插入元素。

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination = {10, 20, 30};
    
    // 使用inserter在destination的第二个元素前插入source中的元素
    std::copy(source.begin(), source.end(), std::inserter(destination, destination.begin() + 1));
    
    // 输出destination中的元素
    for (int num : destination) {
        std::cout << num << " ";
    }
    // 输出: 10 1 2 3 4 5 20 30
    
    return 0;
}

插入迭代器的内部工作原理​

插入迭代器是包装了容器和插入点的特殊迭代器适配器。当我们对插入迭代器进行赋值操作时，它会调用相应的容器方法来插入元素，而不是替换已有元素。

下面是一个简化的插入迭代器实现示例：

cpp
template <typename Container>
class back_insert_iterator {
private:
    Container* container;
    
public:
    back_insert_iterator(Container& c) : container(&c) {}
    
    back_insert_iterator& operator=(const typename Container::value_type& value) {
        container->push_back(value);
        return *this;
    }
    
    // 其他必要的操作符...
};

// helper函数，用于创建back_insert_iterator
template <typename Container>
back_insert_iterator<Container> back_inserter(Container& c) {
    return back_insert_iterator<Container>(c);
}

实际应用场景​

场景1：过滤容器元素​

使用插入迭代器和std::copy_if算法来过滤容器：

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> evenNumbers;
    
    // 过滤出偶数并插入到evenNumbers中
    std::copy_if(numbers.begin(), numbers.end(), 
                 std::back_inserter(evenNumbers),
                 [](int n) { return n % 2 == 0; });
    
    // 输出结果
    for (int num : evenNumbers) {
        std::cout << num << " ";
    }
    // 输出: 2 4 6 8 10
    
    return 0;
}

场景2：容器连接​

使用插入迭代器连接多个容器：

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> first = {1, 2, 3};
    std::vector<int> second = {4, 5, 6};
    std::vector<int> third = {7, 8, 9};
    std::vector<int> result;
    
    // 将三个容器的内容连接到result
    std::copy(first.begin(), first.end(), std::back_inserter(result));
    std::copy(second.begin(), second.end(), std::back_inserter(result));
    std::copy(third.begin(), third.end(), std::back_inserter(result));
    
    // 输出结果
    for (int num : result) {
        std::cout << num << " ";
    }
    // 输出: 1 2 3 4 5 6 7 8 9
    
    return 0;
}

场景3：构建复杂数据结构​

使用插入迭代器构建复杂的数据结构：

cpp
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<std::pair<std::string, int>> data = {
        {"apple", 5},
        {"banana", 3},
        {"cherry", 7},
        {"apple", 2},
        {"banana", 4}
    };
    
    // 使用map来统计每种水果的总数量
    std::map<std::string, int> fruitCount;
    
    for (const auto& pair : data) {
        fruitCount[pair.first] += pair.second;
    }
    
    // 转换回vector以便排序
    std::vector<std::pair<std::string, int>> sortedData;
    std::copy(fruitCount.begin(), fruitCount.end(), 
              std::back_inserter(sortedData));
    
    // 按数量排序
    std::sort(sortedData.begin(), sortedData.end(),
              [](const auto& a, const auto& b) {
                  return a.second > b.second;
              });
    
    // 输出结果
    for (const auto& pair : sortedData) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // 输出:
    // cherry: 7
    // apple: 7
    // banana: 7
    
    return 0;
}

性能考虑​

虽然插入迭代器非常方便，但在某些情况下可能会导致性能问题：

  1. 对于vector容器：如果不预先分配足够的空间，使用back_inserter可能导致多次重新分配内存。
  2. 对于list和deque容器：front_inserter在头部插入元素效率较高，但对于vector这种操作会非常低效。
提示

对于已知大小的情况，先使用reserve方法预分配空间，然后再使用插入迭代器，可以显著提高性能：

cpp
std::vector<int> destination;
destination.reserve(source.size()); // 预分配空间
std::copy(source.begin(), source.end(), std::back_inserter(destination));

总结​

插入迭代器是C++ STL中非常实用的工具，它们允许算法自动扩展目标容器而不是覆盖现有元素：

  • back_inserter: 适用于需要在容器尾部添加元素的场景
  • front_inserter: 适用于需要在容器头部添加元素的场景
  • inserter: 适用于需要在容器指定位置添加元素的场景

掌握插入迭代器的使用，可以让你的代码更加灵活和健壮，特别是在处理不确定大小的数据集时。

练习​

  1. 使用back_inserter和std::transform算法，将一个整数向量中的每个元素都乘以2，并存储到一个新向量中。
  2. 使用front_inserter将一个字符串向量中的所有元素复制到一个std::list<std::string>中，并解释输出结果的顺序。
  3. 使用inserter将一个向量的元素插入到另一个向量的中间位置。
  4. 实现一个函数，使用插入迭代器将两个已排序的容器合并成一个新的已排序容器。

更多资源​