libstdc++-v3/doc/html/manual/associative.html

   1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Associative</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"><meta name="keywords" content="
   2       ISO C++
   3     ,
   4       library
   5     "><meta name="keywords" content="
   6       ISO C++
   7     ,
   8       runtime
   9     ,
  10       library
  11     "><link rel="home" href="../index.html" title="The GNU C++ Library"><link rel="up" href="containers.html" title="Chapter 9.  Containers"><link rel="prev" href="containers.html" title="Chapter 9.  Containers"><link rel="next" href="containers_and_c.html" title="Interacting with C"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Associative</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="containers.html">Prev</a> </td><th width="60%" align="center">Chapter 9.
  12   Containers
  13
  14 </th><td width="20%" align="right"> <a accesskey="n" href="containers_and_c.html">Next</a></td></tr></table><hr></div><div class="section" title="Associative"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="std.containers.associative"></a>Associative</h2></div></div></div><div class="section" title="Insertion Hints"><div class="titlepage"><div><div><h3 class="title"><a name="containers.associative.insert_hints"></a>Insertion Hints</h3></div></div></div><p>
  15      Section [23.1.2], Table 69, of the C++ standard lists this
  16      function for all of the associative containers (map, set, etc):
  17    </p><pre class="programlisting">
  18       a.insert(p,t);
  19    </pre><p>
  20      where 'p' is an iterator into the container 'a', and 't' is the
  21      item to insert.  The standard says that <span class="quote">“<span class="quote"><code class="code">t</code> is
  22      inserted as close as possible to the position just prior to
  23      <code class="code">p</code>.</span>”</span> (Library DR #233 addresses this topic,
  24      referring to <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html" target="_top">N1780</a>.
  25      Since version 4.2 GCC implements the resolution to DR 233, so
  26      that insertions happen as close as possible to the hint. For
  27      earlier releases the hint was only used as described below.
  28    </p><p>
  29      Here we'll describe how the hinting works in the libstdc++
  30      implementation, and what you need to do in order to take
  31      advantage of it.  (Insertions can change from logarithmic
  32      complexity to amortized constant time, if the hint is properly
  33      used.)  Also, since the current implementation is based on the
  34      SGI STL one, these points may hold true for other library
  35      implementations also, since the HP/SGI code is used in a lot of
  36      places.
  37    </p><p>
  38      In the following text, the phrases <span class="emphasis"><em>greater
  39      than</em></span> and <span class="emphasis"><em>less than</em></span> refer to the
  40      results of the strict weak ordering imposed on the container by
  41      its comparison object, which defaults to (basically)
  42      <span class="quote">“<span class="quote">&lt;</span>”</span>.  Using those phrases is semantically sloppy,
  43      but I didn't want to get bogged down in syntax.  I assume that if
  44      you are intelligent enough to use your own comparison objects,
  45      you are also intelligent enough to assign <span class="quote">“<span class="quote">greater</span>”</span>
  46      and <span class="quote">“<span class="quote">lesser</span>”</span> their new meanings in the next
  47      paragraph.  *grin*
  48    </p><p>
  49      If the <code class="code">hint</code> parameter ('p' above) is equivalent to:
  50    </p><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
  51           <code class="code">begin()</code>, then the item being inserted should
  52           have a key less than all the other keys in the container.
  53           The item will be inserted at the beginning of the container,
  54           becoming the new entry at <code class="code">begin()</code>.
  55       </p></li><li class="listitem"><p>
  56           <code class="code">end()</code>, then the item being inserted should have
  57           a key greater than all the other keys in the container.  The
  58           item will be inserted at the end of the container, becoming
  59           the new entry before <code class="code">end()</code>.
  60       </p></li><li class="listitem"><p>
  61           neither <code class="code">begin()</code> nor <code class="code">end()</code>, then:
  62           Let <code class="code">h</code> be the entry in the container pointed to
  63           by <code class="code">hint</code>, that is, <code class="code">h = *hint</code>.  Then
  64           the item being inserted should have a key less than that of
  65           <code class="code">h</code>, and greater than that of the item preceding
  66           <code class="code">h</code>.  The new item will be inserted between
  67           <code class="code">h</code> and <code class="code">h</code>'s predecessor.
  68           </p></li></ul></div><p>
  69      For <code class="code">multimap</code> and <code class="code">multiset</code>, the
  70      restrictions are slightly looser: <span class="quote">“<span class="quote">greater than</span>”</span>
  71      should be replaced by <span class="quote">“<span class="quote">not less than</span>”</span>and <span class="quote">“<span class="quote">less
  72      than</span>”</span> should be replaced by <span class="quote">“<span class="quote">not greater
  73      than.</span>”</span> (Why not replace greater with
  74      greater-than-or-equal-to?  You probably could in your head, but
  75      the mathematicians will tell you that it isn't the same thing.)
  76    </p><p>
  77      If the conditions are not met, then the hint is not used, and the
  78      insertion proceeds as if you had called <code class="code"> a.insert(t)
  79      </code> instead.  (<span class="emphasis"><em>Note </em></span> that GCC releases
  80      prior to 3.0.2 had a bug in the case with <code class="code">hint ==
  81      begin()</code> for the <code class="code">map</code> and <code class="code">set</code>
  82      classes.  You should not use a hint argument in those releases.)
  83    </p><p>
  84      This behavior goes well with other containers'
  85      <code class="code">insert()</code> functions which take an iterator: if used,
  86      the new item will be inserted before the iterator passed as an
  87      argument, same as the other containers.
  88    </p><p>
  89      <span class="emphasis"><em>Note </em></span> also that the hint in this
  90      implementation is a one-shot.  The older insertion-with-hint
  91      routines check the immediately surrounding entries to ensure that
  92      the new item would in fact belong there.  If the hint does not
  93      point to the correct place, then no further local searching is
  94      done; the search begins from scratch in logarithmic time.
  95    </p></div><div class="section" title="bitset"><div class="titlepage"><div><div><h3 class="title"><a name="containers.associative.bitset"></a>bitset</h3></div></div></div><div class="section" title="Size Variable"><div class="titlepage"><div><div><h4 class="title"><a name="associative.bitset.size_variable"></a>Size Variable</h4></div></div></div><p>
  96         No, you cannot write code of the form
  97       </p><pre class="programlisting">
  98       #include &lt;bitset&gt;
  99
 100       void foo (size_t n)
 101       {
 102           std::bitset&lt;n&gt;   bits;
 103           ....
 104       }
 105    </pre><p>
 106      because <code class="code">n</code> must be known at compile time.  Your
 107      compiler is correct; it is not a bug.  That's the way templates
 108      work.  (Yes, it <span class="emphasis"><em>is</em></span> a feature.)
 109    </p><p>
 110      There are a couple of ways to handle this kind of thing.  Please
 111      consider all of them before passing judgement.  They include, in
 112      no chaptericular order:
 113    </p><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>A very large N in <code class="code">bitset&lt;N&gt;</code>.</p></li><li class="listitem"><p>A container&lt;bool&gt;.</p></li><li class="listitem"><p>Extremely weird solutions.</p></li></ul></div><p>
 114      <span class="emphasis"><em>A very large N in
 115      <code class="code">bitset&lt;N&gt;</code>.  </em></span> It has been
 116      pointed out a few times in newsgroups that N bits only takes up
 117      (N/8) bytes on most systems, and division by a factor of eight is
 118      pretty impressive when speaking of memory.  Half a megabyte given
 119      over to a bitset (recall that there is zero space overhead for
 120      housekeeping info; it is known at compile time exactly how large
 121      the set is) will hold over four million bits.  If you're using
 122      those bits as status flags (e.g.,
 123      <span class="quote">“<span class="quote">changed</span>”</span>/<span class="quote">“<span class="quote">unchanged</span>”</span> flags), that's a
 124      <span class="emphasis"><em>lot</em></span> of state.
 125    </p><p>
 126      You can then keep track of the <span class="quote">“<span class="quote">maximum bit used</span>”</span>
 127      during some testing runs on representative data, make note of how
 128      many of those bits really need to be there, and then reduce N to
 129      a smaller number.  Leave some extra space, of course.  (If you
 130      plan to write code like the incorrect example above, where the
 131      bitset is a local variable, then you may have to talk your
 132      compiler into allowing that much stack space; there may be zero
 133      space overhead, but it's all allocated inside the object.)
 134    </p><p>
 135      <span class="emphasis"><em>A container&lt;bool&gt;.  </em></span> The
 136      Committee made provision for the space savings possible with that
 137      (N/8) usage previously mentioned, so that you don't have to do
 138      wasteful things like <code class="code">Container&lt;char&gt;</code> or
 139      <code class="code">Container&lt;short int&gt;</code>.  Specifically,
 140      <code class="code">vector&lt;bool&gt;</code> is required to be specialized for
 141      that space savings.
 142    </p><p>
 143      The problem is that <code class="code">vector&lt;bool&gt;</code> doesn't
 144      behave like a normal vector anymore.  There have been
 145      journal articles which discuss the problems (the ones by Herb
 146      Sutter in the May and July/August 1999 issues of C++ Report cover
 147      it well).  Future revisions of the ISO C++ Standard will change
 148      the requirement for <code class="code">vector&lt;bool&gt;</code>
 149      specialization.  In the meantime, <code class="code">deque&lt;bool&gt;</code>
 150      is recommended (although its behavior is sane, you probably will
 151      not get the space savings, but the allocation scheme is different
 152      than that of vector).
 153    </p><p>
 154      <span class="emphasis"><em>Extremely weird solutions.  </em></span> If
 155      you have access to the compiler and linker at runtime, you can do
 156      something insane, like figuring out just how many bits you need,
 157      then writing a temporary source code file.  That file contains an
 158      instantiation of <code class="code">bitset</code> for the required number of
 159      bits, inside some wrapper functions with unchanging signatures.
 160      Have your program then call the compiler on that file using
 161      Position Independent Code, then open the newly-created object
 162      file and load those wrapper functions.  You'll have an
 163      instantiation of <code class="code">bitset&lt;N&gt;</code> for the exact
 164      <code class="code">N</code> that you need at the time.  Don't forget to delete
 165      the temporary files.  (Yes, this <span class="emphasis"><em>can</em></span> be, and
 166      <span class="emphasis"><em>has been</em></span>, done.)
 167    </p><p>
 168      This would be the approach of either a visionary genius or a
 169      raving lunatic, depending on your programming and management
 170      style.  Probably the latter.
 171    </p><p>
 172      Which of the above techniques you use, if any, are up to you and
 173      your intended application.  Some time/space profiling is
 174      indicated if it really matters (don't just guess).  And, if you
 175      manage to do anything along the lines of the third category, the
 176      author would love to hear from you...
 177    </p><p>
 178      Also note that the implementation of bitset used in libstdc++ has
 179      <a class="link" href="ext_containers.html#manual.ext.containers.sgi" title="Backwards Compatibility">some extensions</a>.
 180    </p></div><div class="section" title="Type String"><div class="titlepage"><div><div><h4 class="title"><a name="associative.bitset.type_string"></a>Type String</h4></div></div></div><p>
 181       </p><p>
 182      Bitmasks do not take char* nor const char* arguments in their
 183      constructors.  This is something of an accident, but you can read
 184      about the problem: follow the library's <span class="quote">“<span class="quote">Links</span>”</span> from
 185      the homepage, and from the C++ information <span class="quote">“<span class="quote">defect
 186      reflector</span>”</span> link, select the library issues list.  Issue
 187      number 116 describes the problem.
 188    </p><p>
 189      For now you can simply make a temporary string object using the
 190      constructor expression:
 191    </p><pre class="programlisting">
 192       std::bitset&lt;5&gt; b ( std::string(<span class="quote">“<span class="quote">10110</span>”</span>) );
 193    </pre><p>
 194      instead of
 195    </p><pre class="programlisting">
 196       std::bitset&lt;5&gt; b ( <span class="quote">“<span class="quote">10110</span>”</span> );    // invalid
 197     </pre></div></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="containers.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="containers.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="containers_and_c.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 9.
 198   Containers
 199
 200  </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Interacting with C</td></tr></table></div></body></html>