0

我有一个由整数 ID 定义的 JS 对象列表。

objects = [{
    id: 0,
    type: 'null'
}, {
    id: 1,
    type: 'foo'
}, {
    id: 2,
    type: 'bar'
}];

我实现了一个从列表中删除元素的功能：

removeObject = function(o){
    objects.splice(objects.indexOf(o), 1);
}

我的问题是我需要创建一个函数来在我的列表中添加一个新项目，其 id 尚未使用（例如列表中不存在的较低正整数）。

我试图做类似的事情，但是当我删除对象 0 时它不起作用（例如）。

addObject = function(type){
    objects.push({
        id: objects.length,
        type: type
    });
};

我怎样才能做到这一点 ？

编辑 1

根据您的回答，我认为在性能方面的最佳解决方案是只使用一个 topId，当我在列表中添加一个新对象时它总是递增。

但这并不能满足我的要求。实际上我认为@X-Pippes 的反应可能很好。

我应该这样做吗：

objects = [{
    id: 0,
    type: 'null'
}, {
    id: 1,
    type: 'foo'
}, {
    id: 2,
    type: 'bar'
}];

// Init available ids list with the default value
availableIds = [objects.length];

removeObject = function(o){
    // Remove the object from the list
    objects.splice(objects.indexOf(o), 1);
    // Add its id to the available ids list
    availableIds.push(o.id);
}

addObject = function(type){
    // Get lower id available
    var newId = Math.min.apply(Math,availableIds);
    // Push the new object with the id retrieved
    objects.push({
        id: newId,
        type: type
    });
    // Remove used id from the available ids list
    availableIds.splice(availableIds.indexOf(newId), 1);
    // Add a default id if available list is empty
    if(availableIds.length < 1) availableIds.push(objects.length);
};
4

5 回答 5

1

如果您删除例如 0 并且下一个 addObject 是 0 您必须执行以下操作：

  • 保留一个列表[初始为空]，删除每个 ID。当您需要添加一个新的时，选择较短的，从列表中添加和删除。
  • 还要保留一个添加了最大 ID 的 var。如果上一个列表为空，则将 +1 添加到 var 和具有该 id 的 addObject
于 2013-10-23T17:01:05.670 回答
1

使用正确的结构。JavaScriptobject将完成这项工作。它保证您只能获得一项作为密钥，您可以在 O(1)ish 中通过密钥查找和删除。尝试以效率较低的方式重新实现它是没有意义的，这将是 O(n) 查找。

var structure = {
    objects : {},
    topId : 0
}

structure.add = function(item) {
    var id = this.topId ++;

    structure.objects[id] = item;
}

structure.add("thing")
structure.add("other thing")
structure.add("another thing")

structure.objects
>>> Object {0: "thing", 1: "other thing", 2: "another thing"}

structure.objects[1]
>> "other thing"

然后是正常的索引操作来获取/设置/删除。

如果您使用该函数，那么您的数据结构上有一个不变量（保证），您不会两次使用相同的 ID。

于 2013-10-23T16:59:25.683 回答
0

您需要一个函数来查找第一个空闲号码：

addObject = function(type){
    objects.push({
        id: firstOpenIndex(),
        type: type
    });
};

firstOpenIndex = function() {
    for(var idx = 0; true; i++) {
       var found = false;
       for(var o in objects) {
          if (objects[o].id == idx) {
             found = true;
             break;
          }
       }
       if (!found) return idx;
    }
}
于 2013-10-23T17:03:32.997 回答
0

您可以并且可能应该只使用一个数组，例如：

objects.type=['null','foo','bar'];

添加对象请参阅： 如何将某些内容附加到数组？

找到一个值：var index = objects.type.indexOf('foo');

找到第一个空字段var index = objects.type.indexOf('');，您可以使用它来查找要添加的元素（如果索引为 -1，则使用 objects.type.length）如果您通过将元素设置为“”来“删除”一个元素，或者......除非您有特定的原因为了保持“ID”静态（在本例中为数组索引），删除元素并仅将新元素附加到末尾

要删除元素，请参阅： 如何从 JavaScript 中的数组中删除特定元素？ 这将允许您推送/附加下一个数据。

如果您需要一个带有空字段的新对象数组来填充，因为您需要跟踪新数据：

object.newField=new Array(objects.type.length);

如果您的对象包含多个数组，您可能想要创建用于插入/添加和删除/删除的函数，因此您不要对 1 进行操作，而不是对另一个进行操作。

一切都已经内置（阅读可能已经非常快了），您不需要为您非常酷的对象类型重新发明构造函数。

于 2013-10-23T17:45:39.940 回答
0

在 Javascript MaxInt 中是 9007199254740992。为什么不继续递增呢？

于 2013-10-23T17:10:30.590 回答