Ordered dictionary in swift 2 Loosely basing myself on this blog post, I implemented an ordered dictionary. In essence, it's a wrapper struct for a list of tuples with some initialisers and some functions (map, filter, toArray, ...) added to it.

struct OrderedDictionary&lt;KeyType: Hashable, ValueType&gt;: SequenceType
{
    typealias KeyValueType = (key:KeyType, value:ValueType)

    private var tuples: [KeyValueType] = []

    init() {}

    init(_ tupleArgs: KeyValueType...)
    {
        self.init(tupleArgs)
    }

    init(_ tupleArgs: [KeyValueType])
    {
        tuples = tupleArgs
    }

    subscript(key:KeyType) -&gt; ValueType?
    {
        get
        {
            return tuples.filter({ $0.key == key })[0].value
        }

        set(newValue)
        {
            if let val = newValue
            {
                if tuples.contains({ $0.key == key })
                {
                    tuples = tuples.map({ $0.key == key ? ($0.key, val) : $0 })
                }
                else
                {
                    tuples.append((key, val))
                }
            }
            else
            {
                tuples = tuples.filter({ $0.key != key })
            }
        }
    }

    func generate() -&gt; AnyGenerator&lt;KeyValueType&gt;
    {
        var nextIndex = 0
        return anyGenerator({
            if nextIndex &gt;= self.tuples.count
            {
                return nil
            }
            else
            {
                return self.tuples[nextIndex++]
            }
        })
    }

    mutating func insert(tuple: KeyValueType, atIndex index: Int)
    {
        tuples = tuples.filter({ $0.key != tuple.key })
        tuples.insert(tuple, atIndex: index)
    }

    func map&lt;NewKeyType:Hashable, NewValueType&gt;(transform: (KeyValueType) -&gt; (key:NewKeyType, value:NewValueType)) -&gt; OrderedDictionary&lt;NewKeyType, NewValueType&gt;
    {
        return OrderedDictionary&lt;NewKeyType, NewValueType&gt;(tuples.map(transform))
    }

    func filter(includeElement: (KeyValueType) -&gt; Bool) -&gt; OrderedDictionary&lt;KeyType, ValueType&gt;
    {
        return OrderedDictionary(tuples.filter(includeElement))
    }

    func sort(isOrderedBefore: (KeyValueType, KeyValueType) -&gt; Bool) -&gt; OrderedDictionary&lt;KeyType, ValueType&gt;
    {
        return OrderedDictionary(tuples.sort(isOrderedBefore))
    }

    func reverse() -&gt; OrderedDictionary&lt;KeyType, ValueType&gt;
    {
        return OrderedDictionary(tuples.reverse())
    }

    func toArray&lt;T&gt;(transform:((KeyValueType) -&gt; T)) -&gt; [T]
    {
        return tuples.map(transform)
    }

    func toArray() -&gt; [KeyValueType]
    {
        return tuples
    }

    func toDict() -&gt; [KeyType:ValueType]
    {
        var dict: [KeyType:ValueType] = [:]
        for tuple in tuples
        {
            dict[tuple.key] = tuple.value
        }
        return dict
    }
}


Does this look okay? Is it Swift-y enough and are there no major performance issues? I'm a bit worried about the filter, map, reverse and sort functions, but I'm not sure why. I'm also not confident about my use of map in the subscript setter.
Your code looks generally good (with two real problems explained below).

Instead of an empty default array

private var tuples: [KeyValueType] = []


which is overwritten in two of the three init methods, I would initialize the
array explicitly:

private var tuples: [KeyValueType]

init() {
    tuples = []
}


but that is perhaps a matter of taste. 

The problem with the other two init methods is that they don't check
for duplicate keys, e.g. if you call

let od = OrderedDictionary(("foo", 1), ("bar", 2), ("foo", 3))


You either have to add an explicit check (and throw an error or fail
if duplicate keys are given), or add the key/value pairs sequentially
so that duplicate keys are silently overwritten with the new value:

init(_ tupleArgs: [KeyValueType]) {
    self.init()
    for (key, value) in tupleArgs {
        self[key] = value
    }
}




There is a problem in your subscript getter method:

return tuples.filter({ $0.key == key })[0].value 


will crash if there is no key/value tuple for the given key, instead of returning
nil, because accessing [0] requires that there is at least one element.
This can be fixed as

return tuples.filter({ $0.key == key }).first?.value


because first returns an optional. But this is not very effective. The
filter method always traverses the entire array, but only the first (and only)
matching tuple is needed. This can be achieved with indexOf:

get {
    if let index = tuples.indexOf({ $0.key == key }) {
        return tuples[index].value
    } else {
        return nil
    }
}


Similarly, in the subscript setter method, it is not effective to call
contains first and then map the entire tuple array to a new array.
I would implement that as

set(newValue) {
    if let index = tuples.indexOf({ $0.key == key }) {
        if let val = newValue {
            // Update existing value
            tuples[index].value = val
        } else {
            // Remove existing value
            tuples.removeAtIndex(index)
        }
    } else if let val = newValue {
        // Add new value
        tuples.append((key, val))
    }
}




The generate method can be simplified considerably, since you are only
forwarding the enumeration to the tuples array:

func generate() -&gt; AnyGenerator&lt;KeyValueType&gt; {
    return anyGenerator(tuples.generate())
}




The 

func toArray&lt;T&gt;(transform:((KeyValueType) -&gt; T)) -&gt; [T]


is not really needed, you'll get the same result already with your
map() and toArray() method.



You should make your type conform to CustomStringConvertible so that
printing an ordered dictionary gives a nice looking result. A simple
implementation would be

extension OrderedDictionary : CustomStringConvertible {
    var description: String {
        return "[ "
            + tuples.map({ (key, value) in "\(key) : \(value)"}).joinWithSeparator(", ")
            + "]"
    }
}




Creating a new (ordered) dictionary by mapping both keys and values
can lead to unexpected results if two keys are mapped to the same
new key. E.g. (with the fixed init method from above):

let od1 = OrderedDictionary(("foo", 1), ("bar", 2), ("FOO", 3))
print(od1) // [ foo : 1, bar : 2, FOO : 3]

let od2 = od1.map { (key, value) in (key.uppercaseString, value) }
print(od2) // [ FOO : 3, BAR : 2]


You have to decide if that is wanted. Alternatively, define a 
map() method which only maps the values but preserves the keys.



If you plan to add the code to a framework then you have to annotate the struct
itself and all its public methods as public.



Some remarks concerning the performance: Each key lookup is done by a linear
traversal of the tuples array. For large dictionaries this can become a problem.

The project from the referenced blog post solves this by maintaining both
a dictionary (for the key/value pairs) and an array (for the ordered keys).
 The advantage is that a 
lookup is fast. But adding a new key or removing a key still requires a 
linear traversal of the keys array. Whether this is acceptable or not
depends on how often keys are added/removed compared to key/value lookups.

One could store the key/value pairs in a tree structure to improve the
performance (e.g. AVL tree or a red-black tree). Of course that increases
the complexity of the code.