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

在内存以后会消耗更多的内存方面，因为你必须存储每个节点两个指针。