STL map、set中key為結構體的用法，stlmap

STL map、set中key為結構體的用法，stlmap

下面是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中查看相關定義