在 C++ std::set 中如何利用不同类型的值进行搜索？

在 C++ 集合中如何利用不同类型的值进行搜索

一、背景
二、初衷
三、is_transparent
四、总结

一、背景

C++14 引入了一项引人注目的功能，为关联容器弥补了某些案例中长久以来的不足之处：即允许使用在语义上被视为键，但在技术上并非真正键的值对关联容器进行搜索。这意味着可以在关联容器中使用与存储元素不同类型的值进行查找。例如，可以使用员工的 ID 在一组包含 Employee 对象的集合中进行搜索，即使该 ID 并不构成 Employee 对象的组成部分。

在这里插入图片描述

二、初衷

这一功能在set的上下文中尤为重要。一些集合存储的对象包含其自身的键，换句话说，这些对象有一个可以视作键的子成员，例如 ID，而整个对象则被视为值。这在许多实际应用中十分常见，例如当希望存储一组具有唯一标识符的Employee信息时。

这些对象通常采用如下形式：

class Employee
{
public:
    explicit Employee(int id, std::string const& name) : id_(id), name_(name) {}
    int getId() const { return id_; }
    std::string getName() const { return name_; }

private:
    int id_;
    std::string name_;
};

Employee 类表示一个员工，其中包含两个数据成员：id_ 和 name_，分别用于表示员工的 ID 和姓名。

希望能够在 std::set 中存储多个员工。由于比较任意两个员工并决定其相对大小没有实质意义，而每名员工都有唯一的 ID，凭借该 ID 即可提供一个技术性顺序，从而按该顺序对员工在集合中进行排序。因此，选择使用 std::set 来存储员工，并根据其 ID 进行排列。

为实现这一目的，C++ 的std::set提供了自定义比较器的功能。比较器是一个函数对象，它定义了集合中元素的比较规则。

struct CompareId
{
    bool operator()(Employee const& employee1, Employee const& employee2) const {
        return employee1.getId() < employee2.getId();
    }
};

std::set<Employee, CompareId> employees;

定义了名为 CompareId 的比较器，明确了如何对两个 Employee 对象进行比较。该比较器利用 operator() 函数接收两个 Employee 对象为参数，并返回布尔值，指示第一个员工是否小于第二个员工。比较器通过 getId() 方法获取每个员工的 ID，并依据这些 ID 进行比较。

通过这样的方式，集合中的员工将根据 ID 进行合理排序。该功能自 C++98 以来便已存在。

然而，一旦开始使用此排序特性，通常会出现一个基本需求，即通过 ID 搜索员工。即希望能够利用一个 ID 值来查找集合中对应的员工。

你可能会想：“没问题！我可以添加几个比较函数来解决这个问题！”。

struct CompareId
{
    bool operator()(Employee const& employee1, Employee const& employee2) const
    {
        return employee1.getId() < employee2.getId();
    }
    bool operator()(int id, Employee const& employee) const
    {
        return id < employee.getId();
    }
    bool operator()(Employee const& employee, int id) const
    {
        return employee.getId() < id;
    }
};

添加了两个新的 operator() 函数，以便能够比较 int 类型的值和 Employee 对象。这样一来，程序员可以通过传入一个整数 ID（代表员工的 ID）与集合中的 Employee 对象进行比较。

然而，当调用 ID 的搜索时…

std::set<Employee, CompareId> employees = { Employee(1, "John"), Employee(2, "Bill") };
std::cout << employees.find(1)->getName() << '\
';

该代码并未成功编译。“怎么会这样？”，“这是为什么呢？”。答案在于 find 方法的原型：

iterator find( const Key& key );

实际上，find 方法仅接受与集合元素类型完全相同的键。因此，尽管比较是基于元素的 ID 部分，仍然必须传入一个 Employee 对象。

C++ 文档应该存在解决办法。事实证明并未有简单的解决方案。一些不太合适的选择：

通过向 Employee 类添加一个仅接收引用的构造函数，以构造不完整的“空”员工，仅为进行比较，
通过使用 std::map<int, Employee>，从而打破了整个设计，导致 ID 的重复存储。
通过将 Employee 类中的 ID 移除，并将其作为键用于 std::map<int, Employee> 中，进而破坏有意义的设计以避免 ID 的重复。

就在绝望的修改整个程序时，C++14 的到来及时为其提供了救赎。

is_transparent_96">三、is_transparent

本质上，C++14 通过为 find 方法引入新重载，以及对 count、lower_bound、upper_bound 和 equal_range 重载的增强，填补了这一空白。这些重载是模板化的，理论上可以接受任何能够与 Employee 进行比较的类型，包括其 ID。

为了实现这些重载，比较函数对象需要定义一个名为 is_transparent 的类型别名。此类型别名的具体值并不重要，唯一重要的是其被定义的状态：

struct CompareId
{
    using is_transparent = void; // 可使用 void，也可选择 int 或 struct CanSearchOnId;
    bool operator()(Employee const& employee1, Employee const& employee2) const
    {
        return employee1.getId() < employee2.getId();
    }
    bool operator()(int id, Employee const& employee) const
    {
        return id < employee.getId();
    }
    bool operator()(Employee const& employee, int id) const
    {
        return employee.getId() < id;
    }
};

上using is_transparent = void; 语句表明该比较器支持透明比较。这一特性允许使用不同于集合元素类型的值进行比较。

因此，find 方法将按预期顺利执行。以下代码将编译通过并产生结果：

std::set<Employee, CompareId> employees = { Employee(1, "Lion"), Employee(2, "Long") };
std::cout << employees.find(1)->getName() << '\
';

这一功能以比通用 lambda 表达式等新特性更为低调但仍然极具价值的方式融入标准库，为我们在使用关联容器时提供了一个更优雅且更简洁的方法，以便利用不同类型的键进行搜索。

四、总结

is_transparent 是 C++14 中一项强大的创新，允许我们以与集合元素类型不同的值进行搜索。这一功能简化了代码设计，提升了开发效率，为我们在关联容器上执行操作提供了更大的灵活性。
在这里插入图片描述