| arrays are structured best suited for iterated and/or ordered data, that is best sorted to be used efficiently. recall a bag is a hash table associating a key and the number of its occurences. it is best suited towards a task that just needs to know how many of a certain type of object, in O(1) time. dictionaries provide a more generalized hash table, with an object as a key associated to an object as data. if the task provides the key, then a hash table can quickly located data associated with it. alan fay |
| since a set is a type of hash table, the element acts as the key, and the only input to a request on a set. this provides O(1) feedback if the element is in the set or not. an array however, when sorted, preforms a binary search for the element in O(log n), and unsorted, O(n) worst case. once the index for the element is found, subsequent accesses are O(1), if the array doesn't change. in a structure where elements are being added at some interval of time, the set wins for efficiency for this task. alan fay |
| an array does not need to maintain the invariant that the data in it are in a sorted order. one can call a sort on the array, but an ordered collection invokes a sort of some kind to keep its data sorted. since it's not clear what task's speed is being compared, here's just a list of a few tasks: adding, array wins; deletion, ordered collection wins (binary search versus iteration to find element); search, ordered collection wins (binary search again); iteration, the same in both. alan fay |
| OrderedCollections are Arrays that can grow as needed. The data is not sorted! Barbara Ericson |
| Ordered collections are slower than arrays when you add to them. This is because their bounds must be checked. Also, when an OrderedCollection is full and something is added to it, it must be doubled in size. OrderedCollections are about the same as Arrays when accessing an element at a known index. - Jim McPherson |