多线程Java threadsafe集合，在移除/获取时进行排序

Question

我的情况是，我需要一个线程安全队列，它在每次调用remove（）方法时运行排序，并且只有在调用该方法时才运行排序。这是因为在由于外部因素将对象添加到集合后，对象可以动态更改“优先级”。这也需要线程安全。扩展PriorityBlockingQueue这样的东西没有意义，因为添加内容时，它将运行比较函数。我找不到任何这样的集合/队列，所以我尝试通过环绕数组列表来实现自己的集合/队列：

public class BlockingSortOnTakeQueue<E> implements Queue<E>
{
    private ArrayList<E> m_list;

    public BlockingSortOnTakeArrayList()
    {
        m_list = new ArrayList<>();
    }


    @Override
    public synchronized E remove() 
    {
        m_list.sort(m_comparator);
        return m_list.remove(0);
    }

    ....

不幸的是，我很难弄清楚如何确保对象类型<E>必须实现可比较接口，并在尝试对列表排序时使用该对象比较函数（在代码中，我有m_comparator，未完成/占位符）

是否有人知道仅在remove（）上排序的线程安全队列，或者如何修复我的自定义集合的开头，以便使用泛型对象比较函数对列表进行排序

Answer 1

objects can dynamically change "priority" after they have been added to the collection due external factors. This also needs to be threadsafe.

那么，当排序算法运行时，如果这些“外部因素”改变了集合中的对象，会发生什么呢？它可能会破坏列表，而您的示例代码没有显示如何防止这种情况发生。如果要避免这个问题，这些“外部因素”必须与remove（）函数在同一个对象上同步

此外，如果您的代码成功删除了最高优先级的项，然后在您可以对其执行计划的任何操作之前，一个“外部因素”运行，并导致仍在集合中的其他对象具有更高的优先级，这会给您带来问题吗？如果是这样的话，那么除了同步remove（）函数之外，还需要同步调用remove（）的任何代码块，和执行该操作

Answer 2

看起来你是按你应该做的方式做的。要强制Comparable接口，请写入

public class BlockingSortOnTakeQueue<E extends Comparable<E>> implements Queue<E> {
  ...
  @Override
  public synchronized E remove() {
    Collections.sort(m_list);
    return m_list.remove(0);
  }
}

。。。尽管使用Collections.sort(m_list, Collections.reverseOrder())按相反顺序排序并删除最后一个元素可能会对您有利，因为在ArrayList中这会更快

最好只确定最小元素，而不是对整个列表进行排序，整个列表应该是O（n）而不是O（n logn）