map.svn-base

ffshow源码

		> map<Key, T, Compare, Allocator>::equal_range(const key_type& x) const
	{
		pair<   typename map<Key, T, Compare, Allocator>::const_iterator,
                        typename map<Key, T, Compare, Allocator>::const_iterator
                > retval;
		retval.first = __base_map<Key, T, Compare, Allocator>::lower_bound(x);
		retval.second = upper_bound(x);
		return retval;		
	}

	template <class Key, class T, class Compare, class Allocator> bool operator==
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y)
	{
		if(x.c == y.c && x.data = y.data){
			return true;
		}
		return false;
	}



//Implementation of multimap


template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT multimap
	: public __base_map<Key, T, Compare, Allocator>
{
		//Default value of allocator does not meet C++ standard specs, but it works for this library
		//Deal with it
public:

	typedef	__base_map<Key, T, Compare, Allocator>		base;
	typedef typename base::key_type				key_type;
	typedef typename base::mapped_type			mapped_type;
	typedef typename base::value_type			value_type;
	typedef typename base::key_compare			key_compare;
	typedef typename base::allocator_type			allocator_type;
	typedef typename base::reference			reference;
	typedef typename base::const_reference			const_reference;
	typedef typename base::iterator				iterator;
	typedef typename base::const_iterator			const_iterator;
	typedef typename base::size_type			size_type;
	typedef typename base::difference_type			difference_type;
	typedef typename base::pointer				pointer;
	typedef typename base::const_pointer			const_pointer;
	typedef typename base::reverse_iterator			reverse_iterator;
	typedef typename base::const_reverse_iterator		const_reverse_iterator;

	explicit multimap(const Compare& comp = Compare(), const Allocator& al = Allocator())
		: base(comp, al) {  }

	template <class InputIterator> multimap(InputIterator first, InputIterator last,
		const Compare& comp = Compare(), const Allocator& = Allocator());

	multimap(const multimap<Key,T,Compare,Allocator>& x) : base(x) {  }
	~multimap() {  }

	multimap<Key,T,Compare,Allocator>& operator=(const multimap<Key,T,Compare,Allocator>& x);

	iterator insert(const value_type& x);
	iterator insert(iterator position, const value_type& x);
	template <class InputIterator> void insert(InputIterator first, InputIterator last);

	void      erase(iterator position);
	size_type erase(const key_type& x);
	void      erase(iterator first, iterator last);

	using base::begin;
	using base::end;
	using base::rbegin;
	using base::rend;

	using base::empty;
	using base::size;
	using base::max_size;

	iterator       find(const key_type& x);
	const_iterator find(const key_type& x) const;
	size_type      count(const key_type& x) const;
	iterator       upper_bound(const key_type& x);
	const_iterator upper_bound(const key_type& x) const;
	pair<iterator,iterator>             equal_range(const key_type& x);
	pair<const_iterator,const_iterator> equal_range(const key_type& x) const;

protected:
	//friend class base::iterator;
	//friend class base::const_iterator;

	using base::data;
	using base::c;

};



	template <class Key, class T, class Compare, class Allocator> template <class InputIterator>
		multimap<Key, T, Compare, Allocator>::
		multimap(InputIterator first, InputIterator last, const Compare& comp, const Allocator& al)
		: base(comp, al)
	{
		while(first !=last){
			insert(*first);
			++first;
		}
	}


	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::iterator
		multimap<Key, T, Compare, Allocator>::insert(const value_type &x)
	{
		iterator retval;

		//Either set is empty or element to insert goes at the begining
		if(data.size() == 0 || c(x.first, data[0].first) ){
			data.push_front(x);
			return begin();
		}

		//Element to insert goes at the end
		if( c(data[data.size() - 1].first, x.first) ){
			data.push_back(x);
			return end();
                }

		retval = __base_map<Key, T, Compare, Allocator>::lower_bound(x.first);

		//No match - this should never happen
		if(retval == end()){
			return retval;
		}

		if( !c(x.first, retval->first) ){
			++retval;
		}
		
		typename deque<pair<Key, T>, allocator<pair<Key, T> > >::iterator q(&data, retval.element);
		data.insert(q, x);

		return retval;
	}


	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::iterator 
		multimap<Key, T, Compare, Allocator>::insert(iterator position, const value_type& x)
	{

		//Inserting at begining
		if(position == begin() && !c(position->first, x.first) ){
			data.push_front(x);
			return position;
		}
		//Inserting at end
		if(position == end() && !c(x.first, data[data.size() - 1].first) ){
			data.push_back(x);
			return position;
		}

		//Inserting in middle
		iterator temp = position;
		--temp;
		if( !c(position->first, x.first) && !c(x.first, temp->first) ){
			typename deque<pair<Key, T>, allocator<pair<Key, T> > >::iterator q(&data, position.element);
			data.insert(q, x);
			return position;
		}

		return insert(x);
	}

	template <class Key, class T, class Compare, class Allocator>
		template <class InputIterator> void 
		multimap<Key, T, Compare, Allocator>::insert(InputIterator first, InputIterator last)
	{
		while(first !=last){
			insert(*first);
			++first;
		}
	}



	template <class Key, class T, class Compare, class Allocator> void 
		multimap<Key, T, Compare, Allocator>::erase(iterator position)
	{
		//Create a deque iterator from position information and then
		//Use built in erase feature because it is handy.
		typename deque<pair<Key, T>, allocator<pair<Key, T> > >::iterator pos(&data, position.element);
		data.erase(pos);		
	}

	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::size_type
		multimap<Key, T, Compare, Allocator>::erase(const key_type& x)
	{
		typename multimap<Key, T, Compare, Allocator>::iterator f = __base_map<Key, T, Compare, Allocator>::lower_bound(x);
		typename multimap<Key, T, Compare, Allocator>::iterator l = upper_bound(x);
		size_type t = l.element - f.element;
		erase(f, l);
		return t;
	}



	template <class Key, class T, class Compare, class Allocator>
		void multimap<Key, T, Compare, Allocator>::erase(iterator first, iterator last)
	{
		typename deque<pair<Key, T>, allocator<pair<Key, T> > >::iterator f(&data, first.element);
		typename deque<pair<Key, T>, allocator<pair<Key, T> > >::iterator l(&data, last.element);
		data.erase(f, l);
	}


	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::iterator 
		multimap<Key, T, Compare, Allocator>::find(const key_type& x)
	{
		if(data.size() == 0){
			return end();
		}

		iterator retval = __base_map<Key, T, Compare, Allocator>::lower_bound(x);

		if(retval == end()){
			return retval;
		}

		if( c(x, retval->first) || c(retval->first, x) ){
			return end();
		}

		while( retval.element > 0 && !c(retval->first, x) && !c(x, retval->first) ){
			--retval;
		}
		if( c(retval->first, x)){
			++retval;
		}

		return retval;
	}


	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::const_iterator
		multimap<Key, T, Compare, Allocator>::find(const key_type& x) const
	{
		if(data.size() == 0){
			return end();
		}
		const_iterator retval = __base_map<Key, T, Compare, Allocator>::lower_bound(x);

		if(retval == end()){
			return retval;
		}

		if( c(x, retval->first) || c(retval->first, x) ){
			return end();
		}

		while( retval.element > 0 && !c(retval->first, x) && !c(x, retval->first) ){
			--retval;
		}
		if( c(retval->first, x)){
			++retval;
		}


		return retval;
	}


	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::size_type
		multimap<Key, T, Compare, Allocator>::
		count(const typename multimap<Key, T, Compare, Allocator>::key_type& x) const
	{
		pair<   typename multimap<Key, T, Compare, Allocator>::const_iterator,
			typename multimap<Key, T, Compare, Allocator>::const_iterator
		> temp = equal_range(x);

		return temp.second.element - temp.first.element;
	}

	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::iterator
		multimap<Key, T, Compare, Allocator>::upper_bound(const key_type& x)
	{
		typename multimap<Key, T, Compare, Allocator>::iterator i = __base_map<Key, T, Compare, Allocator>::lower_bound(x);

		while(i != end() && !c(x, i->first)){
			++i;
		}
		return i;
	}

	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::const_iterator
		multimap<Key, T, Compare, Allocator>::upper_bound(const key_type& x) const
	{
		typename multimap<Key, T, Compare, Allocator>::const_iterator i = __base_map<Key, T, Compare, Allocator>::lower_bound(x);

		while(i != end() && !c(x, i->first)){
			++i;
		}
		return i;
	}


	template <class Key, class T, class Compare, class Allocator>
		pair<	typename multimap<Key, T, Compare, Allocator>::iterator,
			typename multimap<Key, T, Compare, Allocator>::iterator
		> multimap<Key, T, Compare, Allocator>::equal_range(const key_type& x)
	{
		pair<   typename multimap<Key, T, Compare, Allocator>::iterator,
                        typename multimap<Key, T, Compare, Allocator>::iterator
                > retval;
		retval.first = __base_map<Key, T, Compare, Allocator>::lower_bound(x);
		retval.second = upper_bound(x);
		return retval;		
	}

	template <class Key, class T, class Compare, class Allocator>
		pair<	typename multimap<Key, T, Compare, Allocator>::const_iterator,
			typename multimap<Key, T, Compare, Allocator>::const_iterator
		> multimap<Key, T, Compare, Allocator>::equal_range(const key_type& x) const
	{
		pair<   typename multimap<Key, T, Compare, Allocator>::const_iterator,
                        typename multimap<Key, T, Compare, Allocator>::const_iterator
                > retval;
		retval.first = __base_map<Key, T, Compare, Allocator>::lower_bound(x);
		retval.second = upper_bound(x);
		return retval;		
	}





/* Non-member functions.  These are at the end because they are not associated with any
   particular class.  These will be implemented as I figure out exactly what all of 
   them are supposed to do, and I have time.
 */

	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator< 
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator!=
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>=
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator<=
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT void swap
		(map<Key,T,Compare,Allocator>& x, map<Key,T,Compare,Allocator>& y);


	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator==
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator< 
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator!=
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator> 
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>=
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator<=
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT void swap
		(multimap<Key,T,Compare,Allocator>& x, multimap<Key,T,Compare,Allocator>& y);

}


#endif