複雜STL max_element

的所以根據這裏的鏈接：http://www.cplusplus.com/reference/algorithm/max_element/，該max_element功能是O（n），顯然是所有STL容器。它是否正確？它不應該是O（log n）集合（實現爲二叉樹）嗎？複雜STL max_element

在一個有點相關的說明，我一直用它更容易回答問題cplusplus.com，但我會好奇，認爲該網站的別人。

來源

2010-07-22 sas4740

cplusplus。COM是我的主頁在大C++項目:) – 2010-07-22 20:50:19

它是線性的，因爲它觸及每個元素。

使用相同的比較器甚至可以在固定時間內使用.rbegin()，因此甚至在集合或其他有序容器上使用它是毫無意義的。

如果你不使用相同的比較功能，但也不能保證該訂單將重合的話，再次，它已經觸及每一個元素，且必須至少線性的。

雖然算法可以專門針對不同的迭代器分類是沒有辦法專注他們基座上的迭代器區間是否是有序的。

大多數算法上無序範圍（max_element在內），少數需要被排序的範圍（例如set_union，set_intersection）一些需要爲範圍（例如push_heap，pop_heap）其它性質工作。

來源

2010-07-22 20:49:18

所以rbegin（）是保證指向最大元素？此外，是否會使用reverse_iterator從最大值到最小值？編輯：有點搜索我自己表明這是這種情況 – sas4740 2010-07-23 00:45:05

@ sas4740：對於一個'std :: set'或其他有序的容器是正確的，因爲元素以遞增順序存儲。（默認的比較器是'std :: less';如果你使用不同的比較器，「增加」可能不是一種有意義的方式來描述它。）'reverse_iterator'總是以相反的順序進行;由於集合的排序順序遞增，反向迭代器按遞減順序排列。 – 2010-07-23 05:34:42

這是一個STL算法，所以它不知道集裝箱什麼。所以這個線性搜索是它可以在前向迭代器上對夫婦做的最好的搜索。

來源

2010-07-22 20:53:37 jyoung

所有STL容器的max_element函數都是O（n）。

這是不正確的，因爲max_element適用於迭代器，而不是容器。如果你給它一個集合的迭代器，它無法知道它們來自一個集合，因此將遍歷所有這些集合以尋找最大值。所以，正確的一句是：

的max_element函數爲O（n）的所有前向迭代

此外，如果你知道你在操縱一組，你已經可以訪問該方法給你最大的元素比O（n）更快，那爲什麼要用max_element？

來源

2010-07-22 20:53:45

STL算法不知道你，它是否是有序的，並使用了什麼樣的順序限制了什麼容器中的迭代器。它是一種線性算法，它檢查範圍內的所有元素，同時記錄迄今爲止所見的最大值。

請注意，即使你可以使用元編程技術來檢測什麼類型，其中從所獲得的迭代器容器的不是你可以跳到最後一個元素，以獲得最大的保證：

int values[] = { 1, 2, 3, 4, 5 }; 
std::set<int, greater<int> > the_set(values, values+5); 
std::max_element(the_set.begin(), the_set.end()); //??

即使迭代器來自集合，它也不是最後一個，而是第一個保持最大值的元素。對於更復雜的數據類型，可以使用與最小值/最大值無關的其他一些鍵來對該集合進行排序。

來源

2010-07-22 20:59:50

複雜STL max_element

回答

相關問題