2

Consider I have a library call which accepts:

  1. a list of items (of mixed/multiple types T1, T2, T3,..), and
  2. a custom comparator C,

and, in addition to doing some work, sorts the list it accepts (first by type, and then using the custom comparator C).

Now, I need items of type T1 sorted by type and then using the custom order, while items of all other types (T2, T3,..) sorted by type only (i. e., once sorted by type, consequently sorted only with a no-op, order-preserving comparator).

In other words, I need smth like this (T1 is java.lang.Integer, T2 is java.lang.String):

import java.util.Comparator;
import java.util.List;

import static java.util.Arrays.asList;
import static java.util.Comparator.comparing;
import static java.util.Comparator.comparingInt;

class C {
    /**
     * The library call.
     */
    static <T> void processAndSort(final List<T> items,
                       final Comparator<? super T> secondaryComparator) {
        final Comparator<T> typeComparator = comparing(it -> it.getClass().getName());

        items.sort(typeComparator.thenComparing(secondaryComparator));

        // Do some extra work.
    }

    public static void main(final String ... args) {
        final List<?> items = asList(13, "Lorem",
                         8, "ipsum",
                         5, "dolor",
                         3, "sit",
                         2, "amet",
                         1, "consectetur",
                         1, "adipiscing");

        processAndSort(items, (final var left, final var right) -> {
            final Class<?> clazz = left.getClass();

            /*
             * Should be already sorted by type.
             */
            if (!clazz.equals(right.getClass())) {
                throw new IllegalStateException();
            }

            if (clazz.equals(Integer.class)) {
                /*
                 * Compare integers using a custom comparator.
                 */
                return comparingInt(Integer::intValue).compare((Integer) left, (Integer) right);
            }

            /*
             * For all other types, retain the original order.
             */
            return 0;
        });

        System.out.println(items);
    }
}

The above code, when run, will produce the following output:

[1, 1, 2, 3, 5, 8, 13, Lorem, ipsum, dolor, sit, amet, consectetur, adipiscing]

Now, provided that both Merge Sort and Timsort algorithms (used by the JDK to sort non-primitives) are stable, is it okay for my custom comparator to return 0 for the pairs where the order should be preserved?

Do any other alternatives exist?

4

2 回答 2

2

是的，可以使用这样的 a 对 aComparator进行排序List。

Collections.sort()（并且List.sort()措辞非常相似）只要求

列表中的所有元素必须使用指定的比较器进行相互比较（即，c.compare(e1, e2) 不得为列表中的任何元素 e1 和 e2 抛出 ClassCastException）。

继续

这种排序保证是稳定的：相同的元素不会因为排序而重新排序。

合同也没有Comparator施加任何进一步的限制来禁止这样的实现——它只是警告这样的顺序不“与 equals 一致”，因此不能与某些地图或集合一起使用。

于 2021-11-17T15:11:45.590 回答
1

对，但是。

两个重要的问题：

  1. 是的，比较器具有“同等级别”的概念，这意味着：在“相同的 hashCode() 并且为真”的意义上，对象可能不一定相等，a.equals(b)但比较器表明它们处于同一级别 ( compare(a, b) == 0)。然而，这意味着什么取决于使用比较器的东西。对于 List.sort 具体来说，这仅意味着“处于同一级别”的所有内容将彼此相邻，此外，排序是稳定的，这意味着，在您开始排序之前它们的顺序是它们之后得到的顺序. 但这正是 List 的排序所做的- 例如TreeSet声明您只能拥有 1 个这样的元素；如果比较器说 2 个项目处于同一级别，则就 TreeSet/TreeMap 而言，它们是相等的，因此您不能在一个树集中有 2 个项目compare(a, b) == 0，即使!a.equals(b). 因此，虽然这个问题的答案是“是”，但请注意，您不能普遍使用这个“比较者说它们处于同一水平”。

  2. 比较器报告不相等的 a/b 是完全可以接受的compare(a, b) == 0，但还有其他规则不值得讨论。所有比较器必须始终遵守这些规则；无论您将比较器用于什么用途，如果不这样做都是一个问题：

  • compare(a, a) == 0必须一直持有。
  • 如果compare(a, b) < 0，则compare(b, a) > 0必须始终成立。
  • 如果compare(a, b) < 0和compare(b, c) < 0，则compare(a, c) < 0必须成立。

这个比较器：

Comparator<Object> communism = (a, b) -> 0;

确实遵守所有这些规则，所以，当然，你可以这样做。

于 2021-11-17T15:24:38.477 回答