c++ - 搜索值并在 vector 中返回其索引的最有效方法？

Question

我正在尝试遍历一个 vector (k)，并检查它是否包含一个值 (key)，如果包含，我想添加在不同 vector (val) 的相同索引处找到的值，然后将在那里找到的任何值添加到第三个 vector (temp)。

for(int i = 0; i < k.size(); ++i)
{
  if(k.at(i) == key)
   {
     temp.push_back(val.at(i));
   } 
}

我最近学到了很多东西，但我在 C++ 方面仍然不是很先进，这段代码确实适合我的目的，但速度非常慢。它可以处理大小为 10 或 100 的小 vector ，但处理更大的 vector (如 1000、10000 甚至 1000000)需要的时间太长。

我的问题是，是否有更快、更有效的方法来做到这一点？

我已经试过了:

std::vector<int>::iterator it = k.begin(); 
while ((iter = std::find(it, k.end(), key)) != k.end()) 
{ 
 int index = std::distance(k.begin(), it); 
 temp.push_back(val.at(index));
} 

我想也许使用 vector 迭代器会加快速度，但由于我不确定如何修复的 bad_alloc 错误，我无法让代码工作。

有谁知道我可以做些什么来使这段代码大大更快？

Answer 1

以下是您可以做的几件事:

1. 为 temp 预分配数据，这样 push_back 就不会导致重复分配:

   temp.reserve(k.size());
   

2. 如果 k 已排序，您可以使用该事实来加快速度:

   auto lowerIt = std::lower_bound(k.begin(), k.end(), key);
   auto upperIt = std::upper_bound(k.begin(), k.end(), key);
   
   for (auto it = lowerIt; it != upperIt; ++it)
       temp.push_back(val[it - k.begin()]);
   

3. at 进行边界检查，因此它比 [] 慢一点。显然，您必须保证您永远不会访问越界索引。