看一下bits/stl_map和bits/stl_set可以看到map和set的定义如下:
84 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 85typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 86class map 87{ 88public: 89typedef _Keykey_type; 90typedef _Tpmapped_type; 91typedef std::pair<const _Key, _Tp>value_type; 92typedef _Comparekey_compare; 93typedef _Allocallocator_type; 94 95private: 96// concept requirements 97typedef typename _Alloc::value_type_Alloc_value_type; 98__glibcxx_class_requires(_Tp, _SGIAssignableConcept) 99__glibcxx_class_requires4(_Compare, bool, _Key, _Key,100_BinaryFunctionConcept)101__glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)102 103public:104class value_compare105: public std::binary_function<value_type, value_type, bool>106{107friend class map<_Key, _Tp, _Compare, _Alloc>;108protected:109_Compare comp;110 111value_compare(_Compare __c)112: comp(__c) { }113 114public:115bool operator()(const value_type& __x, const value_type& __y) const116{ return comp(__x.first, __y.first); }117};118 119private:120/// This turns a red-black tree into a [multi]map. 121typedef typename _Alloc::template rebind<value_type>::other122_Pair_alloc_type;123 124typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,125key_compare, _Pair_alloc_type> _Rep_type;126 127/// The actual tree structure.128_Rep_type _M_t;
85 template<typename _Key, typename _Compare = std::less<_Key>, 86typename _Alloc = std::allocator<_Key> > 87class set 88{ 89// concept requirements 90typedef typename _Alloc::value_type_Alloc_value_type; 91__glibcxx_class_requires(_Key, _SGIAssignableConcept) 92__glibcxx_class_requires4(_Compare, bool, _Key, _Key, 93_BinaryFunctionConcept) 94__glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) 95 96public: 97// typedefs: 98//@{ 99/// Public typedefs.100typedef _Keykey_type;101typedef _Keyvalue_type;102typedef _Compare key_compare;103typedef _Compare value_compare;104typedef _Alloc allocator_type;105//@}106 107private:108typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;109 110typedef _Rb_tree<key_type, value_type, _Identity<value_type>,111key_compare, _Key_alloc_type> _Rep_type;112_Rep_type _M_t; // Red-black tree representing set.113
由于map,set的本身定义都是声明任何成员变量,所有成员变量都是从_Rb_tree继承过来的,唯一的差别只是_Rb_tree最后参数的定义不一样.
set的特征如下:
1.set对象有五个成员_M_node_count标明map有多少个元素，三个指针分别指向树中最左的节点,树的根节点,树的最右节点，_M_color表明是红树还是黑树，，_M_key_compare指向比较函数
2.树的根节点的_M_parent指向头节点
3.每一个节点的值都紧跟着_M_right
看一下例子:
1 #include <set> 2 3 int main() 4 { 5std::set<int> iSet; 6iSet.insert( 0x523 ); 7iSet.insert( 0x352 ); 8iSet.insert( 0x808 ); 9 10return 0; 11 }
看一下main函数的汇编:
(gdb) disassemble mainDump of assembler code for function main: 0x08048634 <+0>:lea 0x4(%esp),%ecx 0x08048638 <+4>:and $0xfffffff0,%esp 0x0804863b <+7>:pushl -0x4(%ecx) 0x0804863e <+10>:push %ebp 0x0804863f <+11>:mov %esp,%ebp 0x08048641 <+13>:push %esi 0x08048642 <+14>:push %ebx 0x08048643 <+15>:push %ecx 0x08048644 <+16>:sub $0x5c,%esp 0x08048647 <+19>:lea -0x54(%ebp),%eax 0x0804864a <+22>:mov %eax,(%esp) 0x0804864d <+25>:call 0x8048712 <_ZNSt3setIiSt4lessIiESaIiEEC2Ev> 0x08048652 <+30>:movl $0x523,-0x34(%ebp) 0x08048659 <+37>:lea -0x3c(%ebp),%eax 0x0804865c <+40>:lea -0x34(%ebp),%edx 0x0804865f <+43>:mov %edx,0x8(%esp) 0x08048663 <+47>:lea -0x54(%ebp),%edx 0x08048666 <+50>:mov %edx,0x4(%esp) 0x0804866a <+54>:mov %eax,(%esp) 0x0804866d <+57>:call 0x804878c <_ZNSt3setIiSt4lessIiESaIiEE6insertERKi> 0x08048672 <+62>:sub $0x4,%esp 0x08048675 <+65>:movl $0x352,-0x28(%ebp) 0x0804867c <+72>:lea -0x30(%ebp),%eax—Type <return> to continue, or q <return> to quit— 0x0804867f <+75>:lea -0x28(%ebp),%edx 0x08048682 <+78>:mov %edx,0x8(%esp) 0x08048686 <+82>:lea -0x54(%ebp),%edx 0x08048689 <+85>:mov %edx,0x4(%esp) 0x0804868d <+89>:mov %eax,(%esp) 0x08048690 <+92>:call 0x804878c <_ZNSt3setIiSt4lessIiESaIiEE6insertERKi> 0x08048695 <+97>:sub $0x4,%esp 0x08048698 <+100>:movl $0x808,-0x1c(%ebp) 0x0804869f <+107>:lea -0x24(%ebp),%eax 0x080486a2 <+110>:lea -0x1c(%ebp),%edx 0x080486a5 <+113>:mov %edx,0x8(%esp) 0x080486a9 <+117>:lea -0x54(%ebp),%edx 0x080486ac <+120>:mov %edx,0x4(%esp) 0x080486b0 <+124>:mov %eax,(%esp) 0x080486b3 <+127>:call 0x804878c <_ZNSt3setIiSt4lessIiESaIiEE6insertERKi> 0x080486b8 <+132>:sub $0x4,%esp 0x080486bb <+135>:mov $0x0,%ebx 0x080486c0 <+140>:lea -0x54(%ebp),%eax 0x080486c3 <+143>:mov %eax,(%esp) 0x080486c6 <+146>:call 0x80486fe <_ZNSt3setIiSt4lessIiESaIiEED2Ev> 0x080486cb <+151>:mov %ebx,%eax 0x080486cd <+153>:lea -0xc(%ebp),%esp 0x080486d0 <+156>:add $0x0,%esp—Type <return> to continue, or q <return> to quit— 0x080486d3 <+159>:pop %ecx 0x080486d4 <+160>:pop %ebx 0x080486d5 <+161>:pop %esi 0x080486d6 <+162>:pop %ebp 0x080486d7 <+163>:lea -0x4(%ecx),%esp 0x080486da <+166>:ret0x080486db <+167>:mov %edx,%ebx 0x080486dd <+169>:mov %eax,%esi 0x080486df <+171>:lea -0x54(%ebp),%eax 0x080486e2 <+174>:mov %eax,(%esp) 0x080486e5 <+177>:call 0x80486fe <_ZNSt3setIiSt4lessIiESaIiEED2Ev> 0x080486ea <+182>:mov %esi,%eax 0x080486ec <+184>:mov %ebx,%edx 0x080486ee <+186>:mov %eax,(%esp) 0x080486f1 <+189>:call 0x8048564 <_Unwind_Resume@plt>End of assembler dump.
由上面汇编可知,ebp-0x54是set的this指针.
玩坏了可以选择重来，
