map

mpeg4 video codec mpeg4 video codec

	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>
		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>::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. end() for error.
		 */

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

		//Before the first element
		if( c(x, data[0].first) ){
			return begin();
		}


		//Element is larger than all known elemenst
		if( c( data[data.size()-1].first, x) ){
			return end();
		}

		//Or if it is the last element
		if( !c(x, data[size()-1].first) ){
			return iterator(data.size()-1, this);
		}

		size_type low;
		size_type high;
		size_type i=0;

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

		//This algorithm will accept duplicates in keys

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

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

		return iterator(i, this);
	}

	template <class Key, class T, class Compare, class Allocator>
		typename multimap<Key, T, Compare, Allocator>::const_iterator
		multimap<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. end() for error.
		 */

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

		//Before the first element
		if( c(x, data[0].first) ){
			return begin();
		}


		//Element is larger than all known elemenst
		if( c( data[data.size()-1].first, x) ){
			return end();
		}

		//Or if it is the last element
		if( !c(x, data[size()-1].first) ){
			return const_iterator(data.size()-1, this);
		}

		size_type low;
		size_type high;
		size_type i=0;

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

		//This algorithm will accept duplicates in keys

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

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

		return const_iterator(i, this);
	}


	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 = ifind(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 = 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 = ifind(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 = ifind(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>::lower_bound(const key_type& x)
	{
		typename multimap<Key, T, Compare, Allocator>::iterator i = find(x);
/*		if(i == end()){
			return i;
		}
		while( i.element > 0 && !c(i->first, x) && !c(x, i->first) ){
			--i;
		}
		if( c(i->first, x)){
			++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>::lower_bound(const key_type& x) const
	{
		//FIXME - linear search - can we do any better?
		typename multimap<Key, T, Compare, Allocator>::const_iterator i = find(x);
/*		if(i == end()){
			return i;
		}
		while( i.element >0 && !c(i->first, x) && !c(x, i->first) ){
			--i;
		}
		if( c(i->first, x)){
			++i;
		}
*/		return i;
	}

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