<!--
    Licensed to the Apache Software  Foundation (ASF) under one or more
    contributor  license agreements.  See  the NOTICE  file distributed
    with  this  work  for  additional information  regarding  copyright
    ownership.   The ASF  licenses this  file to  you under  the Apache
    License, Version  2.0 (the  License); you may  not use  this file
    except in  compliance with the License.   You may obtain  a copy of
    the License at

    http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the  License is distributed on an  "AS IS" BASIS,
    WITHOUT  WARRANTIES OR CONDITIONS  OF ANY  KIND, either  express or
    implied.   See  the License  for  the  specific language  governing
    permissions and limitations under the License.

    Copyright 1999-2007 Rogue Wave Software, Inc.
-->

<HTML>
<HEAD>
<TITLE>The set Data Abstraction</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="8.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="8-2.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>8.1 The set Data Abstraction</H2>
<A NAME="idx127"><!></A>
<P>A <B><I><A HREF="../stdlibref/set.html">set</A></I></B> is a collection of values. Although the abstract concept of a set does not necessarily imply an ordered collection, the standard library <B><I>set</I></B> datatype is always ordered. </P>
<BLOCKQUOTE><HR><B>
NOTE --  If necessary, a collection of values that cannot be ordered can be maintained in an alternative data structure, such as a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>.
</B><HR></BLOCKQUOTE>
<A NAME="idx128"><!></A>
<P>Because the container used to implement the <B><I><A HREF="../stdlibref/set.html">set</A></I></B> data structure maintains values in an ordered representation, <B><I>set</I></B>s are optimized for insertion and removal of elements, and for testing to see whether a particular value is contained in the collection. Each of these operations can be performed in a logarithmic number of steps, whereas for a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>, <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B>, or <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B>, each operation requires in the worst case an examination of every element held by the container. For this reason, <B><I><A HREF="../stdlibref/set.html">std::set</A></I></B> should be the data structure of choice in any problem that emphasizes insertion, removal, and test for inclusion of values. Like a <B><I>list</I></B>, a <B><I>set</I></B> is not limited in size, but rather expands and contracts as elements are added to or removed from the collection.</P>
<A NAME="idx129"><!></A>
<P>There are two varieties of <B><I><A HREF="../stdlibref/set.html">set</A></I></B>s provided by the C++ Standard Library. In the <B><I>set</I></B> container, every element is unique, and insertions of values that are already contained in the <B><I>set</I></B> are ignored. In the <B><I><A HREF="../stdlibref/multiset.html">multiset</A></I></B> container, on the other hand, multiple occurrences of the same value are permitted.</P>
<BLOCKQUOTE><HR><B>
NOTE -- In other programming languages, a multiset is sometimes referred to as a bag.
</B><HR></BLOCKQUOTE>
<A NAME="811"><H3>8.1.1 Include Files</H3></A>
<A NAME="idx130"><!></A>
<P>Whenever you use a <B><I><A HREF="../stdlibref/set.html">set</A></I></B> or a <B><I><A HREF="../stdlibref/multiset.html">multiset</A></I></B>, you must include the set header file:</P>

<UL><PRE>
#include &lt;set&gt;
</PRE></UL>

<BR>
<HR>
<A HREF="8.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="8-2.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>