是否有任何可能的方法在C++中使用單一函數對自然意義上的所有類型的數據進行排序?在我的情況下,我定義了一個基於模板數據類型的鏈表結構,並且我想將它包含的數據作爲鏈表排序。如何在C++中編寫一個通用的排序函數?
回答
是的,你可以很自然地用鏈表實現插入排序。您可以使用與std::sort類似的界面編寫模板化功能。
然後,您可以使用operator<
來比較任何類型的元素或Compare
函數。
您可以允許您的列表作爲輸入,並返回一個排序列表作爲輸出。
複雜性會下降到O(n^2)
與插入排序,但這是IMO最簡單的方法。 我不認爲你可以做更好的隨機存取容器。也許合併排序可以實現列表。看起來像一個很好的候選人。
或者,您可以將列表複製/移動到支持隨機訪問迭代器的結構中,並用std::sort
對它進行排序並將其轉換回列表。這在技術上具有更好的複雜性,但是由於2次變換操作而具有相當大的常數因子。但對於大名單,最終會更快。
你真的不應該在意拷貝或移動,而是'交換'。這也是'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
。
請注意,對於列表,最好修復內部列表指針而不交換數據(可能不可交換)。 – Jarod42
- 1. 如何在C編寫一個函數
- 2. 如何在C中編寫函數的通用鉤子?
- 3. 如何在C++中編寫一個默認的構造函數?
- 4. 如何在c#中編寫通用函數?
- 5. 如何編寫在C++中使用其他函數的函數
- 6. 如何在c#中編寫一個通用函數,它將根據類的類型調用不同的函數?
- 7. 如何在c#中編寫ajax函數#
- 8. 如何在C中編寫函數?
- 9. 如何編寫一個函數在Python
- 10. 如何編寫通用的「getData」函數?
- 11. 如何在C#中編寫這個C++函數?
- 12. 如何用Python語言編寫一個比較函數來排序日期
- 13. 在目標c中編寫一個簡單的C++函數
- 14. 如何編寫一個返回另一個函數的函數?
- 15. 如何在php中編寫一個通用的db插入函數
- 16. 如何編寫通用轉換函數?
- 17. 如何編寫一個函數用它的參數調用一個函數?
- 18. 如何編寫一個排序並附加到新列表的函數?
- 19. 如何用C++編寫構造函數?
- 20. 編寫一個原型函數(C++)
- 21. 在java中編寫通用函數
- 22. 如何編寫一個創建空隊列的c函數?
- 23. 如何編寫一個清除內存池的函數C
- 24. 如何編寫一個Objective-C的便利構造函數
- 25. 如何在函數中編寫一個Traversable實例,在Haskell中?
- 26. C++如何寫一個構造函數?
- 27. 如何在swift中編寫這個objective-c函數?
- 28. 如何在swift中編寫這個void objective-c函數
- 29. 在Django中,我如何爲每個函數編寫一個?
- 30. 幫助在C#中編寫C函數#
Ahem ['std :: sort'](http://en.cppreference.com/w/cpp/algorithm/sort)? – Borgleader
@Borgleader - 海報說他有一個鏈表,它不會與'std :: sort'一起工作,因爲它不太可能是一個隨機訪問結構。 – Sean
@肖恩你錯過了這一點。問題是「是否可能」。是的,看看std :: sort。 – Borgleader