📄 hash_map.html
字号:
<HTML><HEAD><TITLE><hash_map></TITLE></HEAD><BODY><H1><A NAME="<hash_map>"><CODE><hash_map></CODE></A></H1><HR><P>Include the <A HREF="index.html#STL">STL</A>standard header <B><CODE><hash_map></CODE></B> to define the<A HREF="lib_cont.html#Containers">container</A>template classes <CODE>hash_map</CODE> and<CODE>hash_multimap</CODE>, and their supportingtemplates.</P><PRE>namespace std {template<class Key, class Pr> class <B><A HREF="#hash_compare">hash_compare</A></B>;template<class Key, class Ty, class Tr, class Alloc> class <B><A HREF="#hash_map">hash_map</A></B>;template<class Key, class Ty, class Tr, class Alloc> class <B><A HREF="#hash_multimap">hash_multimap</A></B>; // TEMPLATE FUNCTIONStemplate<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator==">operator==</A></B>( const hash_map<Key, Ty, Tr, Alloc>& left, const hash_map<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator==">operator==</A></B>( const hash_multimap<Key, Ty, Tr, Alloc>& left, const hash_multimap<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator!=">operator!=</A></B>( const hash_map<Key, Ty, Tr, Alloc>& left, const hash_map<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator!=">operator!=</A></B>( const hash_multimap<Key, Ty, Tr, Alloc>& left, const hash_multimap<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator<">operator<</A></B>( const hash_map<Key, Ty, Tr, Alloc>& left, const hash_map<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator<">operator<</A></B>( const hash_multimap<Key, Ty, Tr, Alloc>& left, const hash_multimap<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator>">operator></A></B>( const hash_map<Key, Ty, Tr, Alloc>& left, const hash_map<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator>">operator></A></B>( const hash_multimap<Key, Ty, Tr, Alloc>& left, const hash_multimap<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator<=">operator<=</A></B>( const hash_map<Key, Ty, Tr, Alloc>& left, const hash_map<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator<=">operator<=</A></B>( const hash_multimap<Key, Ty, Tr, Alloc>& left, const hash_multimap<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator>=">operator>=</A></B>( const hash_map<Key, Ty, Tr, Alloc>& left, const hash_map<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> bool <B><A HREF="#operator>=">operator>=</A></B>( const hash_multimap<Key, Ty, Tr, Alloc>& left, const hash_multimap<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> void <B><A HREF="#swap">swap</A></B>( hash_map<Key, Ty, Tr, Alloc>& left, hash_map<Key, Ty, Tr, Alloc>& right);template<class Key, class Ty, class Tr, class Alloc> void <B><A HREF="#swap">swap</A></B>( hash_multimap<Key, Ty, Tr, Alloc>& left, hash_multimap<Key, Ty, Tr, Alloc>& right); };</PRE><H2><A NAME="hash_compare"><CODE>hash_compare</CODE></A></H2><PRE>template<class Key, class Pr = less<Key> > class <B>hash_compare</B> { Pr <B>comp</B>;public: const size_t <B>bucket_size</B> = 4; const size_t <B>min_buckets</B> = 8; <B>hash_compare</B>(); <B>hash_compare</B>(Pr pred); size_t <B>operator()</B>(const Key& Key) const; bool <B>operator()</B>(const Key& keyval1, const Key& keyval2) const; };</PRE><P>The template class describes an object that can be used byany of the containers<CODE><A HREF="#hash_map">hash_map</A></CODE>,<CODE><A HREF="#hash_multimap">hash_multimap</A></CODE>,<CODE><A HREF="hash_set.html#hash_set">hash_set</A></CODE>, or<CODE><A HREF="hash_set.html#hash_multiset">hash_multiset</A></CODE> as a<B><A NAME="hash traits">hash traits</A></B> objectto order the sequence it controls.Each of these stores hash traits object of type <CODE>Tr</CODE>(a template parameter). You can derive a class from a specialization of<CODE>hash_compare</CODE>, to selectively override certain functionsand objects. Or you can supply your own version of this class,provided you meet certain minimum requirements.Specifically, for an object <CODE>hash_comp</CODE> of type<CODE>hash_compare<Key, Pr></CODE>,the following behavior is required by the above containers:</P><UL><LI>For all values <CODE>keyval</CODE> of type <CODE>Key</CODE>,the call <CODE>hash_comp(keyval)</CODE> serves as a<B><A NAME="hash function">hash function</A></B>,which yields a distribution of values of type <CODE>size_t</CODE>.The function supplied by <CODE>hash_compare</CODE> simplyreturns <CODE>keyval</CODE>.</LI><LI>For any value <CODE>keyval1</CODE> oftype <CODE>Key</CODE> that precedes <CODE>keyval2</CODE> in the sequenceand has the same hash value (value returned by the hash function),<CODE>hash_comp(keyval2, keyval1)</CODE> is false. The function must impose a<A HREF="lib_stl.html#strict weak ordering">strict weak ordering</A>on values of type <CODE>Key</CODE>.The function supplied by <CODE>hash_compare</CODE> returns<CODE>comp(keyval1, keyval2)</CODE> where <CODE>comp</CODE> is a storedobject of type <CODE>Pr</CODE> that you can specify when you constructthe object <CODE>hash_comp</CODE>. For the default <CODE>Pr</CODE> parameter type<CODE><A HREF="functio2.html#less">less</A><Key></CODE>,sort keys never decrease in value.</LI><LI>The integer constant<CODE><A NAME="hash_compare::bucket_size">bucket_size</A></CODE>specifies the mean number of elements per ``bucket'' (hash-tableentry) that the container should endeavor not to exceed. It mustbe greater than zero. The value supplied by<CODE>hash_compare</CODE> is 4.</LI><LI>The integer constant<CODE><A NAME="hash_compare::min_buckets">min_buckets</A></CODE>specifies the minimum number of buckets to maintain in the hash table.It must be a power of two and greater than zero. The value supplied by<CODE>hash_compare</CODE> is 8.</LI></UL><H2><A NAME="hash_map"><CODE>hash_map</CODE></A></H2><HR><P><B><CODE><A HREF="#hash_map::allocator_type">allocator_type</A>· <A HREF="#hash_map::begin">begin</A>· <A HREF="#hash_map::clear">clear</A>· <A HREF="#hash_map::const_iterator">const_iterator</A>· <A HREF="#hash_map::const_pointer">const_pointer</A>· <A HREF="#hash_map::const_reference">const_reference</A>· <A HREF="#hash_map::const_reverse_iterator">const_reverse_iterator</A>· <A HREF="#hash_map::count">count</A>· <A HREF="#hash_map::difference_type">difference_type</A>· <A HREF="#hash_map::empty">empty</A>· <A HREF="#hash_map::end">end</A>· <A HREF="#hash_map::equal_range">equal_range</A>· <A HREF="#hash_map::erase">erase</A>· <A HREF="#hash_map::find">find</A>· <A HREF="#hash_map::get_allocator">get_allocator</A>· <A HREF="#hash_map::insert">insert</A>· <A HREF="#hash_map::iterator">iterator</A>· <A HREF="#hash_map::key_comp">key_comp</A>· <A HREF="#hash_map::key_compare">key_compare</A>· <A HREF="#hash_map::key_type">key_type</A>· <A HREF="#hash_map::lower_bound">lower_bound</A>· <A HREF="#hash_map::hash_map">hash_map</A>· <A HREF="#hash_map::mapped_type">mapped_type</A>· <A HREF="#hash_map::max_size">max_size</A>· <A HREF="#hash_map::operator[]">operator[]</A>· <A HREF="#hash_map::pointer">pointer</A>· <A HREF="#hash_map::rbegin">rbegin</A>· <A HREF="#hash_map::reference">reference</A>· <A HREF="#hash_map::rend">rend</A>· <A HREF="#hash_map::reverse_iterator">reverse_iterator</A>· <A HREF="#hash_map::size">size</A>· <A HREF="#hash_map::size_type">size_type</A>· <A HREF="#hash_map::swap">swap</A>· <A HREF="#hash_map::upper_bound">upper_bound</A>· <A HREF="#hash_map::value_comp">value_comp</A>· <A HREF="#hash_map::value_compare">value_compare</A>· <A HREF="#hash_map::value_type">value_type</A></CODE></B></P><HR><PRE>template<class Key, class Ty, class Tr = hash_compare<Key, less<Key> >, class Alloc = allocator<pair<const Key, Ty> > > class <B>hash_map</B> {public: typedef Key <B><A HREF="#hash_map::key_type">key_type</A></B>; typedef Ty <B><A HREF="#hash_map::mapped_type">mapped_type</A></B>; typedef Tr <B><A HREF="#hash_map::key_compare">key_compare</A></B>; typedef Alloc <B><A HREF="#hash_map::allocator_type">allocator_type</A></B>; typedef pair<const Key, Ty> <B><A HREF="#hash_map::value_type">value_type</A></B>; class <B><A HREF="#hash_map::value_compare">value_compare</A></B>; typedef Alloc::pointer <B><A HREF="#hash_map::pointer">pointer</A></B>; typedef Alloc::const_pointer <B><A HREF="#hash_map::const_pointer">const_pointer</A></B>; typedef Alloc::reference <B><A HREF="#hash_map::reference">reference</A></B>; typedef Alloc::const_reference <B><A HREF="#hash_map::const_reference">const_reference</A></B>; typedef T0 <B><A HREF="#hash_map::iterator">iterator</A></B>; typedef T1 <B><A HREF="#hash_map::const_iterator">const_iterator</A></B>; typedef T2 <B><A HREF="#hash_map::size_type">size_type</A></B>; typedef T3 <B><A HREF="#hash_map::difference_type">difference_type</A></B>; typedef reverse_iterator<const_iterator> <B><A HREF="#hash_map::const_reverse_iterator">const_reverse_iterator</A></B>; typedef reverse_iterator<iterator> <B><A HREF="#hash_map::reverse_iterator">reverse_iterator</A></B>; <B><A HREF="#hash_map::hash_map">hash_map</A></B>(); explicit <B><A HREF="#hash_map::hash_map">hash_map</A></B>(const Tr& traits); <B><A HREF="#hash_map::hash_map">hash_map</A></B>(const Tr& traits, const Alloc& al); <B><A HREF="#hash_map::hash_map">hash_map</A></B>(const hash_map& right); template<class InIt> <B><A HREF="#hash_map::hash_map">hash_map</A></B>(InIt first, InIt last); template<class InIt> <B><A HREF="#hash_map::hash_map">hash_map</A></B>(InIt first, InIt last, const Tr& traits); template<class InIt> <B><A HREF="#hash_map::hash_map">hash_map</A></B>(InIt first, InIt last, const Tr& traits, const Alloc& al); iterator <B><A HREF="#hash_map::begin">begin</A></B>(); const_iterator <B><A HREF="#hash_map::begin">begin</A></B>() const; iterator <B><A HREF="#hash_map::end">end</A></B>(); const_iterator <B><A HREF="#hash_map::end">end</A></B>() const; reverse_iterator <B><A HREF="#hash_map::rbegin">rbegin</A></B>(); const_reverse_iterator <B><A HREF="#hash_map::rbegin">rbegin</A></B>() const; reverse_iterator <B><A HREF="#hash_map::rend">rend</A></B>(); const_reverse_iterator <B><A HREF="#hash_map::rend">rend</A></B>() const; size_type <B><A HREF="#hash_map::size">size</A></B>() const; size_type <B><A HREF="#hash_map::max_size">max_size</A></B>() const; bool <B><A HREF="#hash_map::empty">empty</A></B>() const; Alloc <B><A HREF="#hash_map::get_allocator">get_allocator</A></B>() const; mapped_type <B><A HREF="#hash_map::operator[]">operator[]</A></B>(const Key& keyval); pair<iterator, bool> <B><A HREF="#hash_map::insert">insert</A></B>(const value_type& val); iterator <B><A HREF="#hash_map::insert">insert</A></B>(iterator where, const value_type& val); template<class InIt> void <B><A HREF="#hash_map::insert">insert</A></B>(InIt first, InIt last); iterator <B><A HREF="#hash_map::erase">erase</A></B>(iterator where); iterator <B><A HREF="#hash_map::erase">erase</A></B>(iterator first, iterator last); size_type <B><A HREF="#hash_map::erase">erase</A></B>(const Key& keyval); void <B><A HREF="#hash_map::clear">clear</A></B>(); void <B><A HREF="#hash_map::swap">swap</A></B>(hash_map& right); key_compare <B><A HREF="#hash_map::key_comp">key_comp</A></B>() const; value_compare <B><A HREF="#hash_map::value_comp">value_comp</A></B>() const; iterator <B><A HREF="#hash_map::find">find</A></B>(const Key& keyval); const_iterator <B><A HREF="#hash_map::find">find</A></B>(const Key& keyval) const; size_type <B><A HREF="#hash_map::count">count</A></B>(const Key& keyval) const; iterator <B><A HREF="#hash_map::lower_bound">lower_bound</A></B>(const Key& keyval); const_iterator <B><A HREF="#hash_map::lower_bound">lower_bound</A></B>(const Key& keyval) const; iterator <B><A HREF="#hash_map::upper_bound">upper_bound</A></B>(const Key& keyval); const_iterator <B><A HREF="#hash_map::upper_bound">upper_bound</A></B>(const Key& keyval) const; pair<iterator, iterator> <B><A HREF="#hash_map::equal_range">equal_range</A></B>(const Key& keyval); pair<const_iterator, const_iterator> <B><A HREF="#hash_map::equal_range">equal_range</A></B>(const Key& keyval) const; };</PRE><P>The template class describes an object that controls avarying-length sequence of elements of type<CODE><A HREF="utility.html#pair">pair</A><const Key, Ty></CODE>.The sequence is<A HREF="lib_stl.html#sequence ordering">ordered by</A> the<A HREF="#hash traits">hash traits</A> object<CODE>Tr</CODE>, which includes both a two-operand function for imposing a<A HREF="lib_stl.html#strict weak ordering">strict weak ordering</A>and a one-operand <A HREF="#hash function">hash function</A>.The first element of each pair is the <B>sort key</B> and thesecond is its associated <B>value</B>.The sequence is represented in a way that permits lookup, insertion,and removal of an arbitrary element with a number of operations that can beindependent of the number of elements in the sequence (constant time).In the worst case, the number of operations isproportional to the number of elementsin the sequence (linear time). Moreover, inserting an elementinvalidates no iterators, and removing an elementinvalidates only those iterators which point at the removed element.</P><P>The object orders the sequence it controls by calling a stored⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -