博客之家-Feng

代码中频繁使用了std::vector（动态数组），这在进行查找操作时不得不依赖效率较低的for循环（时间复杂度为O(n)），尤其在处理大型文件或复杂数据模型时，程序运行速度明显变慢。实际上，随着开发进程的深入，我们不可避免地会面临程序性能优化的问题。通过优化动态数组的查找算法，可以显著提升程序的执行效率。为此，推荐两种C++标准库中的容器，它们能有效优化动态数组的查找性能。

1.std::map

在C++中，std::map 是一个关联容器，它存储了键值对（key-value pairs），其中键是唯一的。由于std::map 是基于红黑树实现的，因此它能够提供对元素的有序存储以及高效的查找、插入和删除操作。

std::map 提供了一个名为 find 的成员函数，它用于在映射中查找与给定键（key）相对应的元素。如果找到，find 函数返回一个指向该元素的迭代器（iterator），否则返回一个指向映射末尾的迭代器（end() 迭代器）。

语法

iterator find(const Key& key);

参数

key：要查找的键值。

返回值

返回一个迭代器，指向映射中与给定键相匹配的第一个元素，如果找不到匹配的元素，则返回 end() 迭代器。

示例代码

#include <iostream>
#include <map>
int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";
    int keyToFind = 2;
    auto it = myMap.find(keyToFind);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->second << std::endl;
    } else {
        std::cout << "Key not found." << std::endl;
    }
    return 0;
}

输出

Found: two

注意事项

find 函数的时间复杂度为 O(log n)。
使用 find 函数时，如果找到了键，你可以通过迭代器直接访问对应的值。
如果需要检查键是否存在，可以使用 find 函数的返回值与 end() 迭代器进行比较。

2.std::set

在C++标准库中，std::set 是一个关联容器，它存储了唯一元素的集合，并且这些元素会按照特定的排序准则（通常是升序）自动排序。std::set 通常是基于红黑树实现的，这使得它能够提供对元素的有序存储以及高效的查找、插入和删除操作。

主要特点

元素唯一：std::set 中的每个元素都是唯一的。
自动排序：元素会根据定义的比较函数自动排序。
快速查找：提供高效的查找操作，时间复杂度为 O(log n)。

查找方法

std::set 提供了几种查找元素的方法：

find 方法

功能：在集合中查找与给定值相等的元素。

返回值：如果找到元素，返回指向该元素的迭代器；如果没有找到，返回 end() 迭代器。

count 方法

功能：返回集合中与给定值相等的元素数量。由于 std::set 中元素唯一，所以返回值要么是 0（未找到），要么是 1（找到）。

返回值：返回一个整数，表示找到的元素数量。

equal_range 方法

功能：返回一个迭代器对，表示集合中与给定值相等的元素的范围。由于 std::set 中元素唯一，所以返回的范围只包含一个元素。

返回值：返回一个 std::pair，其中 first 是指向找到的元素的迭代器，second 是指向该元素之后元素的迭代器。

lower_bound 方法

功能：返回指向不小于给定值的第一个元素的迭代器。

返回值：如果找到这样的元素，返回指向该元素的迭代器；如果没有找到，返回 end() 迭代器。

upper_bound 方法

功能：返回指向大于给定值的第一个元素的迭代器。

返回值：如果找到这样的元素，返回指向该元素的迭代器；如果没有找到，返回 end() 迭代器。

示例代码

#include <iostream>
#include <set>
int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};
    int valueToFind = 3;
    auto it = mySet.find(valueToFind);
    if (it != mySet.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Value not found." << std::endl;
    }
    int count = mySet.count(valueToFind);
    std::cout << "Count: " << count << std::endl;
    auto range = mySet.equal_range(valueToFind);
    std::cout << "Equal range: [" << *(range.first) << ", " << *(range.second) << "]" << std::endl;
    auto lower = mySet.lower_bound(valueToFind);
    std::cout << "Lower bound: " << *lower << std::endl;
    auto upper = mySet.upper_bound(valueToFind);
    std::cout << "Upper bound: " << *upper << std::endl;
    return 0;
}

输出

Found: 3
Count: 1
Equal range: [3, 4]
Lower bound: 3
Upper bound: 4

最后，对于存储自定义类对象的情况，你可以选择使用 std::set 或 std::map，这取决于你的具体需求。以下是一些考虑因素：

是否需要键值对：如果你需要将每个对象与一个特定的键关联起来，那么 std::map 是更好的选择。std::map 存储键值对，其中键是唯一的。如果你只需要存储对象，而不需要与键关联，那么 std::set 可能更适合。
查找速度：std::set 和 std::map 都基于平衡二叉树实现，提供了对数时间复杂度的查找功能（O(log n)）。
排序：std::set 会根据对象的比较结果自动排序，而 std::map 会根据键的比较结果自动排序。如果你需要有序的数据集，那么 std::set 或 std::map 都是不错的选择。
唯一性：std::set 确保存储的对象是唯一的，而 std::map 确保键是唯一的。

示例：使用 std::set 存储自定义类对象

假设你有一个自定义类 Person，你可以使用 std::set 来存储这些对象：

#include <iostream>
#include <set>

class Person {
public:
    std::string name;
    int age;
    Person(const std::string& name, int age) : name(name), age(age) {}
    // 重载 < 操作符，以便 std::set 可以比较 Person 对象
    bool operator<(const Person& other) const {
        return name < other.name || (name == other.name && age < other.age);
    }
};

int main() {
    std::set<Person> people;
    // 插入对象
    people.insert(Person("Alice", 30));
    people.insert(Person("Bob", 25));
    people.insert(Person("Charlie", 35));
    // 查找对象
    auto it = people.find(Person("Bob", 25));
    if (it != people.end()) {
        std::cout << "Found: " << it->name << ", " << it->age << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    // 遍历 set 并打印所有对象
    for (const auto& person : people) {
        std::cout << person.name << ", " << person.age << std::endl;
    }
    return 0;
}

示例：使用 std::map 存储自定义类对象

如果你需要将对象与一个特定的键关联起来，可以使用 std::map：

#include <iostream>
#include <map>

class Person {
public:
    std::string name;
    int age;

    Person(const std::string& name, int age) : name(name), age(age) {}
};

int main() {
    std::map<std::string, Person> people;
    // 插入对象
    people["Alice"] = Person("Alice", 30);
    people["Bob"] = Person("Bob", 25);
    people["Charlie"] = Person("Charlie", 35);
    // 查找对象
    auto it = people.find("Bob");
    if (it != people.end()) {
        std::cout << "Found: " << it->second.name << ", " << it->second.age << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    // 遍历 map 并打印所有对象
    for (const auto& pair : people) {
        std::cout << pair.first << ": " << pair.second.name << ", " << pair.second.age << std::endl;
    }
    return 0;
}

二开效率提升技巧之动态数组查找算法优化

评论