10

注意：虽然我的特定上下文是 Objective-C，但我的问题实际上超越了编程语言的选择。此外，我将其标记为“主观”，因为否则肯定有人会抱怨，但我个人认为这几乎完全是客观的。另外，我知道这个相关的 SO question，但由于这是一个更大的问题，我认为最好将其作为一个单独的问题。请不要在没有完全阅读和理解的情况下批评这个问题。谢谢！

我们大多数人都熟悉存储键值关联的字典抽象数据类型，根据我们选择的语言，我们是否将其称为映射、字典、关联数组、哈希等。字典的简单定义可以概括为三个属性：

  1. 通过键访问值（而不是通过索引，如数组）。
  2. 每个键都与一个值相关联。
  3. 每个键必须是唯一的。

任何其他属性都可以说是针对特定目的的便利或专业化。例如，某些语言（尤其是 PHP 和 Python 等脚本语言）模糊了字典和数组之间的界限，并且确实为字典提供了排序。尽管这很有用，但这样的添加并不是字典的基本特征。在纯粹意义上，字典的实际实现细节是无关紧要的。

对于我的问题，最重要的观察是未定义枚举键的顺序- 字典可以以它认为最方便的任何顺序提供键，并且由客户根据需要组织它们。

我创建了强制特定键排序的自定义字典，包括自然排序顺序（基于对象比较）和插入顺序。很明显，将前者命名为SortedDictionary上的某个变体（我实际上已经实现了），但后者的问题更大。我见过LinkedHashMap和LinkedMap (Java)、OrderedDictionary (.NET)、OrderedDictionary (Flash)、OrderedDict (Python) 和OrderedDictionary (Objective-C)。其中一些更成熟，一些更概念验证。

LinkedHashMap是根据 Java 集合传统中的实现来命名的——“linked”是因为它使用双向链表来跟踪插入顺序，而“hash”是因为它是 HashMap 的子类。除了用户不需要担心这一点之外，类名甚至没有真正表明它的作用。使用有序似乎是现有代码之间的共识，但关于这个主题的网络搜索也揭示了“有序”和“排序”之间的可以理解的混淆，我也有同感。.NET 实现甚至对明显的误称有评论，并建议它应该改为“IndexedDictionary”，因为您可以在排序的特定点检索和插入对象。

我正在设计一个框架和 API，我想尽可能智能地命名这个类。从我的角度来看，索引可能会起作用（取决于人们如何解释它，并基于字典的广告功能），排序不精确并且有太多混淆的可能性，并且链接“是正确的”（向 Monty Python 道歉）。;-)

作为用户，什么名称对您来说最有意义？是否有一个特定的名称可以准确地说明该类的功能？（如果合适的话，我不反对使用稍长一些的名称，例如 InsertionOrderDictionary。）

编辑：另一个很大的可能性（在我下面的回答中讨论）是IndexedDictionary。我不太喜欢“插入顺序”，因为如果您允许用户在特定索引处插入键、重新排序键等，这没有任何意义。

4

9 回答 9

6

我投票 OrderedDictionary，原因如下：

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

我理解您对“OrderedDictionary”的担忧，但 Cocoa 已经开创了先例。当用户想要维护特定的序列时，他们使用“有序”：-[NSApplication orderedDocuments]、-[NSWindow orderedIndex]、-[NSApplication orderedWindows] 等。所以，John Pirie 的想法大多是正确的。

但是，您不想让插入字典成为用户的负担。他们会希望创建一次字典，然后让它保持适当的顺序。他们甚至不想按特定顺序请求对象。订单规范应在初始化期间完成。

因此，我建议将 OrderedDictionary 设为类集群，并使用 InsertionOrderDictionary 和 NaturalOrderDictionary 和 CustomOrderDictionary 的私有子类。然后，用户只需像这样创建一个 OrderedDictionary：

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

对于 CustomOrderDictionary，您可以让他们给您一个比较选择器，甚至（如果他们运行的是 10.6）一个块。我认为这将为未来的扩展提供最大的灵活性，同时仍保持适当的名称。

于 2009-06-30T17:55:54.273 回答
4

我投票赞成InsertionOrderDictionary。你搞定了。

于 2009-06-20T19:15:10.083 回答
3

强烈投票给 OrderedDictionary。

“有序”一词的含义正是您所宣传的内容：在遍历项目列表时，选择这些项目有一个定义的顺序。“索引”是一个实现词——它更多地谈论如何实现排序。索引、链表、树……用户无所谓；数据结构的这一方面应该被隐藏。“有序”是您提供的附加功能的确切词，无论您如何完成它。

此外，似乎订购的选择可以由用户选择。为什么你不能在你的数据类型上创建允许用户从字母顺序切换到插入时间顺序的方法？在默认情况下，用户会选择一个特定的排序并坚持使用它，在这种情况下，实现的效率不会低于为每个排序方法创建专门的子类。在一些不常用的情况下，开发人员实际上可能希望对相同的数据使用多种不同的排序方式，具体取决于应用程序上下文。（我可以想到我从事过的特定项目，我希望有这样的数据结构可用。）

称它为 OrderedDictionary，因为这正是它的本质。（坦率地说，我对“字典”这个词的使用有更多的问题，因为这个词在很大程度上暗示了排序，而流行的实现不提供它，但这是我最讨厌的。你真的应该能够说“字典”并知道排序是按字母顺序排列的——因为这就是字典的本质——但这个论点对于流行语言的现有实现来说为时已晚。）并允许用户以他选择的顺序访问。

于 2009-06-27T14:47:08.837 回答
2

自从发布这个问题以来，我开始倾向于IndexedDictionary或IndexableDictionary之类的东西。虽然能够保持任意键排序很有用，但仅将其限制为插入排序似乎是不必要的限制。另外，我的班级已经支持indexOfKey:and keyAtIndex:，它们（有目的地）类似于 NSArray 的indexOfObject:and objectAtIndex:。我正在强烈考虑添加insertObject:forKey:atIndex:与 NSMutableArray 匹配的insertObject:atIndex:.

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

最大的问题：“索引”或“可索引”是否像“有序”一样模糊或可能令人困惑？人们会想到数据库索引，还是书籍索引等？如果他们假设它是用数组实现的，那会是有害的吗？或者这会简化用户对功能的理解吗？

编辑：考虑到我正在考虑在将来添加与NSIndexSet一起使用的方法，这个名字更有意义。（NSArray 具有-objectsAtIndexes:为给定索引处的对象添加/删除观察者的方法。）

于 2009-06-20T19:59:41.693 回答
1

KeyedArray 呢？

于 2009-06-22T10:15:34.520 回答
0

正如您在上一段中所说，我认为 InsertionOrder(ed)Dict(ionary) 非常明确；除了密钥将按照插入的顺序返回之外，我看不出如何以任何方式解释它。

于 2009-06-20T19:16:30.407 回答
0

乍一看，我同意第一个回复——InsertionOrderDictionary，尽管乍一看“InsertionOrder”的含义有点模棱两可。

您所描述的内容对我来说几乎与 C++ STL 映射完全一样。据我了解，地图是具有附加规则的字典，包括排序。STL 简单地称它为“地图”，我认为这很贴切。map 的诀窍在于，如果不使其冗余，就不能真正对继承表示认可——即“MapDictionary”。这太多余了。“地图”有点太基本了，留下了很大的误解空间。

尽管在查看您的文档链接后，“CHMap”可能不是一个糟糕的选择。

也许是“CHMappedDictionary”？=)

祝你好运。

编辑：感谢您的澄清，您每天都会学到新东西。=)

于 2009-06-21T05:40:03.713 回答
0

通过将索引顺序与插入顺序分离，这不是简单地归结为将数组和字典保存在单个对象中吗？我想我对这类对象的投票是 IndexedKeyDictionary

在 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 名称）。你会怎么称呼这种数据结构？索引值字典？

于 2009-06-22T07:26:13.783 回答
-1

唯一的区别allKeys是以特定顺序返回键吗？如果是这样，我会简单地将allKeysSorted和allKeysOrderdByInsertion方法添加到标准NSDictionaryAPI。

这个插入顺序字典的目标是什么？与数组相比，它给程序员带来了什么好处？

于 2009-06-20T19:17:19.377 回答