最有效的方法來搜索一個值並返回其向量中的索引？

我試圖遍歷一個向量（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的錯誤修理。

有沒有人知道我能做些什麼來使這個小小的代碼多更快？

來源

2016-10-17 Dante

您是否需要將數據保存在兩個單獨的向量中？這對於地圖或無序地圖來說似乎是一項完美的工作。 – krzaq

@krzaq不，我認爲我不知道，k和val向量在它們的索引處相等，並且它們也是相同的大小。有什麼方法可以將它們放在一起嗎？這會加速嗎？ – Dante

你花時間查找和複製數據。通過查找時間，地圖可以提供很多幫助。 – krzaq

這裏有一些事情可以做：

預分配數據爲temp，使push_back不會導致重複分配：

如果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()]);

at會進行邊界檢查，因此它比[]慢一點點。你顯然必須保證你永遠不會訪問越界索引。

來源

2016-10-17 05:35:47 Rakete1111

非常有幫助，我對它進行了排序並加快了速度，我保留[]，因爲我永遠不會訪問出界索引，並且我已經預先分配了temp。 – Dante

我並不是故意提交該評論，但我不知道如何在發佈後編輯它們。正如我所說的，我做了所有3件事，而且速度很快，但不足以應付10k或100k。我注意到，如果我運行帶有1000個元素的向量，它在0-1000的瞬間就會消失，但是如果我做了10000個元素，從0到1000需要5倍的時間，你知道這是爲什麼嗎？可能？ – Dante

@Dante我會說一個1000元素的矢量可以存儲在L緩存中，而不是RAM，它比RAM快。但有10,000個元素，它不能存儲在緩存中，所以速度較慢 – Rakete1111

除了Rakete的建議：

如果你的鑰匙矢量進行排序 - 使用std::binary_search代替std::find，然後只需迭代，直到向量的下一個值/結束。

如果您可以自由更改數據結構，請將數據保存在std::unordered_multimap中，並使用equal_range訪問具有所需密鑰的元素。

來源

2016-10-17 05:45:18 krzaq

最有效的方法來搜索一個值並返回其向量中的索引？

回答

相關問題