javascript - 你能在 JavaScript 中对不透明对象实例数组进行排序吗？不是按属性(property)

Question

这不是按属性排序的问题!!

假设我有一个对象实例数组。许多实例在数组中不止一次。

var array = [
  opaqueObjectA,
  opaqueObjectB,
  opaqueObjectA,
  opaqueObjectC,
  opaqueObjectB,
  opaqueObjectC,
  opaqueObjectA,
];

我不关心顺序，我关心的是同一实例的对象最终彼此相邻。换句话说，排序之后，一个可能的结果是

var array = [
  opaqueObjectB,
  opaqueObjectB,
  opaqueObjectC,
  opaqueObjectC,
  opaqueObjectA,
  opaqueObjectA,
  opaqueObjectA,
];

我不关心 A 或 B 或 C 在前，我只关心相同实例的对象在排序后是否彼此相邻。

所以问题是

1. JavaScript sort 能保证处理这种情况吗？

2. 如果不行我该怎么做？排序函数要求我在 a < b 时返回 -1，a > b 中的 1 和在 a === b 时返回 0 但鉴于对象是不透明的，并且由于我无权访问指针值或其他内容，我没有什么可以比较它们以获得小于或大于结果，只有相等的结果。

我可以为每个不透明的对象添加一些 sortId，但是向对象添加属性似乎不太好，我不知道我是否在拼凑一个属性。我可以制作另一组对象，每个对象都有一个 id 和对一个实例的引用，对它们进行排序，然后将它们的实例收集到一个新数组中。不得不去构建一个完整的对象数组来排序似乎也很蹩脚。

实际上，我还希望能够按多个实例进行排序，这是一个属性，但仍然无法比较。示例:

var array = [
  { thing: opaqueThingA, stuff: opaqueStuffG, },
  { thing: opaqueThingA, stuff: opaqueStuffH, },
  { thing: opaqueThingB, stuff: opaqueStuffG, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
  { thing: opaqueThingB, stuff: opaqueStuffH, },
  { thing: opaqueThingA, stuff: opaqueStuffG, },
  { thing: opaqueThingA, stuff: opaqueStuffH, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
];

我希望能够先按事物对它们进行排序，然后再按事物进行排序。所以一个可能的结果是

var array = [
  { thing: opaqueThingB, stuff: opaqueStuffG, },
  { thing: opaqueThingB, stuff: opaqueStuffH, },
  { thing: opaqueThingA, stuff: opaqueStuffG, },  // Note the G' s 
  { thing: opaqueThingA, stuff: opaqueStuffG, },  // Are next to
  { thing: opaqueThingA, stuff: opaqueStuffH, },  // each other
  { thing: opaqueThingA, stuff: opaqueStuffH, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
];

这在 C/C++ 中是微不足道的，因为我可以只比较地址的实例。有没有一种方法可以在 JavaScript 中执行此操作，而不会弄脏带有 hacking 属性的对象，也不会创建仅用于排序的临时数组？

Answer 1

您不能使用 Array.prototype.sort 来做到这一点，因为发送到比较器函数的参数只是对象，您需要自己在某个地方跟踪对象。

var objectA = {name: 'objectA'}, objectB = {name: 'objectB'}, objectC = {name: 'objectC'};
var original = [objectA, objectB, objectA, objectC, objectB, objectC, objectA];

var instanceSort = function (original) {
        var seen = [], comparator = function (a, b) {
                if (seen.indexOf(a) === -1) seen.push(a);
                if (seen.indexOf(b) === -1) seen.push(b);
                return seen.indexOf(a) - seen.indexOf(b);
        }
        return original.sort(comparator);
}

var sorted = instanceSort(original);
console.log(sorted);

如果你需要多次调用这个函数，你可以像这样将它添加到Array.prototype，而不是污染作用域:

Array.prototype.instanceSort = function (original) { ... }

然后像这样在你的数组上调用它:var sorted = original.instanceSort()

---

@steady rain 提示说这是低效的，所以这是一个改进的版本:

var instanceSort = function (original) {
    var i, o, comparator, sorted;

    for (i = original.length - 1; i >= 0; i--) {
        o = original[i];
        if (!o.hasOwnProperty('__instanceSortIndex')) o.__instanceSortIndex = i;
    }

    comparator = function (a, b) {
        return a.__instanceSortIndex - b.__instanceSortIndex;
    }

    sorted = original.sort(comparator);

    for (i = original.length - 1; i >= 0; i--) {
        delete original[i].__instanceSortIndex;
    }

    return sorted;
}

这假设您永远不需要对可能最终被此函数排序的任何对象使用名为 __instanceSortIndex 的属性。理论上有点脏，但在实践中使用是安全的。

---

这是另一个，但它仅在您定位 modern browsers which support WeakMap 时有效并且您喜欢将函数作为参数发送给 .sort() 的想法:

var objectA = {name: 'objectA'}, objectB = {name: 'objectB'}, objectC = {name: 'objectC'};
var original = [objectA, objectB, objectA, objectC, objectB, objectC, objectA];

var instanceSort = function (a, b) {
        if (!instanceSort.history) {
                instanceSort.history = new WeakMap();
                instanceSort.uid = 0;
        }

        var h = instanceSort.history, aIndex, bIndex;
        if (h.has(a)) aIndex = h.get(a);
        else h.set(a, aIndex = ++instanceSort.uid);
        if (h.has(b)) bIndex = h.get(b);
        else h.set(b, bIndex = ++instanceSort.uid);

        return aIndex - bIndex;
}

var sorted = original.sort(instanceSort);

WeakMap 可以将现有对象作为键保存，但不会添加到对象引用计数中，因此基本上您可以使用它来存储隐藏属性，而不必担心您还保存引用并创建内存泄漏。在这种情况下，我在 instanceSort 比较器函数中使用了一个 WeakMap 来为它作为参数接收的每个对象分配一个唯一的整数标识符，并将标识符之间的差异用作“差异” "对象之间。

缺点是您不能将它用于 IE11、Firefox 31 ESR、Safari 7.1、iOS 7、Konqueror(所有版本)和 Opera(所有版本)之前的浏览器。有关支持 WeakMap 的浏览器的详细信息，请参阅上面的链接。