的最快方法載體

我在做一個項目，我需要將數據插入到載體中的排序和查找它...的最快方法載體

我需要最快的排序和搜索算法可能我...我一直在搜索，發現std :: sort基本上是quicksort這是最快的排序之一，但我無法弄清楚哪種搜索算法是最好的？ ??的binarySearch你能幫助我嗎？ TNX ...所以我有3種方法：

void addToVector(Obj o) 
{ 
    fvector.push_back(o); 
} 

void sortVector() 
{ 
    sort(fvector.begin(), fvector().end()); 
} 

Obj* search(string& bla) 
{ 
//i would write binary search here 
return binarysearch(..); 
}

來源

2014-05-08 user3617449

二進制搜索是標準的「快」搜索桶排序算法對於一個數組或向量 – wheybags

使用std :: sort並在std :: binary_search之後就可以了。 – 101010

是否必須對矢量進行排序，或者是否可以使用另一個（未排序的）帶有攤銷O（1）的數據結構？ – Deduplicator

我一直在尋找，並發現std::sort基本上是快速排序。

答：不太。大多數實現使用hybrid algorithm，如 introsort，其結合了quick-sort,heap-sort和insertion sort。

快速排序是最快的排序方法之一。

答：不太。一般來說，它是成立的（即，在平均情況下，快速排序的複雜性爲）。然而，快速排序具有二次最壞情況表現（即，）。此外，對於少量輸入（例如，如果您有一個帶有少量元素的std::vector），快速排序的排序往往會比被認爲「更慢」的其他排序算法實現最差的性能（參見下圖）：

enter image description here

我找不出哪個搜索算法是最好的。它是二進制搜索嗎？

答案：Binary search具有相同的平均值和最差情況下的性能（即，）。還要記住，二進制搜索要求容器應按升序或降序排列。然而，是否優於其他搜索方法（例如，具有時間複雜度的linear search）取決於許多因素。其中一些是：

元素/對象的數量（見下圖）。

元素/對象的類型。

enter image description here

底線：

通常尋找「最快」的算法表示不成熟的優化，並根據其中一個「偉大的」（不成熟的優化是所有邪惡的根源 - Donald Knuth）。正如我希望已經清楚顯示的那樣，「最快」取決於許多因素。

使用std::sort來排序std::vector。

排序您std::vector使用std::binary_search，找出你的std::vector是否存在某種元素或使用std::lower_bound或std::upper_bound找到並從您的std::vector獲取元素之後。