Поскольку вы случайно не можете получить доступ к элементу NSMutableSet, означает ли это, что он реализован как связанный список?- это NSMutableSet, реализованный как связанный список?
I.e. будет ли она иметь более быструю вставку/удаление, чем NSMutableArray?
Исходный код доступен, поэтому вы можете посмотреть: CFSet.c. (Это аналог Core Foundation NSSet, но они в основном одинаковы.) Это хэш-таблица.
Но вы также должны иметь в виду, что NSArray, по сути, не реализован как массив. Вы можете увидеть реализацию здесь: CFArray.c. Может быть, this blog article проще понять, хотя он немного устарел (~ 5 лет.)
Наборы обычно реализуются со сбалансированными двоичными деревьями поиска (например, красно-черные деревья, деревья avl).
Hashtables дает вам O (1) для вставки, удаления и поиска. Деревьям требуется по крайней мере O (log (N)) для любого из них. См. Мой ответ. – back2dos
@ back2dos: хеши используются, только если вам не нужен заказ. Из-за этого ограничения есть HashMap и TreeMap в java, а также map и unordered_map в C++. В java также есть TreeSet и HashSet. – swegi
Согласовано, хотя по определению наборы «не имеют особого порядка» http://en.wikipedia.org/wiki/Set_(computer_science) – back2dos
Нет. Время поиска будет быстрее, потому что оно будет использовать хеши.
Я не являюсь объектом Objective-C progammer, но обычно наборы реализуются через хэш-таблицы, которые (если они будут выполнены правильно) будут давать O (1) для вставки, удаления и поиска.
Технически хеши обычно дают вам O (M), где M - размер ключа, но для набора вы просто будете использовать идентификатор ключевого объекта, который является постоянным, поэтому вы возвращаетесь к O (1).
Этот вопрос следует ... http://stackoverflow.com/questions/4422141/objective-c-what-structure-should-i -use-to-store-these-objects – Robert