Data Structure

July 19, 2023

map & unordered_map (aka dictionary)

std::map 和数组（array）是两种不同的数据结构，它们在用途和特性上有一些重要的区别。

std::map 有序容器，对于有序的键值对集合，可以使用 Dictionary 类型。这是 Swift 标准库提供的主要字典类型，它基于哈希表实现，具有快速的键值查找性能。

std::unordered_map 无序容器，对于无序的键值对集合，可以使用 Set 类型，其中的元素以无特定顺序存储。它通过将键映射到哈希值来存储和查找键值对，因此在大多数情况下，它提供了更快的查找性能。每个键在 std::unordered_map 中也是唯一的。

数组是一种线性数据结构，它将元素按照顺序存储在连续的内存空间中。数组的访问速度很快，可以通过索引直接访问元素。

std::map 是一种关联容器，它使用红黑树（一种自平衡二叉搜索树）实现。std::map 中的元素按照键的顺序进行排序并存储，而不是按照插入顺序。这使得在 std::map 中查找元素的速度较快。

数组中的元素可以重复，你可以在任意位置插入、修改或删除元素。

std::map 中的键是唯一的，每个键都与一个值相关联。当插入重复键时，旧的键值对会被替换。

数组对于随机访问非常高效，因为可以通过索引直接访问元素，时间复杂度为 O(1)。

std::map 支持插入、删除和查找操作，时间复杂度取决于树的高度，平均情况下为 O(log n)。

数组在创建时需要分配连续的内存空间，并且大小固定。如果需要动态添加或删除元素，可能需要重新分配更大的内存空间。

std::map 动态地分配和释放内存，可以根据需要自动调整存储空间。

综上所述，数组适用于需要快速随机访问元素的场景，而 std::map 适用于需要高效地根据键进行查找和排序的场景，并且元素的唯一性是关键。根据具体的需求和数据访问模式，选择适合的数据结构是很重要的。

關於Swift Dictionary三兩事

對比Array，Dictionary 是另一個很常見的資料結構之一，有的程式稱它 Object 或 Map，透過 key 去存取資料。在搜尋的時間複雜度，Array 是Big O(n)，因為需要逐一去找，Ditionary 是 BigO(1)，因為透過 key 就能直接取出。