VC++如何使用C++ STL标准模板库中的算法函数（附源码）

VC++常用功能开发汇总（专栏文章列表，欢迎订阅，持续更新...）https://blog.csdn.net/chenlycly/article/details/124272585 STL（Standard Templete Library）活动模板库已被广泛地应用于各种C++程序的开发中，STL中vector、list、map等列表极大地方便了我们日常的开发，不再需要我们去实现链表等数据结构，使用这些列表能基本能解决开发过程中遇到的各种问题。今天我们就来讲讲如何使用STL内置的算法函数。

1、概述

   STL中提供了sort、conut、count_if、find、find_if、remove_copy、remove_copy_if等多个算法函数，我们不需要再自己去实现搜索或排序算法，使用STL提供的这些算法函数就能轻易地完成对应的任务。此外，当vector、list等STL列表中存放的数据量比较大时，直接使用for循环去遍历列表，去按条件搜索，效率就是个问题了，而使用STL的算法函数可以有效的提升搜索效率，提高代码的运行速度。

STL提供了哪些算法函数，以及算法函数的详细说明，可以参见《STL源码剖析》一书的第6章。

2、调用sort函数对列表元素进行排序

   STL中的sort排序函数用的比较多，UI层在显示列表时，需要根据列表元素的名称进行排序，一般我们先在内存中进行排序。列表元素存放在STL列表中，我们调用STL算法函数sort进行排序。比如列表中的存放的是设备信息，设备信息结构体如下所示：（文章中的后续示例代码均以该结构体来说明）

// 设备信息
struct TDeviceInfo 
{
    char achDeviceId[64];   // 设备id
    char achDeviceName[64]; // 设备名称
    int nDevType;            // 设备类型
};

设备信息列表数据存放在vector列表vtDevList中：

vector<TDeviceInfo> vtDevList; // 存放设备信息的列表

   比如我们需要按照设备名称做升序排列，相关代码如下所示：

std::sort( vtDevList.begin(), vtDevList.end(), [](TDeviceInfo& tDevInfo1, TDeviceInfo& tDevInfo2)->bool{
CString strDevName1 = CopyUtf8ToCStringT(tDevInfo1.achDeviceName);
CString strDevName2 = CopyUtf8ToCStringT(tDevInfo2.achDeviceName);
return (lstrcmp( strDevName1, strDevName2 ) < 0);
});

上述代码中使用到了C++11引入的匿名函数，即lamda表达式。在低版本的Visual Studio中是不支持C++11规范的，所以要专门写个比较函数，设置到sort接口中，如下所示：

BOOL NameCompare( TDeviceInfo& tDevInfo1, TDeviceInfo& tDevInfo2 )
{
    CString strDevName1 = CopyUtf8ToCStringT(tDevInfo1.achDeviceName);
    CString strDevName2 = CopyUtf8ToCStringT(tDevInfo2.achDeviceName);
    return (lstrcmp( strDevName1, strDevName2 ) < 0);
}
std::sort( vtDevList.begin(), vtDevList.end(), NameCompare );

3、调用count_if查找满足条件的元素个数

   当我们需要到列表中搜索满足搜索条件的的元素个数时，可以使用count_if算法函数。比如我们需要到设备列表中搜索包含“东城区”关键字的所有设备个数，实现代码如下：

CString strKeyWords = _T("东城区");
std::count_if( vtDevList.begin(), vtDevList.end(), [&](TDeviceInfo& tDevInfo)->bool{
CString strDevName = CopyUtf8ToCStringT(tDevInfo.achDeviceName);
int nPos = strDevName.Find( strKeyWords );
return (nPos != -1 );
});

   同样上述代码中也使用到了匿名函数，和上一个示例代码不同的是，我们在“[]”中添加了&符号，使用该符号表示匿名函数可以访问所在函数中的变量。上例中的匿名函数中就访问了所在函数中的局部变量strKeyWords。

4、调用find_if函数找到目标元素的信息

   当我们需要到列表中搜索满足条件的设备信息时，可以使用find_if算法函数，该函数返回满足条件的元素对应的迭代器。比如我们要搜索设备id为E40CF3E4-CC2B-437F-A4B9-65F2D5BD0712的设备信息，示例代码如下：

char* pTarget = "E40CF3E4-CC2B-437F-A4B9-65F2D5BD0712";
 
vector<TDeviceInfo>::iterator itor = std::find_if(vtDevList.begin(), vtDevList.end(), 
[&](TDeviceInfo tInfo) { return strcmp(pTarget, tInfo.achDeviceId)==0; } );
if (itor != vtDevList.end())
{
    // 找到目标设备
}

有人可能会问，此处我们能不能使用find接口？我们可以go到STL算法函数的内部实现代码中：

template<class _InIt,
    class _Ty> inline
    _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
    {    // find first matching _Val
    _DEBUG_RANGE(_First, _Last);
    return (_Rechecked(_First,
        _Find(_Unchecked(_First), _Unchecked(_Last), _Val)));
    }
        // TEMPLATE FUNCTION find
template<class _InIt,
    class _Ty> inline
    _InIt _Find(_InIt _First, _InIt _Last, const _Ty& _Val)
    {    // find first matching _Val
    for (; _First != _Last; ++_First)
        if (*_First == _Val)
            break;
    return (_First);
    }

   传入的搜索条件是整个元素信息，如果STL列表中存放的是TDeviceInfo结构体对象，给Find函数传入的搜索条件就是一个TDeviceInfo对象，那这个Find函数内部是否相等的判断条件该如何解释呢？默认情况下，对于TDeviceInfo结构体，所有成员值相等，结构体对象才会相等的，显然我在搜素某个设备时，肯定是不知道目标设备的所有信息的，所以我们需要在该结构体中重载==操作符，在该函数中判断两个结构体是否相等。如下所示，设备Guid是全局唯一的，我们只要判断设备Guid是否相等就能确定是不是同一个设备了，所以我们实现如下的重载函数：

// 设备信息
struct TDeviceInfo 
{
    char achDeviceId[64];   // 设备id
    char achDeviceName[64]; // 设备名称
    int nDevType;            // 设备类型
    // 重载==操作符
    BOOL operator==( const TDeviceInfo& tDevInfo )
    {
        return !strcmp(achDeviceId, tDevInfo.achDeviceId);
    }
};

那下面就可以使用如下的代码去调用find函数了：

TDeviceInfo tDevInfo;
strcpy( tDevInfo.achDeviceId, "E40CF3E4-CC2B-437F-A4B9-65F2D5BD0712" );
TDeviceInfo tTragetDevInfo = std::find( vtDevList.begin(), vtDevList.end(), tDevInfo );

5、调用remove_copy_if函数搜索满足条件的多个元素

   我们有时需要到STL列表去搜索满足搜索条件的多个元素。比如我们要到设备列表中去搜索所有包含“东城区”字样的所有设备信息，使用for循环去遍历的代码如下：

// 通过for循环去遍历列表搜目标设备
char* pMatchNameStr = "东城区";
vector<TDeviceInfo> vtMatchedDevList; // 存放满足匹配条件的元素
vector<TDeviceInfo>::iterator itor = vtDevList.begin();
for (; itor != vtDevList.end(); itor++)
{
    CStringA strDeviceName = itor->achDeviceName;
    if (strDeviceName.Find(strDeviceName) != -1)
    {
        vtMatchedDevList.push_back(*itor);
    }
}

   当设备列表vtDevList中存放了数万个元素时，上述for循环搜索的效率就不太高了，我们可以通过使用remove_copy_if算法函数去对现有代码进行替换：

BOOL MatchDeviceFunc(TDeviceInfo& tInfo)
{
    char* pMatchNameStr = "东城区";
 
    CStringA strDeviceName = tInfo.achDeviceName;
    if ( strDeviceName.Find(pMatchNameStr) != -1 )
    {
        return TRUE;
    }
 
    return FALSE;
}
 
vector<TDeviceInfo> vtMatchedDevList;
std::remove_copy_if(vtDevList.begin(), vtDevList.end(), std::back_inserter(vtMatchedDevList), &MatchDeviceFunc);

   对于上述remove_copy_if调用，前两个参数指明搜索开始和结束的迭代器，第三个元素指定存放满足搜索条件的元素的列表，第四个参数指定条件判断函数MatchDeviceFunc。
    remove_copy_if算法函数的调用，可以有效地提升搜索速度。在我们项目中做过类似这样的优化，搜索速度可以提升1到2个数量级。

6、总结

   在我们搜索STL列表速度遇到瓶颈时，可以考虑使用STL自带的算法函数去有效提升搜索效率。其实我们以前对比过STL算法函数内部的实现，很多STL算法函数内部实现和我们直接去通过for循环遍历的代码是类似的，甚至是一模一样的，比如find_if算法函数的实现，那为啥使用算法函数时就是要快很多呢？可能是编译器能对算法函数中的代码进行更好的优化，使其在运行时能跑的更快一点。