如何在C++的pair类型unordered_set中以O(1)复杂度查找首元素为x的pair

问题背景 #

需要删除unordered_set<pair<int, int>>中首元素为指定值的pair，当前用find_if实现查找，但复杂度是O(n)，希望实现类似unordered_set::find的O(1)平均复杂度查找。现有代码如下：

typedef pair<int, int> pairs;

// Hash function
struct hashFunction{
   size_t operator()(const pairs &x) const{return x.first ^ x.second;}
};

// 注意：原Comparator函数写法错误，返回值是pair而非bool，无法编译
struct comp{
    bool operator()(pairs a , pairs b){     
        return a.first < b.first ? a : b;
    }
};

// 目标函数
void delEdge(unordered_set<pairs, hashFunction, comp> adj[], int u, int v){
    adj[v].erase(/* 查找首元素为u的pair的迭代器 */);
    adj[u].erase(/* 查找首元素为v的pair的迭代器 */);
}

此前用find_if的实现：

find_if(adj[v].begin(), adj[v].end(), [](auto& el){ return el.first == u; });

但该方法复杂度为O(n)，无法满足高效需求。

解决方案 #

核心问题分析 #

unordered_set的find方法能实现O(1)平均复杂度，依赖两个条件：

1. 哈希函数能将目标元素映射到正确的桶；
2. 相等比较器能精准识别目标元素与集合中元素的相等性。

但需求是按pair的首元素查找，而非整个pair的完全匹配，unordered_set本身不支持这种“部分键”的查找。此外原代码中的comp函数存在语法错误（返回pair而非bool），根本无法正常工作。

方案1：替换为unordered_map（推荐） #

如果邻接表中每个节点的邻居是唯一的（无重边），直接用unordered_map<int, int>替代unordered_set<pair<int, int>>，其中key对应原pair的首元素，value对应原pair的尾元素。这样查找和删除操作都是O(1)平均复杂度：

// 修改邻接表类型为unordered_map
void delEdge(unordered_map<int, int> adj[], int u, int v){
    adj[v].erase(u); // 直接通过key=u查找并删除，O(1)平均复杂度
    adj[u].erase(v);
}

方案2：调整unordered_set的哈希与比较器（仅适用于单重边场景） #

如果必须保留unordered_set，且每个首元素对应唯一的pair（无重边），可以调整哈希函数和相等比较器，让仅首元素相同即判定为相等，同时哈希仅基于首元素：

typedef pair<int, int> pairs;

// 哈希函数仅基于pair的首元素
struct hashFunction{
   size_t operator()(const pairs &x) const{
       return hash<int>()(x.first);
   }
};

// 相等比较器：仅比较首元素
struct comp{
    bool operator()(const pairs &a, const pairs &b) const{
        return a.first == b.first;
    }
};

// 此时查找可以用find构造一个临时pair（尾元素不影响）
void delEdge(unordered_set<pairs, hashFunction, comp> adj[], int u, int v){
    // 构造临时pair，尾元素任意即可
    adj[v].erase(pairs{u, 0});
    adj[u].erase(pairs{v, 0});
}

注意：这种方案下，unordered_set中无法存在首元素相同的多个pair（会被判定为重复元素），仅适用于无重边的邻接表场景。

方案3：接受O(n)复杂度（适用于有重边场景） #

如果邻接表允许重边（同一首元素对应多个pair），则无法通过unordered_set::find实现O(1)查找，只能继续使用find_if，或者改用multiset并配合自定义排序，但multiset的查找复杂度是O(logn)：

void delEdge(unordered_set<pairs, hashFunction, comp> adj[], int u, int v){
    auto it = find_if(adj[v].begin(), adj[v].end(), [u](const auto& el){
        return el.first == u;
    });
    if(it != adj[v].end()){
        adj[v].erase(it);
    }
    // 同理处理adj[u]
    it = find_if(adj[u].begin(), adj[u].end(), [v](const auto& el){
        return el.first == v;
    });
    if(it != adj[u].end()){
        adj[u].erase(it);
    }
}

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