Назовите структуру словаря, в которой ключи хранятся в предсказуемом порядке?

Я голосую за OrderedDictionary по следующим причинам:

«Индексированный» никогда не используется в классах Какао, за исключением одного экземпляра. Он всегда появляется как существительное (NSIndexSet, NSIndexPath, objectAtIndex: и т. Д.). Есть только один случай, когда "Index" появляется как глагол, который находится в свойстве "indexed" NSPropertyDescription: isIndexed и setIndexed. NSPropertyDescription примерно аналогичен столбцу таблицы в базе данных, где «индексирование» означает оптимизацию для ускорения поиска. Следовательно, имеет смысл, если NSPropertyDescription является частью структуры Core Data, что «isIndexed» и «setIndexed» будут эквивалентны индексу в базе данных SQL. Поэтому называть его «IndexedDictionary» было бы излишним, поскольку индексы в базах данных создаются для ускорения времени поиска, но словарь уже имеет время поиска O (1). Однако называть его «IndexDictionary» также было бы неправильно, поскольку «индекс» в Какао относится к позиции, а не к порядку. Эти два семантически различны.

Я понимаю вашу озабоченность по поводу "OrderedDictionary", но прецедент уже создан в Какао. Когда пользователи хотят поддерживать определенную последовательность, они используют «упорядоченные»: - [NSApplication orderDocuments], - [NSWindow OrderedIndex], - [NSApplicationhibitedWindows] и т. Д. Итак, Джон Пири в основном прав.

Однако вы не хотите, чтобы вставка в словарь была обузой для ваших пользователей. Они захотят создать словарь один раз, а затем поддерживать в нем соответствующий порядок. Они даже не захотят запрашивать объекты в определенном порядке. Спецификация заказа должна быть сделана во время инициализации.

Поэтому я рекомендую сделать OrderedDictonary кластером классов с частными подклассами InsertionOrderDictionary, NaturalOrderDictionary и CustomOrderDictionary. Затем пользователь просто создает OrderedDictionary следующим образом:

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

Для CustomOrderDictionary вы можете попросить их предоставить вам селектор сравнения или даже (если они работают с 10.6) блок. Я думаю, что это обеспечит максимальную гибкость для будущего расширения, сохранив при этом подходящее имя.

Голосую за InsertionOrderDictionary. Ты сделал это.

Решительное голосование за OrderedDictionary.

Слово «заказанный» означает именно то, что вы рекламируете: при итерации по списку элементов существует определенный порядок их выбора. «Индексированный» - это слово реализации - оно больше говорит о том, как достигается упорядочение. Индекс, связанный список, дерево ... пользователю все равно; этот аспект структуры данных должен быть скрыт. «Заказанный» - это точное слово для дополнительной функции, которую вы предлагаете, независимо от того, как вы это делаете.

Кроме того, похоже, что выбор порядка может быть на усмотрение пользователя. Есть ли причина, по которой вы не могли создать для своего типа данных методы, которые позволяют пользователю переключаться, скажем, с алфавитного порядка на порядок вставки? В случае по умолчанию пользователь выберет конкретный порядок и придерживается его, и в этом случае реализация будет не менее эффективной, чем если бы вы создали специализированные подклассы для каждого метода упорядочивания. А в некоторых менее используемых случаях разработчик может фактически пожелать использовать любой из множества различных порядков для одних и тех же данных, в зависимости от контекста приложения. (Я могу вспомнить конкретные проекты, над которыми я работал, где мне хотелось бы иметь такую ​​структуру данных.)

Назовите это OrderedDictionary, потому что это именно то, что вам нужно. (Честно говоря, у меня больше проблем с использованием слова «Словарь», потому что это слово в значительной степени подразумевает упорядочение, в то время как популярные реализации такого рода не обеспечивают его, но это моя любимая мозоль. Вы действительно должны просто иметь возможность скажите «Словарь» и знайте, что упорядочение происходит в алфавитном порядке - потому что это то, что такое словарь - но этот аргумент слишком поздно для существующих реализаций на популярных языках.) И позвольте пользователю получить доступ в том порядке, в котором он выбирает.

С момента публикации этого вопроса я начинаю склоняться к чему-то вроде IndexedDictionary или IndexableDictionary. Хотя полезно иметь возможность поддерживать произвольный порядок ключей, ограничение его только порядком вставки кажется ненужным ограничением. Кроме того, мой класс уже поддерживает indexOfKey: и keyAtIndex:, которые (намеренно) аналогичны indexOfObject: и objectAtIndex: NSArray. Я настоятельно подумываю добавить insertObject:forKey:atIndex:, который соответствует с insertObject:atIndex: NSMutableArray.

Всем известно, что вставка в середину массива неэффективна, но это не значит, что нам нельзя позволять делать это в тех редких случаях, когда это действительно полезно. (Кроме того, реализация могла бы тайно использовать двусвязный список или любую другую подходящую структуру для отслеживания порядка, если это необходимо ...)

Большой вопрос: является ли «индексируемый» или «индексируемый» таким же расплывчатым или потенциально запутанным, как «упорядоченный»? Подумают ли люди об указателях баз данных, указателях книг и т. Д.? Будет ли вредно, если они предположат, что это реализовано с помощью массива, или это может упростить понимание пользователем функциональности?

Изменить: это имя имеет еще больше смысла, учитывая тот факт, что я рассматриваю возможность добавления методов, которые работают с NSIndexSet в будущем. (NSArray имеет _ 7_, а также методы добавления / удаления наблюдателей для объектов по заданным индексам.)

А как насчет KeyedArray?

Как вы сказали в последнем абзаце, я думаю, что InsertionOrder (ed) Dict (ionary) довольно однозначен; Я не понимаю, как это можно интерпретировать иначе, как то, что ключи будут возвращены в том порядке, в котором они были вставлены.

Разве отсоединение индексированного порядка от порядка вставки не сводится просто к хранению массива и словаря в одном объекте? Думаю, мой голос за этот тип объекта - IndexedKeyDictionary

In 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
  }
}

Что было бы действительно круто, так это индексированные значения ... так что у нас есть способ отсортировать значения и получить новый порядок ключей. Например, если бы значения были координатами графика, и мы могли бы читать ключи (имена бункеров), когда мы перемещаемся вверх / вниз по координатной плоскости. Как бы вы назвали эту структуру данных? IndexedValueDictionary?

На первый взгляд, я получил первый ответ - InsertionOrderDictionary, хотя это немного неоднозначно относительно того, что на первый взгляд означает InsertionOrder.

То, что вы описываете, звучит для меня почти так же, как карта C ++ STL. Насколько я понимаю, карта - это словарь, в котором есть дополнительные правила, включая порядок. STL просто называет это «картой», что, на мой взгляд, вполне уместно. Уловка с картой заключается в том, что вы не можете отдать должное наследованию, не сделав его избыточным, то есть "MapDictionary". Это слишком избыточно. «Карта» слишком проста и оставляет много места для неправильного толкования.

Хотя "CHMap" может быть неплохим выбором после просмотра ссылки на вашу документацию.

Может, "CHMappedDictionary"? знак равно

Удачи.

Изменить: Спасибо за разъяснения, каждый день вы узнаете что-то новое. знак равно

Единственная разница в том, что allKeys возвращает ключи в определенном порядке? Если так, я бы просто добавил методы allKeysSorted и allKeysOrderdByInsertion в стандартный NSDictionary API.

Какова цель этого словаря порядка размещения? Какие преимущества он дает программисту по сравнению с массивом?