我需要使用pthreads添加未知次数的数据结构和顺序他们最早的第一，谁能推荐一个良好的结构(链表/数组列表)吗?
链表在查找新对象的位置时将是O(n)，但在插入它时将是常数。
动态数组/数组列表将O(log(n))找到正确的位置，但最坏的情况是O(n)插入，因为您需要将所有值移动到插入点上方。
如果您不需要随机访问，或者至少直到最后，您可以使用堆，O(log(n))插入，在您完成后，您可以将它们分别在O(log(n))中取出，因此O(n*log(n))用于所有它们。
有可能有一个(可能是基于树的)结构可以在O(log(n))(红黑树?)中完成所有这些。
所以，最终它归结为你想要如何准确地使用它。
编辑:查找红黑树，它看起来像O(log(n))搜索("平摊O(1)"，根据维基百科)，插入和删除，所以这可能是你想要的。
如果您只需要在最后排序，则使用链表来存储维护添加记录的count的pthread。然后创建一个大小为count的数组，将元素复制到新创建的数组中，并从列表中删除它们。最后使用qsort对数组进行排序。
如果您需要维护一个有序的pthread列表，请使用heap
前一种方法的复杂度如下
O(n) for Insert
O(nlog(n)) for Sorting
后一种方法将有
O(nlog(n)) for Insert and Fetching
还可以看到优先级队列
请注意，如果你是开放的使用STL，你可以去STL priority_queue
在内存方面，后者将消耗更多的内存，因为每个节点必须存储两个指针。