搜索值并在向量中返回索引的最有效方法？

Question

我试图遍历一个向量(k),并检查它是否包含一个值(键),如果是,我想添加在不同向量(val)的相同索引处找到的值,然后添加任何值在那里找到第三个向量(temp).

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

我最近学到了很多,但我仍然没有超级高级的C++,这段代码确实适用于我的目的,但它非常慢.它可以处理大小为10或100的小向量,但对于大小为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));
} 

我想也许使用矢量迭代器可以加快速度,但由于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边界检查,所以它比一点慢[].你显然必须保证你永远不会访问越界索引.