C++ 之map，set，为什么不用数组代替呢？

举例电话本示例
当使用数值数组和 std::map 来实现电话簿模型时，我们可以演示它们的差异。首先，我们将使用数值数组，然后使用 std::map 来实现电话簿。

使用数值数组的电话簿模型：

#include 
#include 
#include 

struct Contact {
    std::string name;
    std::string phoneNumber;
};

int main() {
    std::vector<Contact> phoneBook;
    
    // 添加联系人
    phoneBook.push_back({"Alice", "123-456-7890"});
    phoneBook.push_back({"Bob", "987-654-3210"});
    
    // 查找联系人
    std::string searchName = "Alice";
    for (const Contact& contact : phoneBook) {
        if (contact.name == searchName) {
            std::cout << "Name: " << contact.name << ", Phone: " << contact.phoneNumber << std::endl;
            break;
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

使用 std::map 的电话簿模型：

#include 
#include 
#include 

int main() {
    std::map<std::string, std::string> phoneBook;
    
    // 添加联系人
    phoneBook["Alice"] = "123-456-7890";
    phoneBook["Bob"] = "987-654-3210";
    
    // 查找联系人
    std::string searchName = "Alice";
    auto it = phoneBook.find(searchName);
    if (it != phoneBook.end()) {
        std::cout << "Name: " << it->first << ", Phone: " << it->second << std::endl;
    } else {
        std::cout << "Contact not found." << std::endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这两个示例都实现了一个电话簿，其中存储了联系人的姓名和电话号码。使用数值数组的示例需要手动遍历数组来查找联系人，而使用 std::map 的示例允许你根据姓名快速查找联系人，因为 std::map 内部使用红黑树实现了高效的查找操作。当电话簿中的联系人数量较多时，std::map 更具有性能优势。

数组是一种简单且有效的数据结构，适用于有限数量的元素的情况。然而，使用数组和使用关联容器（如 std::map）之间存在一些区别，取决于你的需求和应用场景。

下面是一些讨论为什么可能不使用数组的情况：

1. 动态大小：使用数组时，你需要事先知道电话簿中的最大容量。如果电话簿需要动态添加或删除联系人，你就需要实现自己的扩展和缩小数组的逻辑，这可能会变得复杂。

2. 键-值对的快速查找：如果你要根据联系人的姓名快速查找他们的电话号码，使用数组需要进行线性搜索（遍历整个数组），这可能不如红黑树（std::map 的底层数据结构）的 O(log n) 查找效率高。

3. 删除元素的复杂性：如果你从数组中删除一个联系人，需要移动后续元素以填补空缺，这可能会导致性能下降。

4. 内存使用：数组通常需要分配一块连续的内存空间，如果你的电话簿非常大，可能会面临内存分配和管理方面的问题。

当电话簿的大小相对较小且不需要频繁的添加和删除联系人时，使用数组是合理的选择。然而，如果你需要高效的查找、插入和删除操作，以及灵活的动态大小管理，那么关联容器（如 std::map）通常更合适。

在实际应用中，你可以根据具体的需求和性能考虑，选择最合适的数据结构。不同的数据结构在不同的情况下有各自的优劣势。