集合，在删除/获取时进行排序

Question

在这种情况下，我需要一个threadsafe队列，它在每次调用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>必须实现可比较的接口，并在尝试排序列表时使用对象compareTo函数(在我的代码中，m_comparator是未完成/占位符)。

是否有人知道只对remove()进行排序的线程安全队列，或者如何修复我的自定义集合的开始，以便使用泛型对象compareTo函数对列表进行排序。

Answer 1

看上去你是按必须的方式做的。若要强制使用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);
  }
}

...though --用Collections.sort(m_list, Collections.reverseOrder())进行反向排序和删除最后一个元素可能对您有好处，因为在ArrayList中这样做更快。

最好只是标识最小元素，而不是对整个列表进行排序，这将是O(n)而不是O(n log )。

Answer 2

对象可以在将它们添加到集合后动态更改“优先级”。这也需要线程安全。

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

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