C++ 具名要求-全库范围的概念 - 函数对象 (FunctionObject) ，对于不同输入值产生相同输出具有很低概率-散列（hash）

此页面中列出的具名要求，是 C++ 标准的规范性文本中使用的具名要求，用于定义标准库的期待。

某些具名要求在 C++20 中正在以概念语言特性进行形式化。在那之前，确保以满足这些要求的模板实参实例化标准库模板是程序员的重担。若不这么做，则可能导致非常复杂的编译器诊断。

全库范围的概念

函数对象 (FunctionObject) ，对于不同输入值产生相同输出具有很低概率

C++ 具名要求： Hash

散列 (Hash) 是函数对象，其输出仅依赖于输入，且当给定不同输入值时，有非常低的概率生成相同输出。

要求

以下情况下，类型 T 满足散列 (Hash) ：

• 类型 T 满足函数对象 (FunctionObject) 、可复制构造 (CopyConstructible) 、可析构 (Destructible) ，且

给定

• T 或 const T 类型的值 h，其实参类型是 Key
• 可转换为 Key 或 const Key 的值 k
• Key 类型的左值表达式 u

下列表达是必须合法且拥有其指定的效果

调用示例

#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <thread>
#include <typeindex>

struct Cell
{
    int x;
    int y;

    Cell() = default;
    Cell(int a, int b): x(a), y(b) {}

    bool operator <(const Cell &cell) const
    {
        if (x == cell.x)
        {
            return y < cell.y;
        }
        else
        {
            return x < cell.x;
        }
    }

    bool operator ==(const Cell &cell) const
    {
        if (x == cell.x)
        {
            return y < cell.y;
        }
        else
        {
            return x < cell.x;
        }
    }
};

std::ostream &operator<<(std::ostream &os, const Cell &cell)
{
    os << "{" << cell.x << "," << cell.y << "}";
    return os;
}

// std::hash 的自定义特化能注入 namespace std
namespace std
{
/*库函数提供的 hash 的所有显式和部分特化可默认构造 (DefaultConstructible) 、
 * 可复制赋值 (CopyAssignable) 、可交换 (Swappable) 且可析构 (Destructible) 。
 * 用户提供的 hash 特化亦必须满足这些要求。*/

template<>
struct hash<Cell>
{
    size_t operator()(const Cell &cell) const
    {
        return cell.x + cell.y;
    }
};
}

int main()
{
    std::cout << "std::hash<Cell> {}(Cell(1, 1)):       "
              << std::hash<Cell> {}(Cell(1, 1)) << std::endl;
    std::cout << "std::hash<Cell> {}(Cell(101, 102)):   "
              << std::hash<Cell> {}(Cell(101, 102)) << std::endl;
    std::cout << "std::hash<std::string> {}(\"GGX\"):     "
              << std::hash<std::string> {}("GGX") << std::endl;
    std::cout << "std::hash<int> {}(123):               "
              << std::hash<int> {}(123) << std::endl;
    std::cout << "std::hash<long> {}(123456):           "
              << std::hash<long> {}(123456) << std::endl;
    std::cout << "std::hash<bool> {}(true):             "
              << std::hash<bool> {}(true) << std::endl;
    std::cout << "std::hash<float> {}(3.14):            "
              << std::hash<float> {}(3.14) << std::endl;
    std::cout << "std::hash<double> {}(3.14):           "
              << std::hash<double> {}(3.14) << std::endl;
    std::cout << "std::hash<std::type_index> {}(typeid(int)):   "
              << std::hash<std::type_index> {}(typeid(int)) << std::endl;
    std::cout << "std::hash<std::type_index> {}(typeid(Cell)):  "
              << std::hash<std::type_index> {}(typeid(Cell)) << std::endl;
    std::cout << "std::hash<std::thread::id> {}(std::this_thread::get_id()):    "
              << std::hash<std::thread::id> {}(std::this_thread::get_id()) << std::endl;
    return 0;
}

输出

std::hash<Cell> {}(Cell(1, 1)):       2
std::hash<Cell> {}(Cell(101, 102)):   203
std::hash<std::string> {}("GGX"):     349164991
std::hash<int> {}(123):               123
std::hash<long> {}(123456):           123456
std::hash<bool> {}(true):             1
std::hash<float> {}(3.14):            584703180
std::hash<double> {}(3.14):           1427109137
std::hash<std::type_index> {}(typeid(int)):   3616029859
std::hash<std::type_index> {}(typeid(Cell)):  1483223384
std::hash<std::thread::id> {}(std::this_thread::get_id()):    1753268367