下面是map定義的結構：
// TEMPLATE CLASS map
template<class _Kty,
class _Ty,
class _Pr = less<_Kty>,
class _Alloc = allocator<pair<const _Kty, _Ty> > >
class map
: public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> >
{ // ordered red-black tree of {key, mapped} values, unique keys
public:
typedef map<_Kty, _Ty, _Pr, _Alloc> _Myt;
typedef _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> > _Mybase;
typedef _Kty key_type;
typedef _Ty mapped_type;
typedef _Ty referent_type; // retained
typedef _Pr key_compare;
typedef typename _Mybase::value_compare value_compare;
typedef typename _Mybase::allocator_type allocator_type;
typedef typename _Mybase::size_type size_type;
typedef typename _Mybase::difference_type difference_type;
typedef typename _Mybase::pointer pointer;
typedef typename _Mybase::const_pointer const_pointer;
typedef typename _Mybase::reference reference;
typedef typename _Mybase::const_reference const_reference;
typedef typename _Mybase::iterator iterator;
typedef typename _Mybase::const_iterator const_iterator;
typedef typename _Mybase::reverse_iterator reverse_iterator;
typedef typename _Mybase::const_reverse_iterator
const_reverse_iterator;
typedef typename _Mybase::value_type value_type;
map()
: _Mybase(key_compare(), allocator_type())
{ // construct empty map from defaults
}
explicit map(const key_compare& _Pred)
: _Mybase(_Pred, allocator_type())
{ // construct empty map from comparator
}
map(const key_compare& _Pred, const allocator_type& _Al)
: _Mybase(_Pred, _Al)
{ // construct empty map from comparator and allocator
}
template<class _Iter>
map(_Iter _First, _Iter _Last)
: _Mybase(key_compare(), allocator_type())
{ // construct map from [_First, _Last), defaults
_DEBUG_RANGE(_First, _Last);
for (; _First != _Last; ++_First)
this->insert(*_First);
}
template<class _Iter>
map(_Iter _First, _Iter _Last,
const key_compare& _Pred)
: _Mybase(_Pred, allocator_type())
{ // construct map from [_First, _Last), comparator
_DEBUG_RANGE(_First, _Last);
for (; _First != _Last; ++_First)
this->insert(*_First);
}
template<class _Iter>
map(_Iter _First, _Iter _Last,
const key_compare& _Pred, const allocator_type& _Al)
: _Mybase(_Pred, _Al)
{ // construct map from [_First, _Last), comparator, and allocator
_DEBUG_RANGE(_First, _Last);
for (; _First != _Last; ++_First)
this->insert(*_First);
}
#if _HAS_STRICT_CONFORMANCE
void erase(iterator _Where)
{ // erase element at _Where
_Mybase::erase(_Where);
}
size_type erase(const key_type& _Keyval)
{ // erase and count all that match _Keyval
return (_Mybase::erase(_Keyval));
}
void erase(iterator _First, iterator _Last)
{ // erase [_First, _Last)
_Mybase::erase(_First, _Last);
}
#endif /* _HAS_STRICT_CONFORMANCE */
mapped_type& operator[](const key_type& _Keyval)
{ // find element matching _Keyval or insert with default mapped
iterator _Where = this->lower_bound(_Keyval);
if (_Where == this->end()
|| this->comp(_Keyval, this->_Key(_Where._Mynode())))
_Where = this->insert(_Where,
value_type(_Keyval, mapped_type()));
return ((*_Where).second);
}
};
less的定義
template<class _Ty>
struct less
: public binary_function<_Ty, _Ty, bool>
{ // functor for operator<
bool operator()(const _Ty& _Left, const _Ty& _Right) const
{ // apply operator< to operands
return (_Left < _Right);
}
};
從上面定義可以看出，map<_Kty, _Ty, _Pr, _Alloc>的後兩個默認的參數，class _Pr = less<_Kty> , class _Alloc = allocator<pair<const _Kty, _Ty> > >；
而默認缺省定義map時，此時如果結構體為key值時，而此時class _Pr = less<_Kty>要進行_Left < _Right，而如果此時結構體沒有<方法時，則會出錯。
解決上面問題有兩種方法：1.在結構體重重載<操作符；2.定義自己的排序函數，顯式調用。
1.結構體中重載<
#include <iostream>
#include <string>
#include <map>
using namespace std;
struct StructTest
{
string sTemp;
int nCount;
bool operator<(const StructTest& test) const
{
if (sTemp < test.sTemp)
{
return true;
}
else if (sTemp == test.sTemp)
{
if (nCount < test.nCount)
return true;
else
return false;
}
else
{
return false;
}
}
};
void main()
{
map<StructTest,string>mapTest;
map<StructTest,string>::iterator mapTestiter;
StructTest StructTest1,StructTest2,StructTest3;
StructTest1.sTemp="111111";
StructTest1.nCount=6;
StructTest2.sTemp="111111";
StructTest2.nCount=7;
StructTest3.sTemp="000000";
StructTest3.nCount=6;
mapTest.insert(make_pair(StructTest1,"1"));
mapTest.insert(make_pair(StructTest2,"2"));
mapTest.insert(make_pair(StructTest3,"3"));
for (mapTestiter=mapTest.begin();mapTestiter!=mapTest.end();mapTestiter++)
{
cout<<(mapTestiter->first).sTemp<<" "<<(mapTestiter->first).nCount<<" "<<mapTestiter->second<<endl;
}
}
#include <iostream>
#include <string>
#include <map>
using namespace std;
struct StructTest
{
string sTemp;
int nCount;
};
struct ptr_less : public binary_function<StructTest,StructTest,bool>
{
bool operator()(const StructTest& test1, const StructTest& test2) const
{
if (test1.sTemp < test2.sTemp)
{
return true;
}
else if (test1.sTemp == test2.sTemp)
{
if (test1.nCount < test2.nCount)
return true;
else
return false;
}
else
{
return false;
}
}
};
void main()
{
map<StructTest,string,ptr_less>mapTest;
map<StructTest,string,ptr_less>::iterator mapTestiter;
StructTest StructTest1,StructTest2,StructTest3;
StructTest1.sTemp="111111";
StructTest1.nCount=6;
StructTest2.sTemp="111111";
StructTest2.nCount=7;
StructTest3.sTemp="000000";
StructTest3.nCount=6;
mapTest.insert(make_pair(StructTest1,"1"));
mapTest.insert(make_pair(StructTest2,"2"));
mapTest.insert(make_pair(StructTest3,"3"));
for (mapTestiter=mapTest.begin();mapTestiter!=mapTest.end();mapTestiter++)
{
cout<<(mapTestiter->first).sTemp<<" "<<(mapTestiter->first).nCount<<" "<<mapTestiter->second<<endl;
}
}
當然其中的find方法也與_Pr有關。
map中find調用紅黑樹的find
具體調用如下：1.map中的find
2.紅黑樹中find
注意：STL中的SET與map一樣。
具體調用可以查看STL源碼剖析、或者vs中查看相關定義
