針對在迭代器上運行的函數的每個容器優化

所以我知道迭代器的要點是抽象底層容器，因此您不必擔心它是什麼。但是，假設你想寫一個合併排序的優化版本，並且想要做一個適當的排序，如果底層容器是一個鏈表，因爲你可以在鏈表上就地運行合併排序而不需要額外的容器分配。針對在迭代器上運行的函數的每個容器優化

有什麼辦法可以獲取這些信息，以瞭解您是否在鏈接結構上運行和/或訪問標準庫和其他容器的指針？

我假設有一種方式，因爲那是什麼std::sort does？怎麼樣？

來源

2015-04-30 Francisco Aguilera

有人在沒有評論的情況下投下了問題... 這個問題到底出了什麼問題？ –

我沒有downvote，但問題是指出不正確的東西，那不是什麼'std :: sort'。 –

作爲用戶，你不能，但實施可以。例如，如果l是一個列表，gcc-5可以在一段時間內計算出'std :: distance（l.first（），l.end（））'。 –

我也一直希望有辦法做到這一點，但答案是善良的，但不是真的。由於模板扣除規則，這通常是不可能的。每個迭代器可以是一個類的成員，但由於多個類可能具有相同的迭代器，如果一個函數接收到這些迭代器，從字面上和理論上不可能推斷出它來自哪個容器。這有些阻礙了事情。

如果您不需要容器類型，並且可以單獨使用迭代器類型，那麼是的，std::sort可以基於底層容器進行優化。但是，不，std::sort在我知道的任何C++標準庫中沒有針對基於節點的容器的特殊算法。

自己有時有專門版本的容器，見std::list<T>::sort，但通用std::sort不能使用的，由於它可以在任意範圍，std::list<T>::sort只能整個容器上。

我真的希望他們會。當在基於樹的容器上調用時， std::lower_bound和類似的專門化也會很棒。

來源

2015-04-30 22:56:26

所以約定是在容器中放置專門的分類功能。對我來說這是一個大啓示，我一直堅持'std :: sort'，並且認爲它正在優化容器類型。然而，更有趣的是，'C++ 17'提供了一些新的迭代器功能，包括'連續的迭代器'和[容器訪問函數]（http://en.cppreference.com/w/cpp/iterator）（參見：http：//www.cppreference.com/w/cpp/iterator）底端）。鑑於這些新的構造，你認爲這足以使這種情況成爲可能嗎？ –

容器中可能還有專門的排序，但至少你認爲像std :: sort這樣的通用函數能夠發現和/或調用這些函數嗎？ –

排序函數不可能根據接收到的迭代器的類型來優化算法嗎？ – Galik

庫實現者可以執行一些不可移植的事情，並取決於實現的細節。雖然在標準中迭代器類型在容器中被稱爲嵌套類型，但嵌套類型不能被推導出來，實現可以決定將它們作爲具有名稱空間範圍的類型來實現，這些類型可以被引用，並提供嵌套的typedef。然後，實施可以在標準要求的限度內優化操作。

我不知道實現std::sort作爲合併排序的名單任何實現的，但也有在實現中使用其他的技巧，例如std::copy當迭代器是爲持有POD類型在一些圖書館通過實現矢量調用std::memmove而不是一次複製一個元素。

正如我之前提到的，雖然這可以由實現者完成，但編寫自己的代碼試圖做同樣的事情將是不可移植和脆弱的，因爲它取決於一個實現的細節，庫的版本或甚至通過更改編譯器標誌。

來源

2015-04-30 23:19:14

std :: sort只是爲隨機訪問迭代器定義的，它沒有爲列表迭代器定義，所以不存在實現不專用於利用節點。 –

針對在迭代器上運行的函數的每個容器優化

回答

相關問題