C++中通过索引向量从vector<cv::Point2d>快速构建新向量的最优方法

我有一个存储所有图像投影点的vector<cv::Point2d>，还有一个存储簇点对应索引的二维向量std::vector<std::vector<int>>，想通过这些索引构建每个簇对应的vector<cv::Point2d>。目前用的是预分配内存后遍历索引的方法，想知道有没有更高效的实现来提升运行速度，现有代码如下：

// std::vector<std::vector<int>> & indices_vec 来自其他函数

for (int i = 0; i < indices_vec.size(); i++) {
    std::vector<cv::Point2d> image_points_vec(indices_vec[i].size());
    int cnt = 0;
    for (auto & idx : indices_vec[i]) {
      image_points_vec[cnt] = points[idx];
      cnt++;
    }

// 处理 image_points_vec
}

优化方案 #

• 用std::transform替代手动遍历：标准库算法底层经过高度优化，代码更简洁的同时，编译器更容易做循环展开等优化，性能更优。搭配reserve预分配内存避免扩容开销：

for (auto& indices : indices_vec) {
    std::vector<cv::Point2d> image_points_vec;
    image_points_vec.reserve(indices.size());
    std::transform(indices.begin(), indices.end(), std::back_inserter(image_points_vec),
        [&points](int idx) { return points[idx]; });
    // 处理 image_points_vec
}

• 用std::generate_n简化预分配后的赋值：如果习惯预分配内存的写法，用std::generate_n替代手动维护cnt变量，代码更整洁，同样能获得编译器优化：

for (auto& indices : indices_vec) {
    std::vector<cv::Point2d> image_points_vec(indices.size());
    auto idx_it = indices.begin();
    std::generate_n(image_points_vec.begin(), indices.size(),
        [&points, &idx_it]() { return points[*idx_it++]; });
    // 处理 image_points_vec
}

• 开启编译器优化选项：编译时加上-O2或-O3（GCC/Clang），编译器会自动对循环做展开、冗余变量消除等优化，这对提升运行速度的效果往往比手动调整代码更显著。

需要说明的是，所有方案的时间复杂度都是O(n)（n为索引总数），因为必须遍历每个索引完成点映射，但标准库算法的实现经过高度优化，配合编译器优化后，能比手动循环更快。

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