List implementation that maintains ordering

Question

Is there an existing List implementation in Java that maintains order based on provided Comparator?

Something that can be used in the following way:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

so that someT gets inserted such that the order in the list is maintained according to cmp

(On @andersoj suggestion I am completing my question with one more request)

Also I want to be able to traverse the list in sorted order without removing the elements, i.e:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

should pass.

All suggestions are welcome (except telling me to use Collections.sort on the unordered full list), though, I would prefer something in java.* or eventually org.apache.* since it would be hard to introduce new libraries at this moment.

Note: (UPDATE4) I realized that implementations of this kind of list would have inadequate performance. There two general approaches:

1. Use Linked structure (sort of) B-tree or similar
2. Use array and insertion (with binary search)

No 1. has problem with CPU cache misses No 2. has problem with shifting elements in array.

UPDATE2: TreeSet does not work because it uses the provided comparator (MyComparator) to check for equality and based on it assumes that the elements are equal and exclude them. I need that comparator only for ordering, not "uniqueness" filtering (since the elements by their natural ordering are not equal)

UPDATE3: PriorityQueue does not work as List (as I need) because there is no way to traverse it in the order it is "sorted", to get the elements in the sorted order you have to remove them from the collection.

UPDATE:

Similar question:
A good Sorted List for Java
Sorted array list in Java

Answer 1

You should probably be using a TreeSet:

The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

Example:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

Note that this is a set, so no duplicate entries are allowed. This may or may not work for your specific use-case.