map key是一個複雜結構，為什麼無法插入?

我在項目中實現std::map（key是一個std::pair）有序的時候，進行了二次封裝，按值排序，當時在使用過程中這個map find無法查找到我的key,我調試的時候發現find的時候也是調用了自定義的比較函數的。這是怎麼回事，求指導一下。

比如我自定義了一個按值比較：

template&
struct Compare
{
bool operator() (const T1 st1,const T2 st2 )
{
if( st1.cost() &>= st2.cost() )
return true;

return false;
}
};


//以下是相同複雜的key的時候，無法查找到，這是什麼願意啊？

typename DataMapIteretor it2 = m_kCache.find(std::pair&(tKey,it1-&>second));
if( it2 == m_kCache.end())
return;


template&
struct Value_Compare :public std::binary_function&
{
Comp ValueComp_;
bool operator()(const T1 p1,const T1 p2)
{
return ValueComp_(p1.second,p2.second);
}
};

template&
class NewRankCache
{
public:
typedef Comp ValueComp;
ValueComp ValueComp_;

typedef std::pair& KeyValuePair;
typedef mem::map&&> DataEntrySortedMap;
typedef typename DataEntrySortedMap::iterator DataMapIteretor;

private:
typedef mem::map& KeysMap;
typedef typename KeysMap::iterator KeysIterator;
KeysMap m_kKeys;
DataEntrySortedMap m_kCache;
uint32_t m_uiMaxSize;

public:
void NewRankCache::PopByKey(const T1 tKey)
{
typename KeysIterator it1 = m_kKeys.find(tKey);
if( it1 == m_kKeys.end() )
return;

typename DataMapIteretor it2 = m_kCache.find(std::pair&(tKey,it1-&>second));
if( it2 == m_kCache.end())
return;

m_kCache.erase(it2);
m_kKeys.erase(it1);
}

void NewRankCache::PushValue(const T1 tKey, const T2 tValue)
{

//是否key存在
T2* ptemp = GetValueByKey(tKey);
if( ptemp )
{
if( !ValueComp_(tValue,*ptemp) )
return;

PopByKey(tKey);
SetChanged(true);
m_kKeys.insert(KeyValuePair(tKey,tValue));
m_kCache.insert(std::make_pair&(KeyValuePair(tKey,tValue),tValue));
return;
}

if( m_kCache.size() &>= m_uiMaxSize )
{
T2* ptemplast = GetLastValue();
if( ptemplast )
{
if( ValueComp_( tValue,*ptemplast))
PopLastOne();
}
}

if( m_kCache.size() &< m_uiMaxSize ) { SetChanged(true); m_kKeys.insert(KeyValuePair(tKey,tValue)); m_kCache.insert(std::make_pair&(KeyValuePair(tKey,tValue),tValue));
}
}

T2* NewRankCache::GetValueByKey(const T1 tKey)
{
T2* ptemp = NULL;
typename KeysIterator it1 = m_kKeys.find(tKey);
if( it1 != m_kKeys.end() )
{
ptemp = (it1-&>second);
}

return ptemp;

}


---

《Effective STL》

Item 21: Always have comparison functions return false for equal values.

---

這算是一種，對沒經驗的人來說，不容易想到的問題吧……

在用STL的時候，不管管你是algorithm的sort()、lower_bound()，還是set&<&>、map&<&>，這些需要比較的地方，用自定義的struct/class的時候，請千萬定義一個嚴格的小於號。

嚴格的小於號是指，對a和b兩個對象，調用小於比較的時候，實際情況下a&（一個嚴格定義的小於號就能判斷2者之間的關係了，對任意兩個待比較對象a和b

a&a&

a&b

兩者都為true，抱歉我還真不知道該說什麼……）

如果a==b返回true，如果是用sort()，根據你的數據不同，有一定概率會導致無限死循環遞歸下去，Stack Overflow（雖然更多情況下能sort完）……

至於std::set/std::map里，因為無法正確區分相等和小於，出現什麼錯誤都是有可能的。

---

請實現一個小於號，而不是其他。

---

其實你需要的是保證任何時候 x小於y 和 y小於x 有且僅有其中之一成立。

---

推薦閱讀：