如何在C++中編寫一個通用的排序函數？

是否有任何可能的方法在C++中使用單一函數對自然意義上的所有類型的數據進行排序？在我的情況下，我定義了一個基於模板數據類型的鏈表結構，並且我想將它包含的數據作爲鏈表排序。如何在C++中編寫一個通用的排序函數？

來源

2014-01-20 erogol

Ahem ['std :: sort']（http://en.cppreference.com/w/cpp/algorithm/sort）？ – Borgleader

@Borgleader - 海報說他有一個鏈表，它不會與'std :: sort'一起工作，因爲它不太可能是一個隨機訪問結構。 – Sean

@肖恩你錯過了這一點。問題是「是否可能」。是的，看看std :: sort。 – Borgleader

-1

是的，你可以很自然地用鏈表實現插入排序。您可以使用與std::sort類似的界面編寫模板化功能。

然後，您可以使用operator<來比較任何類型的元素或Compare函數。

您可以允許您的列表作爲輸入，並返回一個排序列表作爲輸出。

複雜性會下降到O(n^2)與插入排序，但這是IMO最簡單的方法。 ~~我不認爲你可以做更好的隨機存取容器。~~也許合併排序可以實現列表。看起來像一個很好的候選人。

或者，您可以將列表複製/移動到支持隨機訪問迭代器的結構中，並用std::sort對它進行排序並將其轉換回列表。這在技術上具有更好的複雜性，但是由於2次變換操作而具有相當大的常數因子。但對於大名單，最終會更快。

來源

2014-01-20 12:28:41 luk32

你真的不應該在意拷貝或移動，而是'交換'。這也是'std :: sort'的作用。 – pmr

當你計算純粹的計算複雜性時，當然是。當你使用數據結構對小集進行排序時（我知道你可以說我不應該關心小數據集，因爲它們的定義很快），但值得記住的是複製東西也需要時間。而「交換」無論如何都是副本或移動，不是嗎？此外，我認爲在一個設計不好的算法中（有點像我這裏粗略的草圖），你將受到記憶的束縛，交換次數可能變得不那麼佔優勢。我看到一些假設'malloc'很好的例子，並且打破了它們的複雜性。 – luk32

我並沒有試圖說複製或移動對性能無關緊要，而是交換概括了複製構建/移動構建。如果你有一個很好的定義（在數學意義上）「交換」，你的低層算法不需要關心底層機制。 – pmr

有多種尺寸，你可以通過通用的意思是：

通用相對於數據
通用相對於容器

第一種是最簡單的解決。我們需要考慮排序需要什麼工作：我們的數據爲strict weak ordering。現在我們知道我們需要提供給排序算法的函數的性質，並需要一種方法來傳遞函數。在C++中，假設operator<實現這樣的順序或將函子傳遞給實現它的算法已成爲常態。所以簽名會變成：

template<typename T, typename Comp = std::less<T>> 
my_sort(my_list<T>& l, Comp c = Comp());

我們的排序算法必須執行另一個操作：交換元素。正如我們在這個我們自己的小世界中，我們可以假設我們所有的類型都有一個成員函數T::swap(T& rhs)，它正是這樣做的。在現實世界中，我們將使用免費函數std::swap（具有非限定的調用和使用指令，但這是一個晦澀的技術性）。

第二個問題更棘手，你實際上不想解決它，因爲你只希望你的排序算法在你的列表實現上工作。我鼓勵您深入探討std::sort及其要求，瞭解爲什麼它以這種方式實施，以及爲什麼它不適用於std::list。

來源

2014-01-20 12:44:48 pmr

請注意，對於列表，最好修復內部列表指針而不交換數據（可能不可交換）。 – Jarod42

如何在C++中編寫一個通用的排序函數？

回答

相關問題