命名按可预测顺序存储键的字典结构?

我投票赞成OrderedDictionary,理由如下:

除了在一个实例中,Cocoa类中从不使用“Indexed”。它总是以名词形式出现(NSIndexSet、nsindexath、objectAtIndex:,等等)。“Index”作为动词出现时只有一个实例,它位于NSPropertyDescription的“Index”属性上:isIndexed和setIndexed。NSPropertyDescription大致类似于数据库中的表列,其中“索引”指优化以加快搜索时间。因此,如果NSPropertyDescription是核心数据框架的一部分,那么“isIndexed”和“setIndexed”就相当于SQL数据库中的索引,这是有道理的。因此,将其称为“IndexedDictionary”似乎是多余的,因为创建数据库中的索引是为了加快查找时间,而不是字典 已经 具有0(1)个查找时间。然而,称之为“IndexDictionary”也将是一个误称,因为可可中的“指数”指的是位置,而不是顺序。这两者在语义上是不同的。

我理解你对“OrderedDictionary”的担忧,但可可已经树立了先例。当用户想要维护一个特定的序列时,他们会使用“ordered”:-[NSApplication orderedDocuments]、-[NSWindow orderedIndex]、-[NSApplication orderedWindows]等等。因此,John Pirie的想法基本上是正确的。

但是,您不想让插入到字典中成为用户的负担。他们会想编一本字典 一旦 然后让它保持适当的秩序。他们甚至不想按特定顺序请求对象。订单规格应在初始化期间完成。

因此,我建议使用InsertionOrderDictionary和NaturalOrderDictionary以及CustomOrderDictionary的私有子类将OrderDictionary作为一个类集群。然后,用户只需创建一个OrderedDictionary,如下所示:

OrderedDictionary * dict = [[OrderedDictionary alloc] initWithOrder:kInsertionOrder];
//or kNaturalOrder, etc

InsertionOrderDictionary . 你搞定了。

对OrderedDictionary的强烈投票。

单词“ordered”的意思正是你所宣传的东西:在遍历一个项目列表时,对这些项目的选择有一个定义的顺序。“索引”是一个实现词——它更多地说明了如何实现排序。索引,链表,树。。。用户不在乎;应该隐藏数据结构的这一方面。“Ordered”是您提供的附加功能的确切名称,无论您是如何完成的。

此外,订购的选择似乎可以由用户选择。为什么不能在数据类型上创建允许用户从字母顺序切换到插入时间顺序的方法?在默认情况下,用户将选择一个特定的排序并坚持执行它,在这种情况下,实现的效率不会低于为每个排序方法创建专用子类的效率。在一些使用较少的情况下,开发人员实际上可能希望根据应用程序上下文对同一数据使用多种不同排序中的任意一种。(我可以想到我曾经参与过的一些特定项目,我希望有这样一个数据结构可用。)

称之为OrderedDictionary,因为这正是它的本质。(坦白地说,我对“Dictionary”这个词的用法有更大的问题,因为这个词在很大程度上意味着排序,而这种方法的流行实现并没有提供排序,但这是我最讨厌的。你真的应该说“Dictionary”要知道顺序是按字母顺序排列的——因为字典就是这样的——但对于流行语言中的现有实现来说,这个论点已经太迟了。)并允许用户按自己选择的顺序访问。

自从发布这个问题以来,我开始倾向于 索引的 或 索引词典 . 虽然能够维护任意键顺序很有用,但将其限制为仅插入顺序似乎是不必要的限制。另外,我的班级已经支持 indexOfKey: 和 keyAtIndex: ,这对NSArray的 indexOfObject: objectAtIndex: . 我强烈考虑加入 insertObject:forKey:atIndex: 与NSMutableArray的 insertObject:atIndex: .

每个人都知道插入数组的中间是低效的,但这并不意味着我们不应该在极少数情况下允许它真的有用。(此外,如果需要,实现可以秘密使用双链接列表或任何其他合适的结构来跟踪排序…)

编辑: NSIndexSet 未来(恩萨雷 -objectsAtIndexes: 以及在给定索引处添加/删除对象观察者的方法。)

KeyedArray呢?

在C#中:

public class IndexedKeyDictionary<TKey, TValue> { 

  List<TKey> _keys;
  Dictionary<TKey, TValue> _dictionary;
  ...

  public GetValueAtIndex(int index) {
    return _dictionary[_keys[index]];
  }

  public Insert(TKey key, TValue val, int index) {
    _dictionary.Add(key, val);

    // do some array massaging (splice, etc.) to fit the new key
    _keys[index] = key;
  }

  public SwapKeyIndexes(TKey k1, TKey k2) {
    // swap the indexes of k1 and k2, assuming they exist in _keys
  }
}

真正酷的是索引值…所以我们有办法对值进行排序并获得新的键顺序。比如,如果这些值是图形坐标,我们可以在沿着坐标平面上下移动时读取键(bin名称)。你会称之为什么样的数据结构?索引值词典?

你所描述的声音几乎完全像C++的STL地图。据我所知,地图是一本有额外规则的字典,包括排序。STL简单地将其称为“map”,我认为这是相当恰当的。map的诀窍是,如果不使继承成为冗余的话,就不能真正给予它一个点头——即“MapDictionary”。那太多余了。“地图”有点太基本了,留下了很多误解的空间。

尽管在查看文档链接后,“CHMap”可能不是一个坏的选择。

祝你好运。

唯一的区别是 allKeys 按特定顺序返回键?如果是的话,我只想补充一句 allKeysSorted 和 allKeysOrderdByInsertion NSDictionary 应用程序编程接口。

这个插入顺序字典的目标是什么?与阵列相比,它给程序员带来了什么好处?