如何高效查找std::set中存储的std::shared_ptr元素？

当你需要在存储std::shared_ptr的std::set里按指向对象的值查找时，默认的find方法会因为指针地址不同而失效。这里有两种无需自行实现完整查找算法的方案：

一、自定义比较器的有序集合（高效O(logn)查找） #

std::set默认通过指针地址比较排序，我们可以自定义比较器让集合按指向对象的值来排序和比较，这样就能用原生的find方法高效查找。

示例代码：

#include <iostream>
#include <memory>
#include <set>
#include <string>

// 自定义比较器，按shared_ptr指向的字符串值比较
struct SharedPtrStrCompare {
    bool operator()(const std::shared_ptr<std::string>& lhs, const std::shared_ptr<std::string>& rhs) const {
        return *lhs < *rhs;
    }
};

int main() {
    // 使用自定义比较器的set
    std::set<std::shared_ptr<std::string>, SharedPtrStrCompare> thing;
    thing.insert(std::make_shared<std::string>("a"));
    
    // 用指向相同值的新shared_ptr查找
    auto iter = thing.find(std::make_shared<std::string>("a"));
    std::cout << (iter != thing.end()) << std::endl; // 输出1，查找成功
    return 0;
}

注意：确保所有插入的shared_ptr都不为空，否则解引用会触发未定义行为；如果存储的是自定义类型，需要确保该类型重载了<运算符，或者在比较器里实现对应的比较逻辑。

二、使用std::find_if（适合小规模集合） #

如果不想修改集合的排序规则，或者不需要有序存储，可以用std::find_if结合lambda表达式直接匹配对象值。这种方法是线性遍历，时间复杂度O(n)，适合元素数量不多的场景。

示例代码：

#include <iostream>
#include <memory>
#include <set>
#include <string>
#include <algorithm>

int main() {
    std::set<std::shared_ptr<std::string>> thing;
    thing.insert(std::make_shared<std::string>("a"));
    
    auto target = std::make_shared<std::string>("a");
    // 遍历集合，匹配对象值相等的元素
    auto iter = std::find_if(thing.begin(), thing.end(),
        [&target](const std::shared_ptr<std::string>& elem) {
            return *elem == *target;
        });
    
    std::cout << (iter != thing.end()) << std::endl; // 输出1，查找成功
    return 0;
}

内容的提问来源于stack exchange，提问作者Maddy Guthridge