C++如何使用STL实现高效查找和排序-C++-PHP中文网

STL中适合高效查找的容器有std::unordered_map、std::unordered_set、std::map、std::set和排序后的std::vector。其中std::unordered_map和std::unordered_set基于哈希表，平均查找时间复杂度为O(1)，适用于对查找速度要求高且不关心顺序的场景；std::map和std::set基于红黑树，查找时间复杂度为O(log N)，适用于需要有序数据或稳定性能的场景；排序后的std::vector结合二分查找可实现O(log N)查找，适合静态或低频更新的数据集。选择时需权衡数据规模、操作频率、是否有序及自定义类型的哈希或比较支持。

c++如何使用stl实现高效查找和排序

C++标准模板库（STL）通过提供一系列经过高度优化的容器（如

std::vector

登录后复制

、

std::map

登录后复制

、

std::unordered_map

登录后复制

）和算法（如

std::sort

登录后复制

、

std::find

登录后复制

、

std::binary_search

登录后复制

），使得在C++中实现高效的查找和排序变得相对直接且强大。关键在于理解不同容器和算法的底层机制及其时间复杂度，从而根据具体应用场景做出最合适的选择。

STL 提供了一整套工具来应对各种查找和排序需求。对于排序，

std::sort

登录后复制

是序列容器（如

std::vector

登录后复制

）的首选，它通常采用内省式排序（Introsort），性能非常出色，平均时间复杂度为O(N log N)。查找方面则更为多样，从简单的线性查找

std::find

登录后复制

到针对有序序列的二分查找

std::binary_search

登录后复制

、

std::lower_bound

登录后复制

等，再到基于树结构的

std::map

登录后复制

和基于哈希表的

std::unordered_map

登录后复制

，它们各自在不同场景下提供了从O(N)到O(log N)甚至平均O(1)的查找效率。选择哪个，往往是我在设计系统时最先考虑的问题之一，因为它直接关系到程序的响应速度。

STL中哪些容器最适合高效查找操作？

在STL中，针对高效查找，我们通常会在

std::vector

登录后复制

（配合排序）、

std::map

登录后复制

、

std::set

登录后复制

、

std::unordered_map

登录后复制

和

std::unordered_set

登录后复制

之间做选择。每种容器都有其适用场景和性能特点，这就像选择不同的工具箱来处理不同的任务。

std::vector

登录后复制

本身并不直接提供高效查找，但如果数据是静态的或者不经常变动，我们可以先用

std::sort

登录后复制

对其进行一次排序，之后再利用

std::binary_search

登录后复制

、

std::lower_bound

登录后复制

或

std::upper_bound

登录后复制

进行O(log N)的查找。这种方法在数据量大且查找频繁，但插入/删除操作较少时非常有效。我个人在处理一些只读数据集时，就喜欢这种“一次排序，多次查找”的模式。

立即学习“C++免费学习笔记（深入）”；

std::map

登录后复制

和

std::set

登录后复制

是基于红黑树实现的，它们提供O(log N)的查找、插入和删除操作。它们的优点是数据始终保持有序，可以进行范围查找，并且性能非常稳定。如果你需要有序遍历，或者对查找性能有严格的对数级保证，

map

登录后复制

set

登录后复制

是很好的选择。

std::unordered_map

登录后复制

和

std::unordered_set

登录后复制

则是基于哈希表实现的。它们在平均情况下能提供O(1)的查找、插入和删除操作，理论上是查找最快的容器。但在最坏情况下（哈希冲突严重），性能可能退化到O(N)。它们不保证元素的顺序。我发现，对于那些对查找速度要求极致，且不关心元素顺序的场景，

unordered_map

登录后复制

几乎是我的首选。不过，这也要求我们对哈希函数的质量有所考量，特别是对于自定义类型作为键的情况。

如何利用

std::sort

登录后复制

和自定义比较器实现复杂数据类型的排序？

std::sort

登录后复制

是STL中最常用的排序算法之一，它接受一个迭代器范围和可选的比较函数。对于基本数据类型，

std::sort

登录后复制

默认会进行升序排序。但当我们处理自定义的复杂数据类型时，比如一个

Person

登录后复制

结构体，包含姓名、年龄等字段，就需要自定义比较器来告诉

std::sort

登录后复制

如何比较两个

Person

登录后复制

对象。

自定义比较器可以是：

一个函数对象（Functor）：定义一个重载了
```
operator()
```
登录后复制
的类。
一个Lambda表达式：C++11及更高版本中最灵活和简洁的方式。
一个普通函数：作为比较器的参数传入。

我通常倾向于使用Lambda表达式，因为它简洁且可以直接在调用

std::sort

登录后复制

的地方定义，上下文清晰。

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

struct Person {
    std::string name;
    int age;
    double height;
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30, 1.65},
        {"Bob", 25, 1.80},
        {"Charlie", 30, 1.75},
        {"David", 25, 1.70}
    };

    // 示例1: 按年龄升序排序
    // 如果年龄相同，则按姓名升序排序
    std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        if (a.age != b.age) {
            return a.age < b.age;
        }
        return a.name < b.name;
    });

    std::cout << "Sorted by age, then name:\n";
    for (const auto& p : people) {
        std::cout << p.name << ", " << p.age << ", " << p.height << "\n";
    }

    // 示例2: 按身高降序排序
    std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.height > b.height; // 注意是 > 实现降序
    });

    std::cout << "\nSorted by height (descending):\n";
    for (const auto& p : people) {
        std::cout << p.name << ", " << p.age << ", " << p.height << "\n";
    }

    return 0;
}

登录后复制

通过这种方式，我们可以轻松地根据任何复杂的逻辑来对自定义数据类型进行排序。我记得刚开始学C++的时候，自定义排序函数让我觉得有点神奇，因为它可以把我的“比较规则”直接传给算法，非常灵活。

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

在STL中进行查找时，

std::find

登录后复制

与

std::binary_search

登录后复制

有何区别，何时选用？

std::find

登录后复制

和

std::binary_search

登录后复制

是STL中两种基本的查找算法，但它们的工作原理和适用场景截然不同。理解它们的区别，能帮助我们避免一些常见的性能陷阱。

std::find

登录后复制

执行的是线性查找。它从容器的起始位置开始，逐个元素地与目标值进行比较，直到找到匹配的元素或遍历完整个容器。它的时间复杂度是O(N)，这意味着查找时间与容器中元素的数量成正比。

std::find

登录后复制

的优点是它不需要容器中的元素是排序的，适用于任何类型的序列容器。如果你只需要查找一次，且容器很小或者未排序，

std::find

登录后复制

是个不错的选择。

std::binary_search

登录后复制

执行的是二分查找。它的前提条件是容器中的元素必须已经排序。它通过不断将搜索范围减半来查找目标值，时间复杂度是O(log N)。这意味着即使容器中有数百万个元素，查找也能在非常短的时间内完成。除了

std::binary_search

登录后复制

，还有

std::lower_bound

登录后复制

和

std::upper_bound

登录后复制

，它们不仅能告诉你元素是否存在，还能返回其在有序序列中的插入位置或出现范围的迭代器。

何时选用：

选用
std::find
登录后复制
：
- 当容器未排序，且你不想或不能对其进行排序时。
- 当容器非常小，O(N)的开销可以忽略不计时。
- 当查找操作不频繁，或者只需要进行一次性查找时。
选用
std::binary_search
登录后复制
（或
lower_bound
登录后复制
/
upper_bound
登录后复制
）：
- 当容器已经排序，或者你可以接受一次性排序的成本，并且之后会进行多次查找时。
- 当容器非常大，O(log N)的性能优势会非常显著。
- 当你需要查找元素的精确位置或范围时（使用
```
lower_bound
```
  登录后复制
  /
```
upper_bound
```
  登录后复制
  ）。

我经常看到一些新手在处理一个大型数据集时，反复调用

std::find

登录后复制

，导致程序运行缓慢。其实很多时候，只要先对数据进行一次

std::sort

登录后复制

，然后切换到

std::binary_search

登录后复制

，性能就能得到质的飞跃。当然，如果数据经常变动，每次插入或删除后都需要重新排序，那么

std::map

登录后复制

或

std::unordered_map

登录后复制

可能更合适，因为它们内部维护了有序性或哈希结构。

std::unordered_map

登录后复制

在性能上真的比

std::map

登录后复制

更有优势吗？有哪些潜在的陷阱？

std::unordered_map

登录后复制

和

std::map

登录后复制

都是键值对容器，但它们的底层实现和性能特性差异巨大，因此不能简单地说哪个“更优”，而应该说哪个“更适合”特定场景。我个人在项目中，对这两种容器的选择，往往是性能调优的关键点之一。

性能优势：

std::unordered_map

登录后复制

基于哈希表实现，其平均时间复杂度在查找、插入和删除操作上都是O(1)。这意味着理论上，无论容器中存储了多少元素，这些操作的耗时都是常数级别的。相比之下，

std::map

登录后复制

基于红黑树实现，其所有操作的时间复杂度都是O(log N)。对于大数据集，O(1)的平均性能无疑具有巨大的吸引力。

潜在陷阱： 尽管

unordered_map

登录后复制

在平均性能上表现出色，但它并非没有缺点，甚至有一些“陷阱”需要注意：

最坏情况性能退化： 当哈希函数设计不当，或者遇到恶意数据导致大量哈希冲突时，
```
unordered_map
```
登录后复制
的性能可能退化到O(N)。这时，它甚至可能比
```
map
```
登录后复制
更慢。我曾经遇到过因为自定义类型哈希函数写得不好，导致
```
unordered_map
```
登录后复制
性能急剧下降的情况，排查起来还挺费劲的。
哈希函数要求： 对于自定义类型作为键，你必须提供一个有效的哈希函数（通过特化
```
std::hash
```
登录后复制
模板或提供一个自定义的哈希函数对象）。如果忘记提供，或者提供的哈希函数质量不高，就会导致编译错误或性能问题。
内存开销：
```
unordered_map
```
登录后复制
通常比
```
map
```
登录后复制
有更高的内存开销，因为它需要维护一个哈希表（通常是一个
```
std::vector
```
登录后复制
或数组），即使其中很多桶是空的。此外，每个节点通常也比
```
map
```
登录后复制
的节点更大。
无序性：
```
unordered_map
```
登录后复制
不保证元素的任何特定顺序。如果你需要按键的顺序遍历元素，或者需要进行范围查询，
```
unordered_map
```
登录后复制
就无法满足需求。而
```
map
```
登录后复制
则天然地保持了键的有序性。
哈希表重哈希（rehash）开销： 当哈希表的负载因子（load factor）超过阈值时，
```
unordered_map
```
登录后复制
会进行一次重哈希操作，这涉及到重新分配更大的内存并重新计算所有元素的哈希值和位置。这个操作的开销是O(N)，虽然不频繁，但在某些实时性要求高的场景下需要考虑。

何时选用：

选用
unordered_map
登录后复制
：当你需要最快的平均查找、插入和删除速度，且不关心元素的顺序，并且可以确保哈希函数质量较高时。
选用
map
登录后复制
：当你需要保持元素的有序性，需要进行范围查询，或者对性能的稳定性有严格要求（避免最坏情况），或者自定义类型作为键难以提供高质量哈希函数时。

例如，如果你要存储一个人的ID到其详细信息的映射，并且ID是

int

登录后复制

或

string

登录后复制

这种有良好内置哈希支持的类型，且你只关心快速通过ID查找，那么

unordered_map

登录后复制

会是很好的选择。但如果你需要按ID范围查找，或者ID是自定义的复杂对象，且你不想花精力去写一个好的哈希函数，那么

map

登录后复制

可能更稳妥。

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>

// 自定义类型作为键
struct Point {
    int x, y;
    // 必须提供相等运算符
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 为自定义类型提供哈希函数
// 方式1: 特化std::hash
namespace std {
    template <>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            // 一个简单的哈希组合，实际应用中可能需要更复杂的哈希函数
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_map<Point, std::string> umap;
    umap[{1, 2}] = "Point A";
    umap[{3, 4}] = "Point B";

    if (umap.count({1, 2})) {
        std::cout << "Found in unordered_map: " << umap[{1, 2}] << std::endl;
    }

    // std::map 也可以使用 Point 作为键，但 Point 必须定义 operator<
    std::map<Point, std::string> m;
    // Point 必须有 operator<
    // bool operator<(const Point& other) const {
    //     if (x != other.x) return x < other.x;
    //     return y < other.y;
    // }
    // 如果没有，这里会编译错误

    return 0;
}

登录后复制

这段代码展示了