c++ - 从一维 vector vector 复制到二维 vector 对的第一个元素vector >矩阵

Question

我有多个3个一维 vector (vector<int> starts, vector<int> ends, vector<int> points)。每个元素都有特定数量的元素。

我想按这样的顺序创建一个二维 vector vector<pair<int,int>>matrix:

(从matrix的开头到start的大小) matrix的第一个元素是vector<int> starts的元素，而的第二个元素是“-1”

现在将vector<int> ends的元素追加到matrix，以便matrix的的第一个元素为vector<int> ends的元素，而的第二个元素为“-2”

现在将vector<int> points的元素追加到matrix，以便matrix的的第一个元素是vector<int> points的元素，而的第二个元素是点的索引。

视觉表现 :-

输入:

开始于:{1, 2, 3}结束于:{4, 5, 6}点数:(7, 8, 9}
输出:

矩阵:{ {1, -1}, {2, -1}, {3, -1}, {4, -2}, {5, -2}, {6, -2}, {7, 0}, {8, 1}, {9, 2} }

目前，我正在使用带有for循环功能的push_back，该功能工作得很好，但是当输入大小很大时，代码将非常缓慢。

我使用的代码如下:

vector<pair<int,int>> fast_count_segments(
    vector<int> starts, 
    vector<int> ends, 
    vector<int> points) 
{
   int i = 0;
   vector<pair<int,int>>matrix;

   for(i; i<starts.size(); i++) {
       matrix.push_back(make_pair(starts[i],-1));
   }
   for(i; i<starts.size()+ends.size(); i++) {
       matrix.push_back(make_pair(ends[i-starts.size()],-2));
   }
   for(i; i<starts.size()+ends.size()+points.size(); i++) {
        matrix.push_back(make_pair(
            points[i-starts.size()-ends.size()],
            i-(starts.size()+ends.size())
        ));
   }
   return matrix;
}

您能否在不遍历每个元素的情况下帮助您如何快速满足这些要求来填充2D vector 。我正在使用C++ 11。提前致谢 !!

Answer 1

初步关注:正如@datenwolf和其他人所指出的那样-生成的数据结构不是2D矩阵(除非您表示的是稀疏表示形式的 bool(boolean) 矩阵)。您确定这就是您要填充的内容吗？

无论如何，以下是一些可以提高速度的想法:

不要按值取输入 vector !这是无用的复制...将其.data()或.cbegin()迭代器作为参数，或将 span<int> 参数作为参数。

在目标 vector 上使用 reserve() 方法可以避免多次重新分配。

使用 .emplace_back() 而不是.push_back()来构造这些点，而不是构造然后移动每个点。虽然，老实说，编译器可能无论如何都会优化这些结构。

将输入 vector 的.size()值放入局部变量。这仅在出于某种原因而使编译器怀疑整个函数执行期间大小不会恒定时才有用。

确保将优化开关传递给编译器(例如-O2或-O3传递给GCC和clang)。这对您来说似乎很明显，但有时却很明显，您忘记检查它是否已完成。

一些美学评论:

无需对所有 vector 使用相同的计数器。 for(int i = 0; i < whatever; i++)可以多次使用。

不需要原始的for循环，可以将for(const auto& my_element : my_vector)用于前两个循环。第三个循环比较棘手，因为您需要索引。您可以将std::difference()与迭代器配合使用，或者使用pythont枚举here进行描述。

您可能会考虑将std::transform()与back_emplacer输出迭代器一起使用，而不是使用所有三个循环。无循环码!这将意味着在转换器lambda中使用std::difference()而不是第三个循环。