Q

C++提供了std :: sort，但它是否也提供了有效搜索的內容？

2016-11-12 20 views 0 likes

0

我有一個矢量對象，實現operator<和operator==。 C++提供了std :: sort來有效地對該向量進行排序。C++提供了std :: sort，但它是否也提供了有效搜索的內容？

std中是否還有一個函數來有效地重複搜索一個向量？

我將在該排序的向量上進行許多搜索，所以std :: find似乎不是一個好的選擇，因爲它只是遍歷迭代器，直到找到匹配。

2016-11-12 Michael

+1

有沒有一個原因，你爲什麼將它存儲在一個向量中，而不是在一個集合/ multiset？ – lorro

+2

'std :: lower_bound'或'std :: binary_search'可能會有所幫助。 – Jarod42

+0

@lorro：......或他們的無序_...同行。 – DevSolar

A

回答

4

當然，也有。

例如，看看lower_bound和upper_bound函數。

另外binary_search可能是有用的。

所有這些函數在排序後的輸入上工作並具有對數複雜度。

2016-11-12 17:31:17

2

嘗試std::binary_search從#include <algorithm>

2016-11-12 17:29:30 woockashek

+4

只有當您只需要yes/no時纔有用。 – Yakk

相關問題