map.svn-base

ffshow源码

		__base_map<Key, T, Compare, Allocator>::lower_bound(const key_type &x)
	{
		size_type low  = 0;
		size_type high = data.size();

		while (low < high) {
			size_type i = (low + high) / 2;
			if( c(data[i].first, x) ){
				low = i + 1;
			}else{
				high = i;
			}
		}

		return iterator(low, this);
	}

	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::const_iterator
		__base_map<Key, T, Compare, Allocator>::lower_bound(const key_type &x) const
	{
		size_type low  = 0;
		size_type high = data.size();

		while (low < high) {
			size_type i = (low + high) / 2;
			if( c(data[i].first, x) ){
				low = i + 1;
			}else{
				high = i;
			}
		}

		return const_iterator(low, this);
	}

	template <class Key, class T, class Compare, class Allocator>
		void __base_map<Key, T, Compare, Allocator>::swap(__base_map<Key,T,Compare,Allocator>& m)
	{
		Compare n = c;
		c = m.c;
		m.c = n;

		data.swap(m.data);
	}


	template <class Key, class T, class Compare, class Allocator>
		void __base_map<Key, T, Compare, Allocator>::clear()
	{
		data.clear();
	}


	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::key_compare
		__base_map<Key, T, Compare, Allocator>::key_comp() const
	{
		return c;
	}

//	value_compare value_comp() const;





/* This is the implementation for the map container.  As noted above, it deviates
 * from ISO spec by deriving from a base class in order to reduce code redundancy.
 * More code could be reduced by convirting to virtual functions (thus allowing
 * much of the erase and insert code to be duplicated), but that would deviate from
 * the specifications too much to be worth the risk.
 */





//Implementation of map


template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT map
	: 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;

	using base::value_compare;

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

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

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

	map<Key,T,Compare,Allocator>& operator=(const map<Key,T,Compare,Allocator>& x)
	 {
		if( &x == this){
			return *this;
		}
		c = x.c;
		data = x.data;
		return *this;
	 }

	reference operator[](const key_type& k);

	pair<iterator, bool> 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>
		map<Key, T, Compare, Allocator>::
		map(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 map<Key, T, Compare, Allocator>::reference
		map<Key, T, Compare, Allocator>::operator[](const key_type & k)
	{
/*		iterator i = lower_bound(k);
		if( !c( i->first, k) && !c(k, i->first) ){
			return i->second;
		}
		pair<Key, T> t;
		t.first = k;
		t.second = T();
		return insert(t).first->second;
*/
		//This is from the spec and is quite ugly.
		return (*((insert(make_pair(k, T()))).first)).second;
	}

	template <class Key, class T, class Compare, class Allocator>
		pair<typename map<Key, T, Compare, Allocator>::iterator, bool>
		map<Key, T, Compare, Allocator>::insert(const value_type& x)
	{
		pair<typename map<Key, T, Compare, Allocator>::iterator, bool> 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);
			retval.first = begin();
			retval.second = true;
			return retval;
		}

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

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

		//No match - this should never happen
		if(retval.first == end()){
			retval.second = false;
			return retval;
		}
		
		//If we have an exact match
		if( !c( retval.first->first, x.first) && !c(x.first, retval.first->first ) ){
			retval.second = false;
			return retval;
		}

		typename deque<pair<Key, T>, allocator<pair<Key, T> > >::iterator q(&data, retval.first.element);
		data.insert(q, x);

		retval.first = __base_map<Key, T, Compare, Allocator>::lower_bound(x.first);   //Need to refind because insert can move data around
		retval.second = true;

		return retval;
	}


	template <class Key, class T, class Compare, class Allocator>
		typename map<Key, T, Compare, Allocator>::iterator
		map<Key, T, Compare, Allocator>::insert(iterator position, const value_type& x)
	{
		//Just reusing code.  It's hard to make improvements over existing algo.
		insert(x);
		return find(x.first);
	}

	template <class Key, class T, class Compare, class Allocator>
		template <class InputIterator> void 
		map<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 
		map<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 map<Key, T, Compare, Allocator>::size_type
		map<Key, T, Compare, Allocator>::erase(const key_type& x)
	{
		typename map<Key, T, Compare, Allocator>::iterator i = find(x);
		if(i!=end()){
			erase(i);
			return 1;
		}
		return 0;
	}

	template <class Key, class T, class Compare, class Allocator>
		void map<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 map<Key, T, Compare, Allocator>::iterator
		map<Key, T, Compare, Allocator>::
		find(const typename map<Key, T, Compare, Allocator>::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;
		}

                //Make sure we have an exact match....
                if(!c( retval->first, x) && !c(x, retval->first )){
                        return retval;
                }
                return end();

	}

	template <class Key, class T, class Compare, class Allocator>
		typename map<Key, T, Compare, Allocator>::const_iterator
		map<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;
		}

                //Make sure we have an exact match....
                if(!c( retval->first, x) && !c(x, retval->first )){
                        return retval;
                }
                return end();

	}

	template <class Key, class T, class Compare, class Allocator>
		typename map<Key, T, Compare, Allocator>::size_type
		map<Key, T, Compare, Allocator>::count(const typename map<Key, T, Compare, Allocator>::key_type& x) const
	{
		if( find(x) == end()){
			return 0;
		}
		return 1;
	}

	template <class Key, class T, class Compare, class Allocator>
		typename map<Key, T, Compare, Allocator>::iterator 
		map<Key, T, Compare, Allocator>::upper_bound(const key_type& x)
	{
		typename map<Key, T, Compare, Allocator>::iterator i = __base_map<Key, T, Compare, Allocator>::lower_bound(x);
		if( i != end() && !c(x, i->first) ){
			++i;
		}
		return i;
	}

	template <class Key, class T, class Compare, class Allocator>
		typename map<Key, T, Compare, Allocator>::const_iterator
		map<Key, T, Compare, Allocator>::upper_bound(const key_type& x) const
	{
		typename map<Key, T, Compare, Allocator>::const_iterator i = __base_map<Key, T, Compare, Allocator>::lower_bound(x);
		if(i != end() && !c(x, i->first)){
			++i;
		}
		return i;
	}


	template <class Key, class T, class Compare, class Allocator>
		pair<	typename map<Key, T, Compare, Allocator>::iterator,
			typename map<Key, T, Compare, Allocator>::iterator
		> map<Key, T, Compare, Allocator>::equal_range(const key_type& x)
	{
		pair<   typename map<Key, T, Compare, Allocator>::iterator,
                        typename map<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 map<Key, T, Compare, Allocator>::const_iterator,
			typename map<Key, T, Compare, Allocator>::const_iterator