<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                ### 前言 ? ? ? multimap的特性及其用法和map完全相同,唯一的區別就是multimap允許鍵值key重復,因此multimap的插入操作采用的是底層RB-Tree的insert_equal()而非insert_unique(),有關map容器的介紹前往博文《[關聯容器之map](http://blog.csdn.net/chenhanzhun/article/details/39529425)》。本文的源碼出自SGI STL中的<stl_multimap.h>文件。 ### multimap容器源碼剖析 ~~~ #ifndef __SGI_STL_INTERNAL_MULTIMAP_H #define __SGI_STL_INTERNAL_MULTIMAP_H #include <concept_checks.h> __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma set woff 1174 #pragma set woff 1375 #endif // Forward declaration of operators < and ==, needed for friend declaration. //multimap的特性及其用法和map完全相同,唯一的區別就是multimap允許鍵值key重復 //因此multimap的插入操作采用的是底層RB-Tree的insert_equal()而非insert_unique() //有關map容器的剖析見前面博文 //map內部元素根據鍵值key默認使用遞增排序less //用戶可自行制定比較類型 //內部維護的數據結構是紅黑樹, 具有非常優秀的最壞情況的時間復雜度 //注意:multimap允許元素重復,即鍵值和實值都可以重復,這點與map不同 template <class _Key, class _Tp, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>), class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class multimap; template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y); template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y); template <class _Key, class _Tp, class _Compare, class _Alloc> class multimap { // requirements: __STL_CLASS_REQUIRES(_Tp, _Assignable); __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); public: // typedefs: //下面的定義與map相同 typedef _Key key_type; typedef _Tp data_type; typedef _Tp mapped_type; typedef pair<const _Key, _Tp> value_type; typedef _Compare key_compare; //嵌套類,提供鍵值key比較函數接口 //繼承自<stl_function.h>中的binary_function /* template <class _Arg1, class _Arg2, class _Result> struct binary_function { typedef _Arg1 first_argument_type; typedef _Arg2 second_argument_type; typedef _Result result_type; }; */ class value_compare : public binary_function<value_type, value_type, bool> { friend class multimap<_Key,_Tp,_Compare,_Alloc>; protected: _Compare comp; value_compare(_Compare __c) : comp(__c) {} public: bool operator()(const value_type& __x, const value_type& __y) const { return comp(__x.first, __y.first); } }; private: //底層機制是RB-Tree typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, key_compare, _Alloc> _Rep_type; _Rep_type _M_t; // red-black tree representing multimap public: typedef typename _Rep_type::pointer pointer; typedef typename _Rep_type::const_pointer const_pointer; typedef typename _Rep_type::reference reference; typedef typename _Rep_type::const_reference const_reference; //map的迭代器不直接定義為const_iterator,而是分別定義iterator,const_iterator //是因為map的鍵值key不能被修改,因為必須遵守比較函數的排序規則,所以必須定義為const_iterator //而map的實值value可以被修改,則定義為iterator typedef typename _Rep_type::iterator iterator; typedef typename _Rep_type::const_iterator const_iterator; typedef typename _Rep_type::reverse_iterator reverse_iterator; typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; typedef typename _Rep_type::size_type size_type; typedef typename _Rep_type::difference_type difference_type; typedef typename _Rep_type::allocator_type allocator_type; // allocation/deallocation // 注意:multimap只能使用RB-tree的insert-equal(),不能使用insert-unique() /* 構造函數 multimap(); explicit multimap (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); template <class InputIterator> multimap (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); multimap (const multimap& x); */ multimap() : _M_t(_Compare(), allocator_type()) { } explicit multimap(const _Compare& __comp, const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) { } #ifdef __STL_MEMBER_TEMPLATES template <class _InputIterator> multimap(_InputIterator __first, _InputIterator __last) : _M_t(_Compare(), allocator_type()) { _M_t.insert_equal(__first, __last); } template <class _InputIterator> multimap(_InputIterator __first, _InputIterator __last, const _Compare& __comp, const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } #else multimap(const value_type* __first, const value_type* __last) : _M_t(_Compare(), allocator_type()) { _M_t.insert_equal(__first, __last); } multimap(const value_type* __first, const value_type* __last, const _Compare& __comp, const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } multimap(const_iterator __first, const_iterator __last) : _M_t(_Compare(), allocator_type()) { _M_t.insert_equal(__first, __last); } multimap(const_iterator __first, const_iterator __last, const _Compare& __comp, const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } #endif /* __STL_MEMBER_TEMPLATES */ //拷貝構造函數 multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { } //這里提供了operator=,即可以通過=初始化對象 multimap<_Key,_Tp,_Compare,_Alloc>& operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t = __x._M_t; return *this; } // accessors: //返回鍵值的比較函數,這里是調用RB-Tree的key_comp() key_compare key_comp() const { return _M_t.key_comp(); } //返回實值的比較函數 //這里調用的是map嵌套類中定義的比較函數 /* class value_compare : public binary_function<value_type, value_type, bool> { friend class map<_Key,_Tp,_Compare,_Alloc>; protected : _Compare comp; value_compare(_Compare __c) : comp(__c) {} public: bool operator()(const value_type& __x, const value_type& __y) const { return comp(__x.first, __y.first);//以鍵值調用比較函數 } */ //實際上最終還是調用鍵值key的比較函數,即他們是調用同一個比較函數 value_compare value_comp() const { return value_compare(_M_t.key_comp()); } allocator_type get_allocator() const { return _M_t.get_allocator(); } iterator begin() { return _M_t.begin(); } const_iterator begin() const { return _M_t.begin(); } iterator end() { return _M_t.end(); } const_iterator end() const { return _M_t.end(); } reverse_iterator rbegin() { return _M_t.rbegin(); } const_reverse_iterator rbegin() const { return _M_t.rbegin(); } reverse_iterator rend() { return _M_t.rend(); } const_reverse_iterator rend() const { return _M_t.rend(); } //判斷容器multimap是否為空 bool empty() const { return _M_t.empty(); } //返回容器multimap的大小 size_type size() const { return _M_t.size(); } size_type max_size() const { return _M_t.max_size(); } //交換multimap對象的內容 void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } // insert/erase /* multimap只能使用RB-tree的insert-equal() 插入元素 iterator insert (const value_type& val); iterator insert (iterator position, const value_type& val); template <class InputIterator> void insert (InputIterator first, InputIterator last); */ //插入元素節點,調用RB-Tree的insert-equal(); //插入元素的鍵值key允許重復 iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); } //在指定位置插入元素 iterator insert(iterator __position, const value_type& __x) { return _M_t.insert_equal(__position, __x); } #ifdef __STL_MEMBER_TEMPLATES //插入[first,last)元素 template <class _InputIterator> void insert(_InputIterator __first, _InputIterator __last) { _M_t.insert_equal(__first, __last); } #else void insert(const value_type* __first, const value_type* __last) { _M_t.insert_equal(__first, __last); } void insert(const_iterator __first, const_iterator __last) { _M_t.insert_equal(__first, __last); } #endif /* __STL_MEMBER_TEMPLATES */ /* 擦除元素 void erase (iterator position); size_type erase (const key_type& k); void erase (iterator first, iterator last); */ //在指定位置擦除元素 void erase(iterator __position) { _M_t.erase(__position); } //擦除指定鍵值的節點 size_type erase(const key_type& __x) { return _M_t.erase(__x); } //擦除指定區間的節點 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); } //清空容器 void clear() { _M_t.clear(); } // multimap operations: //查找指定鍵值的節點 iterator find(const key_type& __x) { return _M_t.find(__x); } const_iterator find(const key_type& __x) const { return _M_t.find(__x); } //計算指定鍵值元素的個數 size_type count(const key_type& __x) const { return _M_t.count(__x); } //Returns an iterator pointing to the first element in the container //whose key is not considered to go before k (i.e., either it is equivalent or goes after). //this->first is greater than or equivalent to __x. iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); } const_iterator lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } //Returns an iterator pointing to the first element that is greater than key. iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); } const_iterator upper_bound(const key_type& __x) const { return _M_t.upper_bound(__x); } //Returns the bounds of a range that includes all the elements in the container //which have a key equivalent to k //Because the elements in a map container have unique keys, //the range returned will contain a single element at most. pair<iterator,iterator> equal_range(const key_type& __x) { return _M_t.equal_range(__x); } pair<const_iterator,const_iterator> equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } //以下是操作符重載 #ifdef __STL_TEMPLATE_FRIENDS template <class _K1, class _T1, class _C1, class _A1> friend bool operator== (const multimap<_K1, _T1, _C1, _A1>&, const multimap<_K1, _T1, _C1, _A1>&); template <class _K1, class _T1, class _C1, class _A1> friend bool operator< (const multimap<_K1, _T1, _C1, _A1>&, const multimap<_K1, _T1, _C1, _A1>&); #else /* __STL_TEMPLATE_FRIENDS */ friend bool __STD_QUALIFIER operator== __STL_NULL_TMPL_ARGS (const multimap&, const multimap&); friend bool __STD_QUALIFIER operator< __STL_NULL_TMPL_ARGS (const multimap&, const multimap&); #endif /* __STL_TEMPLATE_FRIENDS */ }; template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { return __x._M_t == __y._M_t; } template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { return __x._M_t < __y._M_t; } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { return !(__x == __y); } template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { return __y < __x; } template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { return !(__y < __x); } template <class _Key, class _Tp, class _Compare, class _Alloc> inline bool operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { return !(__x < __y); } template <class _Key, class _Tp, class _Compare, class _Alloc> inline void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x, multimap<_Key,_Tp,_Compare,_Alloc>& __y) { __x.swap(__y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma reset woff 1174 #pragma reset woff 1375 #endif __STL_END_NAMESPACE #endif /* __SGI_STL_INTERNAL_MULTIMAP_H */ // Local Variables: // mode:C++ // End: ~~~ 參考資料: 《STL源碼剖析》侯捷
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看