📄 sortedassociativecontainer.html
字号:
<HTML><!-- -- Copyright (c) 1996-1999 -- Silicon Graphics Computer Systems, Inc. -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Silicon Graphics makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- -- Copyright (c) 1994 -- Hewlett-Packard Company -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Hewlett-Packard Company makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- --><Head><Title>Sorted Associative Container</Title><!-- Generated by htmldoc --></HEAD><BODY TEXT="#000000" LINK="#006600" ALINK="#003300" VLINK="#7C7F87" BGCOLOR="#FFFFFF"><A HREF="/"><IMG SRC="/images/common/sgilogo_small.gif" ALT="SGI Logo" WIDTH="80" HEIGHT="72" BORDER="0"></A><P><!--end header--><BR Clear><H1>Sorted Associative Container</H1><Table CellPadding=0 CellSpacing=0 width=100%><TR><TD Align=left><Img src = "containers.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD><TD Align=right><Img src = "concept.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD></TR><TR><TD Align=left VAlign=top><b>Category</b>: containers</TD><TD Align=right VAlign=top><b>Component type</b>: concept</TD></TR></Table><h3>Description</h3>A Sorted Associative Container is a type of <A href="AssociativeContainer.html">Associative Container</A>.Sorted Associative Containers use an ordering relation on their keys;two keys are considered to be equivalent if neither one is less thanthe other. (If the ordering relation is case-insensitive stringcomparison, for example, then the keys "abcde" and "aBcDe" areequivalent.) <P>Sorted Associative Containers guarantee that the complexity for mostoperations is never worse than logarithmic <A href="#1">[1]</A>, and they alsoguarantee that their elements are always sorted in ascending order bykey.<h3>Refinement of</h3><A href="ReversibleContainer.html">Reversible Container</A>, <A href="AssociativeContainer.html">Associative Container</A><h3>Associated types</h3>Two new types are introduced, in addition to the types defined in the<A href="AssociativeContainer.html">Associative Container</A> and <A href="ReversibleContainer.html">Reversible Container</A> requirements. <Table border><TR><TD VAlign=top><tt>X::key_compare</tt></TD><TD VAlign=top>The type of a <A href="StrictWeakOrdering.html">Strict Weak Ordering</A> used to compare keys. Its argument type must be <tt>X::key_type</tt>.</TD></TR><TR><TD VAlign=top><tt>X::value_compare</tt></TD><TD VAlign=top>The type of a <A href="StrictWeakOrdering.html">Strict Weak Ordering</A> used to compare values. Its argument type must be <tt>X::value_type</tt>, and it compares two objects of <tt>value_type</tt> by passing the keys associated with those objects to a function object of type <tt>key_compare</tt>.</TD></tr></table><h3>Notation</h3><Table><TR><TD VAlign=top><tt>X</tt></TD><TD VAlign=top>A type that is a model of Sorted Associative Container</TD></TR><TR><TD VAlign=top><tt>a</tt></TD><TD VAlign=top>Object of type <tt>X</tt></TD></TR><TR><TD VAlign=top><tt>t</tt></TD><TD VAlign=top>Object of type <tt>X::value_type</tt></TD></TR><TR><TD VAlign=top><tt>k</tt></TD><TD VAlign=top>Object of type <tt>X::key_type</tt></TD></TR><TR><TD VAlign=top><tt>p</tt>, <tt>q</tt></TD><TD VAlign=top>Object of type <tt>X::iterator</tt></TD></TR><TR><TD VAlign=top><tt>c</tt></TD><TD VAlign=top>Object of type <tt>X::key_compare</tt></TD></tr></table><h3>Definitions</h3><h3>Valid expressions</h3>In addition to the expressions defined in <A href="AssociativeContainer.html">Associative Container</A>and <A href="ReversibleContainer.html">Reversible Container</A>, the following expressions must be valid.<Table border><TR><TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH><TH>Return type</TH></TR><TR><TD VAlign=top>Default constructor</TD><TD VAlign=top><pre>X()X a;</pre></TD><TD VAlign=top> </TD><TD VAlign=top> </TD></TR><TR><TD VAlign=top>Constructor with compare</TD><TD VAlign=top><pre>X(c)X a(c);</pre></TD><TD VAlign=top> </TD><TD VAlign=top> </TD></TR><TR><TD VAlign=top>Key comparison</TD><TD VAlign=top><tt>a.key_comp()</tt></TD><TD VAlign=top> </TD><TD VAlign=top><tt>X::key_compare</tt></TD></TR><TR><TD VAlign=top>Value comparison</TD><TD VAlign=top><tt>a::value_compare()</tt></TD><TD VAlign=top> </TD><TD VAlign=top><tt>X::value_compare</tt></TD></TR><TR><TD VAlign=top>Lower bound</TD><TD VAlign=top><tt>a.lower_bound(k)</tt></TD><TD VAlign=top> </TD><TD VAlign=top><tt>iterator</tt> if <tt>a</tt> is mutable, otherwise <tt>const_iterator</tt>.</TD></TR><TR><TD VAlign=top>Upper bound</TD><TD VAlign=top><tt>a.upper_bound(k)</tt></TD><TD VAlign=top> </TD><TD VAlign=top><tt>iterator</tt> if <tt>a</tt> is mutable, otherwise <tt>const_iterator</tt>.</TD></TR><TR><TD VAlign=top>Equal range</TD><TD VAlign=top><tt>a.equal_range(k)</tt></TD><TD VAlign=top> </TD><TD VAlign=top><tt>pair<iterator, iterator></tt> if <tt>a</tt> is mutable, otherwise <tt>pair<const_iterator, const_iterator></tt>.</TD></tr></table><h3>Expression semantics</h3><Table border><TR><TH>Name</TH><TH>Expression</TH><TH>Precondition</TH><TH>Semantics</TH><TH>Postcondition</TH></TR><TR><TD VAlign=top>Default constructor</TD><TD VAlign=top><pre>X()X a;</pre></TD><TD VAlign=top> </TD><TD VAlign=top>Creates an empty container, using <tt>key_compare()</tt> as the comparison object.</TD><TD VAlign=top>The size of the container is <tt>0</tt>.</TD></TR><TR><TD VAlign=top>Constructor with compare</TD><TD VAlign=top><pre>X(c)X a(c);</pre></TD><TD VAlign=top> </TD><TD VAlign=top>Creates an empty container, using <tt>c</tt> as the comparison object.</TD><TD VAlign=top>The size of the container is <tt>0</tt>. <tt>key_comp()</tt> returns a function object that is equivalent to <tt>c</tt>.</TD></TR><TR><TD VAlign=top>Key comparison</TD><TD VAlign=top><tt>a.key_comp()</tt></TD><TD VAlign=top> </TD><TD VAlign=top>Returns the key comparison object used by <tt>a</tt>.</TD><TD VAlign=top> </TD></TR><TR><TD VAlign=top>Value comparison</TD><TD VAlign=top><tt>a::value_compare()</tt></TD><TD VAlign=top> </TD><TD VAlign=top>Returns the value comparison object used by <tt>a</tt>.</TD><TD VAlign=top>If <tt>t1</tt> and <tt>t2</tt> are objects of type <tt>value_type</tt>, and <tt>k1</tt> and <tt>k2</tt> are the keys associated with them, then <tt>a.value_comp()(t1, t2)</tt> is equivalent to <tt>a.key_comp()(k1, k2)</tt>.</TD></TR><TR><TD VAlign=top>Lower bound</TD><TD VAlign=top><tt>a.lower_bound(k)</tt></TD><TD VAlign=top> </TD><TD VAlign=top>Returns an iterator pointing to the first element whose key is not less than <tt>k</tt>. Returns <tt>a.end()</tt> if no such element exists.</TD><TD VAlign=top>If <tt>a</tt> contains any elements that have the same key as <tt>k</tt>, then the return value of <tt>lower_bound</tt> points to the first such element.</TD></TR><TR><TD VAlign=top>Upper bound</TD><TD VAlign=top><tt>a.upper_bound(k)</tt></TD><TD VAlign=top> </TD><TD VAlign=top>Returns an iterator pointing to the first element whose key is greater than <tt>k</tt>. Returns <tt>a.end()</tt> if no such element exists.</TD><TD VAlign=top>If <tt>a</tt> contains any elements that have the same key as <tt>k</tt>, then the return value of <tt>upper_bound</tt> points to one past the last such element.</TD></TR><TR><TD VAlign=top>Equal range</TD><TD VAlign=top><tt>a.equal_range(k)</tt></TD><TD VAlign=top> </TD><TD VAlign=top>Returns a pair whose first element is <tt>a.lower_bound(k)</tt> and whose second element is <tt>a.upper_bound(k)</tt>. </TD><TD VAlign=top> </TD></tr></table><h3>Complexity guarantees</h3><tt>key_comp()</tt> and <tt>value_comp()</tt> are constant time.<P>Erase element is constant time.<P>Erase key is <tt>O(log(size()) + count(k))</tt>. <A href="#1">[1]</A><P>Erase range is <tt>O(log(size()) + N)</tt>, where <tt>N</tt> is the length of therange. <A href="#1">[1]</A><P>Find is logarithmic. <A href="#1">[1]</A><P>Count is <tt>O(log(size()) + count(k))</tt>. <A href="#1">[1]</A><P>Lower bound, upper bound, and equal range are logarithmic. <A href="#1">[1]</A><h3>Invariants</h3><Table border><TR><TD VAlign=top>Definition of <tt>value_comp</tt></TD><TD VAlign=top>If <tt>t1</tt> and <tt>t2</tt> are objects of type <tt>X::value_type</tt> and <tt>k1</tt> and <tt>k2</tt> are the keys associated with those objects, then <tt>a.value_comp()</tt> returns a <A href="functors.html">function object</A> such that <tt>a.value_comp()(t1, t2)</tt> is equivalent to <tt>a.key_comp()(k1, k2)</tt>.</TD></TR><TR><TD VAlign=top>Ascending order</TD><TD VAlign=top>The elements in a Sorted Associative Container are always arranged in ascending order by key. That is, if <tt>a</tt> is a Sorted Associative Container, then <tt><A href="is_sorted.html">is_sorted</A>(a.begin(), a.end(), a.value_comp())</tt> is always <tt>true</tt>.</TD></tr></table><h3>Models</h3><UL><LI><tt><A href="set.html">set</A></tt><LI><tt><A href="multiset.html">multiset</A></tt><LI><tt><A href="Map.html">map</A></tt><LI><tt><A href="Multimap.html">multimap</A></tt></UL><h3>Notes</h3><P><A name="1">[1]</A>This is a much stronger guarantee than the one providedby <A href="AssociativeContainer.html">Associative Container</A>. The guarantees in <A href="AssociativeContainer.html">Associative Container</A>only apply to average complexity; worst case complexity is allowed tobe greater. Sorted Associative Container, however, provides an upperlimit on worst case complexity.<P><A name="2">[2]</A>This definition is consistent with the semantics described in<A href="AssociativeContainer.html">Associative Container</A>. It is a stronger condition, though: if<tt>a</tt> contains no elements with the key <tt>k</tt>, then <tt>a.equal_range(k)</tt>returns an empty range that indicates the position where those elementswould be if they did exist. The <A href="AssociativeContainer.html">Associative Container</A> requirements,however, merely state that the return value is an arbitrary empty range.<h3>See also</h3><A href="AssociativeContainer.html">Associative Container</A>, <A href="HashedAssociativeContainer.html">Hashed Associative Container</A><!-- start footer --><!-- Footer Begins --><STYLE TYPE="text/css"><!--TD.footer, TD.footer A{ font-family: Arial, helvetica, sans-serif; font-size: 8pt;}A.home {font-family: Arial, helvetica, sans-serif;}--></STYLE><P><A CLASS="home" HREF="index.html">STL Home</A><P><TABLE WIDTH="600" CELLPADDING="0" CELLPADDING="0" BORDER="0"> <TR> <TD ALIGN="RIGHT" CLASS="footer"><A HREF="/company_info/terms.html" TARGET="_top">terms of use</A> | <A HREF="/company_info/privacy.html" TARGET="_top">privacy policy</A></TD> <TD ALIGN="CENTER" CLASS="footer"> | </TD> <TD ALIGN="LEFT" CLASS="footer"><A HREF="/cgi-bin/feedback/" TARGET="_top">contact us</A></TD> </TR><TR> <TD ALIGN="RIGHT" CLASS="footer">Copyright © 1993-2003 Silicon Graphics, Inc. All rights reserved.</TD> <TD ALIGN="CENTER" CLASS="footer"> | </TD> <TD ALIGN="LEFT" CLASS="footer"><A HREF="/company_info/trademarks/" TARGET="_top">Trademark Information</A></TD> </TR></TABLE><!-- Footer Ends --><!-- end footer --><P></BODY></HTML> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -