STL — 从源码层面区别map set和multiset multimap

Love The Way You Lie 2022-06-03 07:49 177阅读 0赞

# 从源码层面区别map set和multiset multimap #

set特性为所有元素都会根据元素的键值自动被排序. set的元素不想map那样可以同时拥有实值(value)和键值(key).set元素的键值就是

实值，实值就 是 键值.set不允许两个元素有相同的键值. multiset的特性以及用法和set完全相同，唯一的差别在于它允许键值重复，因

此它的插入操作采用的是底 层机 制RE\_tree的insert\_equal()而非insert\_unique()

map的特性为，所有元素都会根据元素的键值自动被排序. map的所有元素都为pair，同时拥有实值(value)和键值(key). pair的第一元

素被视为键值， 第二元素视为实值.  multimap的特性以及用法和map完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用

的是底层机 制RE\_tree的 insert\_equal()而非insert\_unique() 我们使用map来举个例子，我们来看看它和multimap之间的区别.

首先我们从RB\_tree源代码中找到insert\_equal()<允许重复插入键值>和insert\_unique()<不允许插入有相同的键值>

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
    typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
    rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value& v)
    {
      link_type y = header;
      link_type x = root();
      while (x != 0) {
        y = x;
        x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
      }
      return __insert(x, y, v);
    }
    
    
    template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
    pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
    rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v)
    {
      link_type y = header;
      link_type x = root();
      bool comp = true;
      while (x != 0) {
        y = x;
        comp = key_compare(KeyOfValue()(v), key(x));
        x = comp ? left(x) : right(x);
      }
      iterator j = iterator(y);   
      if (comp)
        if (j == begin())     
          return pair<iterator,bool>(__insert(x, y, v), true);
        else
          --j;
      if (key_compare(key(j.node), KeyOfValue()(v)))
        return pair<iterator,bool>(__insert(x, y, v), true);
      return pair<iterator,bool>(j, false);
    }

map源代码摘要:

template <class Key, class T, class Compare, class Alloc = alloc>
    #endif
    class map {
    public:
    
    	// typedefs:
    
    	typedef Key key_type;
    	typedef T data_type;
    	typedef T mapped_type;
    	typedef pair<const Key, T> value_type;
    	typedef Compare key_compare;
    
    	class value_compare
    		: public binary_function<value_type, value_type, bool> {
    		friend class map<Key, T, 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);
    		}
    	};
    	.
    		.
    		.
    		template <class InputIterator>
    	map(InputIterator first, InputIterator last)
    		: t(Compare()) {
    		t.insert_unique(first, last);
    	}
    
    	template <class InputIterator>
    	map(InputIterator first, InputIterator last, const Compare& comp)
    		: t(comp) {
    		t.insert_unique(first, last);
    	}
    #else
    map(const value_type* first, const value_type* last)
    : t(Compare()) {
    	t.insert_unique(first, last);
    }
    map(const value_type* first, const value_type* last, const Compare& comp)
    : t(comp) {
    	t.insert_unique(first, last);
    }
    
    map(const_iterator first, const_iterator last)
    : t(Compare()) {
    	t.insert_unique(first, last);
    }
    map(const_iterator first, const_iterator last, const Compare& comp)
    : t(comp) {
    	t.insert_unique(first, last);
    }
    
    pair<iterator, bool> insert(const value_type& x) { return t.insert_unique(x); }
    iterator insert(iterator position, const value_type& x) {
    	return t.insert_unique(position, x);
    }
    #ifdef __STL_MEMBER_TEMPLATES
    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
    	t.insert_unique(first, last);
    }
    #else
    void insert(const value_type* first, const value_type* last) {
    	t.insert_unique(first, last);
    }
    void insert(const_iterator first, const_iterator last) {
    	t.insert_unique(first, last);
    }
    }

multimap源代码:

template <class Key, class T, class Compare, class Alloc = alloc>
    #endif
    class multimap {
    public:
    
    	// typedefs:
    
    	typedef Key key_type;
    	typedef T data_type;
    	typedef T mapped_type;
    	typedef pair<const Key, T> value_type;
    	typedef Compare key_compare;
    
    	class value_compare : public binary_function<value_type, value_type, bool> {
    		friend class multimap<Key, T, 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);
    		}
    	};
    
    	.
    		.
    		.
    #ifdef __STL_MEMBER_TEMPLATES  
    		template <class InputIterator>
    	multimap(InputIterator first, InputIterator last)
    		: t(Compare()) {
    		t.insert_equal(first, last);
    	}
    
    	template <class InputIterator>
    	multimap(InputIterator first, InputIterator last, const Compare& comp)
    		: t(comp) {
    		t.insert_equal(first, last);
    	}
    #else
    		multimap(const value_type* first, const value_type* last)
    		: t(Compare()) {
    			t.insert_equal(first, last);
    		}
    	multimap(const value_type* first, const value_type* last,
    		const Compare& comp)
    		: t(comp) {
    		t.insert_equal(first, last);
    	}
    
    	multimap(const_iterator first, const_iterator last)
    		: t(Compare()) {
    		t.insert_equal(first, last);
    	}
    	multimap(const_iterator first, const_iterator last, const Compare& comp)
    		: t(comp) {
    		t.insert_equal(first, last);
    	}
    
    	iterator insert(const value_type& x) { return t.insert_equal(x); }
    	iterator insert(iterator position, const value_type& x) {
    		return t.insert_equal(position, x);
    	}
    #ifdef __STL_MEMBER_TEMPLATES  
    	template <class InputIterator>
    	void insert(InputIterator first, InputIterator last) {
    		t.insert_equal(first, last);
    	}
    #else
    	void insert(const value_type* first, const value_type* last) {
    		t.insert_equal(first, last);
    	}
    	void insert(const_iterator first, const_iterator last) {
    		t.insert_equal(first, last);
    	}
    
    }

大家比较一下就可以得出结论了！ ！ ！ ！ 关于map和set是不同的参数内容 为什么还可以共用同一个RB\_Tree代码可以看看这个博客:

[map set简易的结构实现][map set]

[map set]: http://blog.csdn.net/dawn_sf/article/details/78506299