typedef ... key_type;

• if we are dealing with a map, then simply the key type
• if we are dealing with a set, then the indirected key type, that is, given ptr_set<T>, key_type* will be T*.

typedef ... key_compare;

• comparison object type that determines the order of elements in the container

typedef ... value_compare;

• comparison object type that determines the order of elements in the container
• if we are dealing with a map, then this comparison simply forwards to the key_compare comparison operation

key_compare key_comp() const;

value_compare value_comp() const;

• returns copies of objects used to determine the order of elements

template< typename InputIterator > void insert( InputIterator first, InputIterator last );

• Requirements: [first,last) is a valid range
• Effects: Inserts a cloned range
• Exception safety: Basic guarantee

template< class InputRange > void insert( const InputRange& r );

• Effects: insert( boost::begin(r), boost::end(r) );

void erase( iterator position );

• Requirements: position is a valid iterator from the container
• Effects: Removes the element defined by position.
• Throws: Nothing

size_type erase( const key_type& x );

• Effects: Removes all the elements in the container with a key equivalent to x and returns the number of erased elements.
• Throws: Nothing

void erase( iterator first, iterator last );

• Requirements: [first,last) is a valid range
• Effects: Removes the range of elements defined by [first,last).
• Throws: Nothing

template< class Range > void erase( const Range& r );

• Effects: erase( boost::begin(r), boost::end(r) );

iterator       find( const Key& x );

const_iterator find( const Key& x ) const;

• Effects: Searches for the key and returns end() on failure.
• Complexity: Logarithmic

size_type count( const Key& x ) const;

• Effects: Counts the elements with a key equivalent to x
• Complexity: Logarithmic

iterator       lower_bound( const Key& x );

const_iterator lower_bound( const Key& x ) const;

• Effects: Returns an iterator pointing to the first element with a key not less than x
• Complexity: Logarithmic

iterator       upper_bound( const Key& x );

const_iterator upper_bound( const Key& x ) const;

• Effects: Returns an iterator pointing to the first element with a key greater than x
• Complexity: Logarithmic

iterator_range<iterator>       equal_range( const Key& x );

iterator_range<const_iterator> equal_range( const Key& x ) const;

• Effects: return boost::make_iterator_range( lower_bound( x ), upper_bound( x ) );
• Complexity: Logarithmic