C中的動態數據結構用於排序time_t對象？

Question

我需要使用pthreads添加一個未知數量的數據結構並且最先排序它們，任何人都可以爲此推薦一個好的結構（鏈表/數組列表）嗎？

Answer 1

鏈表將O(n)在這裏找到新的目標是去的地方，但在將其插入不變。

動態數組/列表將會是O(log(n))找到正確的地方，但最壞的情況O(n)插入，因爲您需要將所有值移過插入點。

如果你不需要隨機訪問，或者至少不是直到最後，你可以使用一個堆，O(log(n))插入，大功告成後，你可以將它們拉出來在每個O(log(n))，所以O(n*log(n))爲所有這些。

而且它可能有一個（可能是基於樹的）結構，它可以做到這一切在O(log(n))（紅黑樹？）。

那麼，到底它歸結爲如何，確切的說，你想用它。

編輯：擡頭red-black trees它看起來像是O(log(n))搜索（根據維基百科，「已攤銷O(1)」），插入和刪除，這可能是你想要的。

Answer 2

如果你只需要在年底訂購，使用鏈表存儲並行線程保持增加的記錄count。然後創建一個大小爲count的數組，將這些元素複製到新創建的數組中並從列表中刪除它們。 最後使用qsort對數組進行排序。

如果你需要的並行線程使用heap

保持一個有序列表中的前一種方法將有如下的複雜性

O(n) for Insert 
O(nlog(n)) for Sorting 

後一種方法將有

O(nlog(n)) for Insert and Fetching 

你也可以見priority queue

請注意，如果你在使用STL開放的，你可以去STL priority_queue

在內存以後會消耗更多的內存方面，因爲你必須存儲每個節點兩個指針。