当前位置：首页 > news >正文

stl 实现非容器类型元素和容器元素比较

news 来源：原创 2025/7/24 1:23:30

在 C++ 标准模板库（STL）中，有许多算法可以接受自定义的比较函数（Compare）。这些算法通常涉及排序、查找、合并、集合操作等场景，允许用户通过 Compare 函数指定如何比较两个元素。

自定义compare的算法

排序相关算法

std::sort

std::stable_sort

std::partial_sort

查找相关算法

在已排序范围中查找元素，支持自定义比较规则。

std::binary_search
std::lower_bound
std::upper_bound
std::equal_range

合并和集合操作相关算法

操作两个已排序范围，需要比较规则保持一致。

std::merge
std::inplace_merge
std::set_union
std::set_intersection
std::set_difference

自定义比较函数的形式

自定义比较函数（Compare）通常是一个二元谓词，用于比较两个元素，返回 true 表示第一个元素应该排在第二个元素之前。形式为：

bool Compare(const T& a, const T& b);

以下代码演示 std::sort 和 std::binary_search 的自定义比较函数：

#include <algorithm>
#include <vector>
#include <iostream>bool descending(const int& a, const int& b) {return a > b; // 降序
}int main() {std::vector<int> data = {1, 3, 5, 7, 9};// 按降序排序std::sort(data.begin(), data.end(), descending);// 输出排序后的结果for (int v : data) {std::cout << v << " ";}std::cout << "\n";// 二分查找int target = 5;if (std::binary_search(data.begin(), data.end(), target, descending)) {std::cout << "Found " << target << "\n";} else {std::cout << "Not found " << target << "\n";}return 0;
}

非容器类型元素的比较

有时候我们会遇到需要根据非容器类型元素进行查找的需求，例如我需要根据一个索引，在有序容器中查找一个对象，这个时候我的查找目标对象和容器元素类型是不一样的，我们看下面例子，如下对象是对一个uint64_t的简单封装

class IdxObject
{
public:operator uint64_t() const{return m_idx;}private: // not allow directly constructIdxObject(uint64_t idx):m_idx((idx)){}private:uint64_t m_idx;
};

现在我需要根据一个uint64_t类型的idx，在容器中使用上面提到的lower_bound查找IdxObject对象，函数申明如下:

IdxObject* findInVector(std::vector<IdxObject*>& vec, const uint64_t& idx)

Predict函数实现

PredIdxObj仿函数是正常的IdxObject的compare函数，这个很容易理解，下面的PredDummyIdxObj的仿函数就是我们用到的技巧，我们将uint64_t类型的idx封装成一个虚拟的IdxObject对象，并用dumyFlag来标识这是一个虚拟对象

class PredIdxObj
{
public:bool operator()(const IdxObject* p1, const IdxObject* p2) const{return (uint64_t)(*p1) < (uint64_t)(*p2);}
};class PredDummyIdxObj
{
public:static const uint64_t dumyFlag = (uint64_t)(-1);struct DummyIdxObj{public:uint64_t m_flag;uint64_t m_idx;DummyIdxObj(const uint64_t& idx): m_flag(dumyFlag), m_idx(idx){}};bool operator()(const IdxObject* p1, const IdxObject* p2) const{if (dumyFlag == (*(uint64_t*)p1))return ((DummyIdxObj*)p1)->m_idx < (uint64_t)(*p2);elsereturn (uint64_t)(*p1) < ((DummyIdxObj*)p2)->m_idx;}
};

那么我们的查找函数实现如下，看到实现代码，就会发现，这个技巧非常巧妙。

IdxObject* findInVector(std::vector<IdxObject*>& vec, const uint64_t& idx)
{if (vec.size() <= 0)return nullptr;PredDummyIdxObj::DummyIdxObj target(idx);PredDummyIdxObj pred;auto iter = std::lower_bound(vec.begin(), vec.end(), (IdxObject*)(&target), pred);if (iter == vec.end())return nullptr;elsereturn *iter;
}