| <HTML> |
| <HEAD> |
| <TITLE>Container Types Not Found in the C++ Standard Library</TITLE> |
| <LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD> |
| <BODY BGCOLOR=#FFFFFF> |
| <A HREF="4-3.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="5.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV> |
| <H2>4.4 Container Types Not Found in the C++ Standard Library</H2> |
| <A NAME="idx63"><!></A> |
| <P>The C++ Standard Library provides the containers used in the solution of most programming problems. However, there are a number of classic container types that are not included. In most cases, this is because the provided containers can be easily adapted to a wide variety of uses, including the uses traditionally provided by the omitted containers. <A HREF="4-4.html#Table 8">Table 8</A> lists the container types that are not contained in the library, and the simple substitution.</P> |
| <H4><A NAME="Table 8">Table 8: Container types not given in the C++ Standard Library </A></H4> |
| <TABLE BORDER="1" CELLPADDING="3" CELLSPACING="3"> |
| <tr><td valign=top><B>Container type NOT given</B> |
| </td><td valign=top><B>C++ Standard Library substitution</B> |
| </td></tr> |
| <A NAME="idx64"><!></A> |
| <tr><td valign=top><P CLASS="TABLE">tree </P> |
| <A NAME="idx65"><!></A> |
| </td><td valign=top><P CLASS="TABLE">The <B><I><A HREF="../stdlibref/set.html">set</A></I></B> datatype is internally implemented using a form of binary search tree. For most problems that would be solved using trees, the <B><I>set</I></B> datatype is an adequate substitute.</P> |
| </td></tr> |
| <A NAME="idx66"><!></A> |
| <tr><td valign=top><P CLASS="TABLE">multidimensional array </P> |
| </td><td valign=top><P CLASS="TABLE">Since <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B>s can hold other <B><I>vector</I></B>s as elements, such structures can be easily constructed.</P> |
| </td></tr> |
| <A NAME="idx67"><!></A> |
| <tr><td valign=top><P CLASS="TABLE">graph </P> |
| </td><td valign=top><P CLASS="TABLE">One representation for graphs can be easily constructed as a <B><I><A HREF="../stdlibref/map.html">map</A></I></B> that holds other <B><I>map</I></B>s. This type of structure is described in the sample problem discussed in <A HREF="9-3.html#932">Section 9.3.2</A>.</P> |
| </td></tr> |
| <A NAME="idx68"><!></A> |
| <tr><td valign=top><P CLASS="TABLE">sparse array </P> |
| </td><td valign=top><P CLASS="TABLE">A novel substitution is the graph representation discussed in <A HREF="9-3.html#932">Section 9.3.2</A>.</P> |
| </td></tr> |
| <A NAME="idx69"><!></A> |
| <tr><td valign=top><P CLASS="TABLE">hash table </P> |
| </td><td valign=top><P CLASS="TABLE">A hash table provides amortized constant time access, and insertion and removal of elements, by converting access and removal operations into indexing operations. In the C++ Standard Library, a hash table can be easily constructed as a <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B> (or <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B>) that holds <B><I><A HREF="../stdlibref/list.html">list</A></I></B>s (or even <B><I><A HREF="../stdlibref/set.html">set</A></I></B>s) as elements. A similar structure is described in the radix sort sample problem discussed in <A HREF="7-3.html">Section 7.3</A>, although this example does not include invoking a hash function to convert a value into an index.</P> |
| <P CLASS="TABLE"><B><I><A HREF="../stdlibref/map.html">map</A></I></B>s and <B><I><A HREF="../stdlibref/multimap.html">multimap</A></I></B>s provide features similar to a hash table's, but inserts and searches are performed in log(N) time, with N being the size of the <B><I>map</I></B> or <B><I>multimap</I></B>.</P> |
| </td></tr> |
| <A NAME="idx70"><!></A> |
| <tr><td valign=top><P CLASS="TABLE">some <B><I><A HREF="../stdlibref/set.html">set</A></I></B> functionality</P> |
| </td><td valign=top><P CLASS="TABLE">In the C++ Standard Library, the <B><I><A HREF="../stdlibref/set.html">set</A></I></B> datatype is specifically ordered, and <B><I>set</I></B> operations (union, intersection, and so on) cannot be performed on collections of unordered values (for example, a set of complex numbers). A <B><I><A HREF="../stdlibref/list.html">list</A></I></B> can be used as a substitute, although it is still necessary to write special set operation functions, as the generic algorithms cannot be used with <B><I>list</I></B>s. </P> |
| </td></tr> |
| </TABLE> |
| |
| <BR> |
| <HR> |
| <A HREF="4-3.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="5.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A> |
| |
| <!-- Google Analytics tracking code --> |
| <script src="http://www.google-analytics.com/urchin.js" type="text/javascript"> |
| </script> |
| <script type="text/javascript"> |
| _uacct = "UA-1775151-1"; |
| urchinTracker(); |
| </script> |
| <!-- end of Google Analytics tracking code --> |
| |
| </BODY> |
| </HTML> |
