CATEGORY / Development

微软 STL lower_bound() 在 DEBUG 下的诡异编译错误

Permanent Link: http://wutiam.net/notes/136

众所周知,在 STL 中,对于有序的 vector 容器,使用 binary_search、lower_bound/upper_bound 等搜索算法要比直接 find 高效得多。但是由于各个 STL 实现版本没有统一的标准,在 DEBUG 环境下各自的校验机制千差万别,这就导致可能出现一些让人郁闷的情况,比如这次的主角,微软的 STL。

现在有一个有序容器 kTasks,比如是 vector 或 deque,容器中保存的是 task 对象,task 对象中有一个 priority 的属性,容器以 task 的 priority 值降序排序。我们需要频繁查询当前该容器中有多少个 task 的 priority 高于一个给定的值,最高效的办法之一是通过 std::lower_bound() 直接拿到区间,再用 std::distance() 直接统计就行了。

1
2
3
4
5
6
7
8
9
10
11
bool PriorityLesser(CTask* pkTask, int nPriority)
{
    return pkTask->GetPriority() >= nPriority;
}
 
unsigned int CountIfPriorityIsGE(int nPriority)
{
    return kTasks.empty() 
        ? 0
        : (unsigned int)std::distance(kTasks.begin(), std::lower_bound(kTasks.begin(), kTasks.end(), nPriority, PriorityLesser));
}

杯具就这么来了,由于这里使用的 std::lower_bound() 是带比较器的,在 DEBUG 模式下编译不过(RELEASE 下没问题),错误很莫名其妙,类似这样:

error C2664: 'bool (CTask *,int)' : cannot convert parameter 2 from 'CTask *' to 'int'
...
see reference to function template instantiation 'bool std::_Debug_lt_pred<_Pr,CTask*,_Ty>(_Pr,_Ty1 &,const _Ty2 &,const wchar_t *,unsigned int)' being compiled

这是啥破玩意儿呀?!MSDN 里的例子很简单,也没说有这种情况,难道是微软 STL 的 bug?没看到有人报过啊。只好硬着头皮看 MS STL 天书般的源代码了。

先来看看 lower_bound() 的代码(知道啥是天书了吧):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
		// TEMPLATE FUNCTION lower_bound WITH PRED
template<class _FwdIt,
	class _Ty,
	class _Diff,
	class _Pr> inline
	_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last,
		const _Ty& _Val, _Pr _Pred, _Diff *)
	{	// find first element not before _Val, using _Pred
	_DEBUG_POINTER(_Pred);
	_DEBUG_ORDER_SINGLE_PRED(_First, _Last, _Pred, true);
	_Diff _Count = 0;
	_Distance(_First, _Last, _Count);
	for (; 0 < _Count; )
		{	// divide and conquer, find half that contains answer
		_Diff _Count2 = _Count / 2;
		_FwdIt _Mid = _First;
		std::advance(_Mid, _Count2);
		_DEBUG_ORDER_SINGLE_PRED(_Mid, _Last, _Pred, false);
 
		if (_DEBUG_LT_PRED(_Pred, *_Mid, _Val))
			_First = ++_Mid, _Count -= _Count2 + 1;
		else
			_Count = _Count2;
		}
	return (_First);
	}

先注意第 10 行和第 18 行的这两个 _DEBUG_ORDER_SINGLE_PRED(),再往里跟,这个宏在 DEBUG 模式下实际执行的代码基本就是:

1
2
3
4
5
6
7
8
9
10
template<class _Pr, class _Ty1, class _Ty2> inline
	bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, const _Ty1& _Left, _Ty2& _Right,
		const wchar_t *_Where, unsigned int _Line)
	{	// test if _Pred(_Left, _Right) and _Pred is strict weak ordering
	if (!_Pred(_Left, _Right))
		return (false);
	else if (_Pred(_Right, _Left))
		_DEBUG_ERROR2("invalid operator<", _Where, _Line);
	return (true);
	}

因为这时传入的都是容器的 iterator,所以实际上是在检查当前容器是否真的有序。。。

这还不算完,再看 lower_bound() 第 20 行的 _DEBUG_LT_PRED(),这个宏在 RELEASE 下是直接调用比较器,而在 DEBUG 下,又是去调用了上面那个 _Debug_lt_pred(),但传入的参数是一个迭代器和一个比较值,也就是既要做正常判断,又要检查反向比较时得到的结果是否正好相反。

终于明白了 DEBUG 下 lower_bound() 都干了些啥,那问题就好解决了。我们的比较器只提供了正常的比较操作(左项为迭代器、右项为比较值),还缺少用于检查容器是否有序的比较器(左右项都为迭代器)和用于检查反向比较的比较器(左项为比较值、右项为迭代器),这么一来,比较器就不能再使用普通函数了,必须以仿函数类的形式来提供所需的三种功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct PriorityLesser
{
    bool operator()(CTask* pkTask, int nPriority) const
    {
        return pkTask->GetPriority() >= nPriority;
    }
#ifdef _DEBUG
    bool operator()(int nPriority, CTask* pkTask) const
    {
        return pkTask->GetPriority() >= nPriority;
    }
    bool operator()(CTask* pkTask1, CTask* pkTask2) const
    {
        return pkTask1->GetPriority() > pkTask2->GetPriority();
    }
#endif // _DEBUG
};
 
unsigned int CountIfPriorityIsGE(int nPriority)
{
    if (kTasks.empty())
    {
        return 0;
    }
 
    OperationQueue::iterator itr = std::lower_bound(kTasks.begin(), kTasks.end(), nPriority, PriorityLesser());
    OperationQueue::difference_type diff = std::distance(kTasks.begin(), itr);
    return (unsigned int)diff;
}

呼~

No Comments / Trackbacks / Pingbacks

Leave a Reply

:) :wink: 8-O :lol: :-D 8) :-| :mrgreen: :oops: :-o :-? :( :twisted: :cry: more »