Learning New Data Structures for iOS Developers

Mobile developers rarely encounter complex data structures in their work. As a rule, in routine tasks it is quite enough to be able to use Array, Dictionary And Set.

In my experience, even with these data structures, developers have problems. Not everyone can explain why, for example, a key in a dictionary requires Hashable protocol, but not for the value. There are also problems with assessing the complexity of operations. But that's not what we're talking about today. There are plenty of good articles about how basic data structures work.

You've probably heard of trees, graphs, linked lists Tree, Graph, Linked List, but in your daily work as a mobile developer, you are unlikely to encounter them. Today I would like to tell you about rare and underestimated data structures. And most importantly, how to let them into your routine work as a programmer.

I took the open-source library from Apple as a basis swift-collectionsThe following data structures are of greatest interest to me:

• Deque

• Heap (Priority Queue)

• OrderedSet

• OrderedDictionary

Deque (Double-ended queue)

Deque (pronounced “deck”) is a data structure that provides the ability to work with a collection of elements, to which elements can be added and removed from both the beginning and the end.

You may ask why it is needed, because it is an ordinary array Array can do the same thing. The special feature is that deletion and insertion at the beginning and end have amortized complexity О(1)while arrays require 0(n) when inserting an element at the beginning.

Amortized performance (or amortized running time) is a technique in algorithm analysis that is used to estimate the average execution time of operations in a sequence, even though some operations may be significantly slower than others.

This feature can greatly improve performance when working with large collections where you need to insert and remove elements from the beginning or end frequently.

Example of using Deque

Let's say we need a class that is responsible for canceling and resuming some operations. We have several restrictions.

• The number of operations that can be undone is finite.

• If we cancel some operations and make new ones, then the possibility of resuming disappears

Working with the data structure itself will not differ much from an array, the interface and other properties are similar.

import Collections

final class UndoRedoService<Operation> {
    
    private var operations: Deque<Operation> = []
    private var lastOperationIndex = -1
    private let capacity: Int
    
    init(capacity: Int = 100) {
        self.capacity = capacity
    }
    
    func register(_ operation: Operation) {
        // Удаляем отмененные операции из очереди операций
        if lastOperationIndex != operations.count - 1 && lastOperationIndex != -1 {
            operations.removeLast(operations.count - lastOperationIndex - 1)
        }
        // Удаляем первую операцию в случае переполнения допустимого размера очереди
        if operations.count > capacity {
            operations.removeFirst()
        }
        operations.append(operation)
        lastOperationIndex = operations.count - 1
    }
    
    func undo() -> Operation? {
        guard !operations.isEmpty else { return nil }
        let last = operations.last
        lastOperationIndex -= 1
        return last
    }
    
    func redo() -> Operation? {
        guard lastOperationIndex != operations.count - 1 else { return nil }
        lastOperationIndex += 1
        let redo = operations[lastOperationIndex]
        return redo
    }
}

In this exampleDequewill be the preferred choice. Adding a new operation to the queue, deleting the first operation if it overflows, or deleting several if there are canceled ones is more efficient than Array. How much more effective can be seen on the graph:

Heap

Heap (in Russian-language literature you can find the name heap) – a partially ordered tree with efficient insertion and deletion operations.

Elements stored in the heap must conform to the protocol Comparable.

public struct Heap<Element: Comparable>

Example of use with integers:

var heap = Heap([5,7,1,20,2,10,15])
print("heap.unordered: \(heap.unordered)") // heap.unordered: [1, 20, 15, 7, 2, 10, 5]
    
let max = heap.max
print("heap.max: \(String(describing: max))") // "heap.max: Optional(20)
    
let popedMax = heap.popMax()
print("heap.popMax: \(String(describing: popedMax))") // "heap.popMax: Optional(20)
    
let removedMax = heap.removeMax()
print("heap.removeMax(): \(String(describing: removedMax))") // "heap.removeMax(): 15
    
heap.insert(0)
    
let removedMin = heap.removeMin()
print("heap.removeMin(): \(String(describing: removedMin))") // "heap.removeMin(): 0
    
print("heap.unordered: \(heap.unordered)") // heap.unordered: [1, 7, 10, 5, 2]

Complexity of operations in Heap

Task scheduler example

Heap can be used to solve various problems, for example:

• Queue of requests to the network or database;

• Multimedia processing (audio and video);

• Processing notifications in order of importance.

Let's say we have some structure Task. This could mean any type of task, a network request, a database, any heavy-duty task.

struct Task: Comparable {
    
    enum Priority: Comparable {
        case low
        case medium
        case high
    }
    
    let id: String
    let priority: Priority
    let action: () -> Void

    static func < (lhs: Task, rhs: Task) -> Bool {
        return lhs.priority < rhs.priority
    }
    
    static func == (lhs: Task, rhs: Task) -> Bool {
        lhs.id == rhs.id && lhs.priority == rhs.priority
    }
}

• structure Task complies with protocol Comparable ;

• Comparability is set depending on priorities (low, medium, high).

final class TaskScheduler {
    private var taskQueue = Heap<Task>()

    // Добавляет новую задачу в очередь
    func scheduleTask(_ task: Task) {
        taskQueue.insert(task)
        executeNextTaskIfExist()
    }

		// Достает и исполняет самую приоритетную задачу, если есть в очереди
    private func executeNextTaskIfExist() {
        guard let task = taskQueue.popMax() else { return }
        task.action()
        // взять новую задачу если есть
    }
}

TaskScheduler controls the order of execution of tasks in accordance with Task.Priority

OrderedSet

OrderedSet – powerful and comfortable hybrid Array And Set

Collection elements must comply with the protocol Hashable. The main difference from the usual Set – now we can access elements by index, and the order will not be disturbed.

For myself, I found a convenient use for this collection in iOS when working with Diffable Data Source. Usually, to work with this API, an array is used as a data source. But a situation may arise when there are duplicates in this data source. Then either we will see duplicate elements on the screen, or, even worse, a crash in case of incorrect implementation Hashable protocol.

Example of using OrderedSet

We will use the structure as data Item

struct Item: Hashable {
    let id: String
    let title: String

    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
    }

    static func == (lhs: Item, rhs: Item) -> Bool {
        lhs.id == rhs.id
    }
}

Let's say we have a screen c UITableView And UITableViewDiffableDataSource

class DiffableViewController: UIViewController {
    var tableView: UITableView!
    var dataSource: UITableViewDiffableDataSource<Int, Item>!
    var items = [Item]()

    override func viewDidLoad() {
        super.viewDidLoad()

        tableView = UITableView(frame: view.bounds, style: .plain)
        view.addSubview(tableView)

        dataSource = UITableViewDiffableDataSource<Int, Item>(tableView: tableView) { (tableView, indexPath, item) -> UITableViewCell? in
            let cell = tableView.dequeueReusableCell(withIdentifier: "cell", for: indexPath)
            cell.textLabel?.text = item.title
            return cell
        }

        tableView.register(UITableViewCell.self, forCellReuseIdentifier: "cell")

        // 1
        let item1 = Item(id: UUID().uuidString, title: "Item 1")
        let item2 = Item(id: UUID().uuidString, title: "Item 1")
        items.append(item1)
        items.append(item2)
        // warning: Две одинаковые строки будут отображены на экране
        updateSnapshot()

        
        // 2
        let item3 = Item(id: "123456789", title: "Item 3")
        let item4 = Item(id: "123456789", title: "Item 4")
        items.append(item3)
        items.append(item4)
        // crash: Приведет к крашу, так как item3 и item4 будут иметь одинаковый хэш
        updateSnapshot()
    }

    func updateSnapshot() {
        var snapshot = NSDiffableDataSourceSnapshot<Int, Item>()
        snapshot.appendSections([0])
        snapshot.appendItems(items)
        dataSource.apply(snapshot, animatingDifferences: true)
    }

    func addItem(_ newItem: Item) {
        items.append(newItem)
        updateSnapshot()
    }

1. In the first case, we add two identical ones Itembut since UUID generates a different value, we will simply see two identical cells on the screen;

2. In the second case id will be the same, which will cause the application to crash. Diffable Data Sourceaccepts only unique objects.

Keeping track of the fact that the hashes are always different can be a problem, especially if we want to tie in to the data from the backend. In this case, OrderedSet. It will help filter out duplicates and transfer only unique values ​​to the snapshot.

var items = OrderedSet<Item>()

...

func updateSnapshot() {
	var snapshot = NSDiffableDataSourceSnapshot<Int, Item>()
    snapshot.appendSections([0])
    snapshot.appendItems(Array(items)) // конвертируем в массив
    dataSource.apply(snapshot, animatingDifferences: true)
}

OrderedDictionary

OrderedDictionary – an ordered collection of key-value pairs. OrderedDictionary has properties of both a dictionary and an array.

import OrderedCollections

@frozen struct OrderedDictionary<Key: Hashable, Value>

Let's immediately look at an example of use from a real project on iOS.

Example of using OrderedDictionary

We have a structure of a certain post, for example, like in social networks:

struct Post: Codable {
    let id: String
    var title: String
    var content: String
}

There is also APIwhich returns new and updated posts in the method fetchPosts

struct PostsResponse: Codable {
    let newPosts: [Post]
    let updatedPosts: [Post]
}

...
func fetchPosts() async throws -> PostsResponse

Manager PostManager is responsible for adding and updating posts according to the following logic:

final class PostManager {
	typealias ID = String
		
    /// Хранит посты в заданном порядке
    private var postArray: [Post] = [] 
    /// Хранит пару id и порядковый номер поста
    private var postDictionary: [ID: Int] = [:] 
    
    func addOrUpdatePosts(_ response: PostsResponse) {
        // Проверяем, что таких постов еще нет и добавляем в конец
        for post in response.newPosts where postDictionary[post.id] == nil {
		    postArray.append(post)
            postDictionary[post.id] = postArray.count - 1
        }
        
        // Находим пост по id чтобы обновить его в массиве
        for post in response.updatedPosts {
            if let index = postDictionary[post.id] {
                postArray[index] = post
            }
        }
    }
   
}

Now try refactoring this code. Here comes into play OrderedDictionary:

private var posts = OrderedDictionary<ID, InstagramPost>()
    
func addOrUpdatePosts(_ response: PostsResponse) {
	// Если пост новый, то он добавится в конец
    for post in response.newPosts {
        posts[post.id] = post
    }
        
    // Если пост существует, то он обновится 
    for post in response.updatedPosts {
        posts[post.id] = post
    }
}

Usage OrderedDictionary greatly simplifies the task, as it combines the functionality of an array and a dictionary:

• Maintains the order of elements;

• Ensures the uniqueness of keys;

• Makes it easy to add and update items.

While using a separate array and dictionary requires additional logic and increases the chance of making a mistake.

Usage OrderedDictionary makes the code cleaner and more maintainable.

Conclusion

The purpose of this article is to convey to the reader the benefits of efficient data structures and show how to use them in routine iOS developer tasks.

If I managed to interest you in this article, then as a bonus I suggest you sort out TrieThis is the data structure behind the question, “How does Google search work?” At my interview, it was at Google. That's what they asked me.

It is often said that algorithms and data structures are not needed, especially for mobile developers. In my opinion, the truth is somewhere in the middle. There is no point in trying to learn all possible tricky algorithms and techniques, this knowledge is unlikely to find application.

I feel that the ability to solve algorithmic problems and the ability to choose the right data structure help me write code more consciously, make fewer mistakes, see corner cases in advance and build logical chains before implementation.

Another lifehack that helps me not to give up if I can't solve a difficult problem on LeetCode is to treat it like a game of chess. Today you lose (couldn't solve the problem), but tomorrow you come with new knowledge and win. Sports interest gives energy for self-improvement.

P.S. To learn more about mobile development and life in London, visit my Telegram channel https://t.me/ios_mobile_developer

Additional materials