map

mpeg4 video codec mpeg4 video codec

	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       lower_bound(const key_type& x);
	const_iterator lower_bound(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;

	iterator ifind(const key_type& x);      //Core find functionality
	const_iterator ifind(const key_type& x) const;      //Core find functionality

	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>::iterator
		map<Key, T, Compare, Allocator>::ifind(const key_type &x)
	{
		/* This function is not from the standard. It is an internal
		 * utility function which returns an iterator to either the
		 * first matching element, or to the element before which
		 * an insert should be performed.  Will not indicate if the
		 *insert should be performed before the first element
		 */

		if(data.size() == 0){
			return end();
		}

		if(data.size() == 1){
			if(  c(data[0].first, x) ){
				return end();
			}
			return begin();
		}

		size_type low;
		size_type high;
		size_type i;

		low = 0;
		high = data.size() - 1;

		//This algorithm assumes no duplicates in stored information
		while(( high - low) > 1){
			i = low + ((high - low) /2);
			if( c(x, data[i].first) ){
				high = i;
			}else{
				low = i;
			}
		}

		if( c(data[low].first, x) ){         // k >=high
			i = high;
		}else{
			i = low;
		}

		return iterator(i, this);
	}

	template <class Key, class T, class Compare, class Allocator>
		typename map<Key, T, Compare, Allocator>::const_iterator
		map<Key, T, Compare, Allocator>::ifind(const key_type &x) const
	{
		/* This function is not from the standard. It is an internal
		 * utility function which returns an iterator to either the
		 * first matching element, or to the element before which
		 * an insert should be performed.  Will not indicate if the
		 *insert should be performed before the first element
		 */

		if(data.size() == 0){
			return end();
		}

		if(data.size() == 1){
			if( c(data[0].first, x) ){
				return end();
			}
			return begin();
		}

		size_type low;
		size_type high;
		size_type i;

		low = 0;
		high = data.size() - 1;

		//This algorithm assumes no duplicates in stored information
		while(( high - low) > 1){
			i = low + ((high - low) /2);
			if( c(x, data[i].first) ){
				high = i;
			}else{
				low = i;
			}
		}

		if( c(data[low].first, x) ){         // k >=high
			i = high;
		}else{
			i = low;
		}

		return const_iterator(i, this);
	}


	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 = ifind(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 = ifind(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 = ifind(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 = ifind(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 = ifind(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>::lower_bound(const key_type& x)
	{
		return ifind(x);
	}

	template <class Key, class T, class Compare, class Allocator>
		typename map<Key, T, Compare, Allocator>::const_iterator
		map<Key, T, Compare, Allocator>::lower_bound(const key_type& x) const
	{
		return ifind(x);
	}

	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 = ifind(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 = ifind(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 = 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
		> 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 = 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;