1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
6 <meta name="generator" content=
7 "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
9 <title>container_base Interface</title>
10 <meta http-equiv="Content-Type" content=
11 "text/html; charset=us-ascii" />
16 <h1><tt>container_base</tt> Interface</h1>
18 <p>An abstract basic associative container.</p>
20 <p>Defined in: <a href=
21 "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/include/ext/pb_ds/assoc_container.hpp"><tt>assoc_container.hpp</tt></a></p>
23 <h2><a name="link1" id="link1">Template Parameters</a></h2>
25 <table class="c1" width="100%" border="1" summary=
26 "Template Parameters">
28 <td width="20%" align="left"><b>Parameter</b></td>
30 <td width="50%" align="left"><b>Description</b></td>
32 <td width="30%" align="left"><b>Default Value</b></td>
38 <a name="Key2501" id="Key2501"><b>typename</b> Key</a>
52 <a name="Mapped318655" id="Mapped318655"><b>typename</b> Mapped</a>
66 <a name="Tag278938" id="Tag278938"><b>class</b> Tag</a>
71 <p>Data structure tag.</p>
80 <a name="Policy_Tl42017403" id=
81 "Policy_Tl42017403"><b>class</b> Policy_Tl</a>
86 <p>Policy typelist.</p>
88 <p>Contains subclasses' policies.</p>
97 <a name="Allocator35940069" id=
98 "Allocator35940069"><b>class</b> Allocator</a>
103 <p>Allocator type.</p>
110 <h2><a name="link2" id="link2">Public Types and
113 <h3><a name="link3" id="link3">General Container
116 <table class="c1" width="100%" border="1" summary="Types">
118 <td width="30%" align="left"><b>Type</b></td>
120 <td width="55%" align="left"><b>Definition</b></td>
122 <td width="15%" align="left"><b>Description</b></td>
128 <a name="size_type55424436" id="size_type55424436">size_type</a>
134 <b>typename</b> <a href=
135 "#Allocator35940069"><tt>Allocator</tt></a>::size_type
147 <a name="difference_type868028452" id=
148 "difference_type868028452">difference_type</a>
154 <b>typename</b> <a href=
155 "#Allocator35940069"><tt>Allocator</tt></a>::difference_type
160 <p>Difference type.</p>
165 <h3><a name="link4" id="link4">Categories</a></h3>
167 <table class="c1" width="100%" border="1" summary="Types">
169 <td width="30%" align="left"><b>Type</b></td>
171 <td width="55%" align="left"><b>Definition</b></td>
173 <td width="15%" align="left"><b>Description</b></td>
179 <a name="container_category1247973216" id=
180 "container_category1247973216">container_category</a>
186 <a href="#Tag278938"><tt>Tag</tt></a>
191 <p>The underlying mapped-structure tag of the
194 <p>This is one of:</p>
197 <li><a href="cc_hash_tag.html"><span class=
198 "c2"><tt>cc_hash_tag</tt></span></a></li>
200 <li><a href="gp_hash_tag.html"><span class=
201 "c2"><tt>gp_hash_tag</tt></span></a></li>
203 <li><a href="rb_tree_tag.html"><span class=
204 "c2"><tt>rb_tree_tag</tt></span></a></li>
206 <li><a href="ov_tree_tag.html"><span class=
207 "c2"><tt>ov_tree_tag</tt></span></a></li>
209 <li><a href="splay_tree_tag.html"><span class=
210 "c2"><tt>splay_tree_tag</tt></span></a></li>
212 <li><a href="pat_trie_tag.html"><span class=
213 "c2"><tt>pat_trie_tag</tt></span></a></li>
215 <li><a href="list_update_tag.html"><span class=
216 "c2"><tt>list_update_tag</tt></span></a></li>
222 <h3><a name="link5" id="link5">Policy Definitions</a></h3>
224 <table class="c1" width="100%" border="1" summary="Types">
226 <td width="30%" align="left"><b>Type</b></td>
228 <td width="55%" align="left"><b>Definition</b></td>
230 <td width="15%" align="left"><b>Description</b></td>
236 <a name="allocator48440069" id="allocator48440069">allocator</a>
242 <a href="#Allocator35940069"><tt>Allocator</tt></a>
247 <p><a href="#Allocator35940069"><tt>Allocator</tt></a>
253 <h3><a name="link6" id="link6">Key-Type Definitions</a></h3>
255 <table class="c1" width="100%" border="1" summary="Types">
257 <td width="30%" align="left"><b>Type</b></td>
259 <td width="55%" align="left"><b>Definition</b></td>
261 <td width="15%" align="left"><b>Description</b></td>
267 <a name="key_type10393186" id="key_type10393186">key_type</a>
273 <b>typename</b> <a href=
274 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
275 <a href="#Key2501"><tt>Key</tt></a>>::other::value_type
280 <p><a href="#Key2501"><tt>Key</tt></a> type.</p>
287 <a name="key_reference2411522399" id=
288 "key_reference2411522399">key_reference</a>
294 <b>typename</b> <a href=
295 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
297 "#key_type10393186"><tt>key_type</tt></a>>::other::reference
302 <p><a href="#Key2501"><tt>Key</tt></a> reference
310 <a name="const_key_reference3185471705" id=
311 "const_key_reference3185471705">const_key_reference</a>
317 <b>typename</b> <a href=
318 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
320 "#key_type10393186"><tt>key_type</tt></a>>::other::const_reference
325 <p>Const key reference type.</p>
332 <a name="key_pointer1299054769" id=
333 "key_pointer1299054769">key_pointer</a>
339 <b>typename</b> <a href=
340 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
342 "#key_type10393186"><tt>key_type</tt></a>>::other::pointer
347 <p><a href="#Key2501"><tt>Key</tt></a> pointer type.</p>
354 <a name="const_key_pointer3735194427" id=
355 "const_key_pointer3735194427">const_key_pointer</a>
361 <b>typename</b> <a href=
362 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
364 "#key_type10393186"><tt>key_type</tt></a>>::other::const_pointer
369 <p>Const key pointer type.</p>
374 <h3><a name="link7" id="link7">Mapped-Type Definitions</a></h3>
376 <table class="c1" width="100%" border="1" summary="Types">
378 <td width="30%" align="left"><b>Type</b></td>
380 <td width="55%" align="left"><b>Definition</b></td>
382 <td width="15%" align="left"><b>Description</b></td>
388 <a name="mapped_type1308374436" id=
389 "mapped_type1308374436">mapped_type</a>
395 <a href="#Mapped318655"><tt>Mapped</tt></a>
400 <p><a href="#Mapped318655"><tt>Mapped</tt></a> type.</p>
407 <a name="mapped_reference4153801225" id=
408 "mapped_reference4153801225">mapped_reference</a>
414 <b>typename</b> <a href=
415 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
417 "#mapped_type1308374436"><tt>mapped_type</tt></a>>::other::reference
422 <p><a href="#Mapped318655"><tt>Mapped</tt></a> reference
430 <a name="const_mapped_reference2113216667" id=
431 "const_mapped_reference2113216667">const_mapped_reference</a>
437 <b>typename</b> <a href=
438 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
440 "#mapped_type1308374436"><tt>mapped_type</tt></a>>::other::const_reference
445 <p>Const mapped reference type.</p>
452 <a name="mapped_pointer337953771" id=
453 "mapped_pointer337953771">mapped_pointer</a>
459 <b>typename</b> <a href=
460 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
462 "#mapped_type1308374436"><tt>mapped_type</tt></a>>::other::pointer
467 <p><a href="#Mapped318655"><tt>Mapped</tt></a> pointer
475 <a name="const_mapped_pointer4207700301" id=
476 "const_mapped_pointer4207700301">const_mapped_pointer</a>
482 <b>typename</b> <a href=
483 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
485 "#mapped_type1308374436"><tt>mapped_type</tt></a>>::other::const_pointer
490 <p>Const mapped pointer type.</p>
495 <h3><a name="link8" id="link8">Value-Type Definitions</a></h3>
497 <table class="c1" width="100%" border="1" summary="Types">
499 <td width="30%" align="left"><b>Type</b></td>
501 <td width="55%" align="left"><b>Definition</b></td>
503 <td width="15%" align="left"><b>Description</b></td>
509 <a name="value_type279018186" id=
510 "value_type279018186">value_type</a>
517 If <a href="#Mapped318655"><tt>Mapped</tt></a> is <a href=
518 "null_mapped_type.html"><span class=
519 "c2"><tt>null_mapped_type</tt></span></a>, then <a href=
520 "#Key2501"><tt>Key</tt></a><br />
521 Otherwise, <a href="#Mapped318655"><tt>Mapped</tt></a>
533 <a name="reference54418471" id="reference54418471">reference</a>
539 <b>typename</b> <a href=
540 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
542 "#value_type279018186"><tt>value_type</tt></a>>::other::reference
547 <p>Value reference type.</p>
554 <a name="const_reference495461441" id=
555 "const_reference495461441">const_reference</a>
561 <b>typename</b> <a href=
562 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
564 "#value_type279018186"><tt>value_type</tt></a>>::other::const_reference
569 <p>Const value <a href=
570 "#reference54418471"><tt>reference</tt></a> type.</p>
577 <a name="pointer2179769" id="pointer2179769">pointer</a>
583 <b>typename</b> <a href=
584 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
586 "#value_type279018186"><tt>value_type</tt></a>>::other::pointer
591 <p>Value pointer type.</p>
598 <a name="const_pointer878814947" id=
599 "const_pointer878814947">const_pointer</a>
605 <b>typename</b> <a href=
606 "#allocator48440069"><tt>allocator</tt></a>::<b>template</b> rebind<
608 "#value_type279018186"><tt>value_type</tt></a>>::other::const_pointer
613 <p>Const Value <a href=
614 "#pointer2179769"><tt>pointer</tt></a> type.</p>
619 <h3><a name="link9" id="link9">Iterator Definitions</a></h3>
621 <table class="c1" width="100%" border="1" summary="Types">
623 <td width="30%" align="left"><b>Type</b></td>
625 <td width="55%" align="left"><b>Definition</b></td>
627 <td width="15%" align="left"><b>Description</b></td>
633 <a name="const_point_iterator2364676009" id=
634 "const_point_iterator2364676009">const_point_iterator</a>
640 Const point-type iterator.
645 <p>Const point-type iterator.</p>
652 <a name="point_iterator2789896775" id=
653 "point_iterator2789896775">point_iterator</a>
660 Point-type iterator.<br />
661 If <a href="#Mapped318655"><tt>Mapped</tt></a> is <a href=
662 "null_mapped_type.html"><span class=
663 "c2"><tt>null_mapped_type</tt></span></a>, then this is synonymous to <a href="#const_point_iterator2364676009"><tt>const_point_iterator</tt></a>
668 <p>Point-type iterator.</p>
675 <a name="const_iterator98626788" id=
676 "const_iterator98626788">const_iterator</a>
682 Const range-type iterator.
687 <p>Const range-type iterator.</p>
694 <a name="iterator10418194" id="iterator10418194">iterator</a>
701 Range-type iterator.<br />
702 If <a href="#Mapped318655"><tt>Mapped</tt></a> is <a href=
703 "null_mapped_type.html"><span class=
704 "c2"><tt>null_mapped_type</tt></span></a>, then this is synonymous to <a href="#const_iterator98626788"><tt>const_iterator</tt></a>
709 <p>Range-type iterator.</p>
714 <h2><a name="link10" id="link10">Public Methods</a></h2>
716 <h3><a name="link11" id="link11">Constructors, Destructor, and
719 <table class="c1" width="100%" border="1" summary="Methods">
721 <td width="45%" align="left"><b>Method</b></td>
723 <td width="55%" align="left"><b>Description</b></td>
741 <h3><a name="link12" id="link12">Information Methods</a></h3>
743 <table class="c1" width="100%" border="1" summary="Methods">
745 <td width="45%" align="left"><b>Method</b></td>
747 <td width="55%" align="left"><b>Description</b></td>
753 <b>inline</b> <a href="#size_type55424436"><tt>size_type</tt></a>
760 <p>Returns the number of distinct <a href=
761 "#value_type279018186"><tt>value_type</tt></a> objects
762 the container object is storing.</p>
769 <b>inline</b> <a href="#size_type55424436"><tt>size_type</tt></a>
776 <p>Returns an upper bound on the number of distinct
777 <a href="#value_type279018186"><tt>value_type</tt></a>
778 objects this container can store.</p>
785 <b>inline</b> <b>bool</b>
792 <p>Returns whether the container object is not storing
794 "#value_type279018186"><tt>value_type</tt></a>
800 <h3><a name="link13" id="link13">Insert Methods</a></h3>
802 <table class="c1" width="100%" border="1" summary="Methods">
804 <td width="45%" align="left"><b>Method</b></td>
806 <td width="55%" align="left"><b>Description</b></td>
812 std::pair<<a href=
813 "#point_iterator2789896775"><tt>point_iterator</tt></a>, <b>bool</b>>
816 "#const_reference495461441"><tt>const_reference</tt></a> r_val)
821 <p>Inserts a <a href=
822 "#value_type279018186"><tt>value_type</tt></a> object. If
823 no <a href="#value_type279018186"><tt>value_type</tt></a>
824 with <span class="c1"><tt>r_val</tt></span>'s key was in
825 the container object, inserts and returns (<a href=
826 "#point_iterator2789896775"><tt>point_iterator</tt></a>
827 object associated with <span class=
828 "c1"><tt>r_val</tt></span>, <tt><b>true</b></tt>);
829 otherwise just returns (<a href=
830 "#point_iterator2789896775"><tt>point_iterator</tt></a>
831 object associated with <span class=
832 "c1"><tt>r_val</tt></span>'s key,
833 <tt><b>false</b></tt>).</p>
840 <a href="#mapped_reference4153801225"><tt>mapped_reference</tt></a>
843 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
848 <p>Subscript operator.</p>
853 <h3><a name="link14" id="link14">Find Methods</a></h3>
855 <table class="c1" width="100%" border="1" summary="Methods">
857 <td width="45%" align="left"><b>Method</b></td>
859 <td width="55%" align="left"><b>Description</b></td>
865 <a href="#point_iterator2789896775"><tt>point_iterator</tt></a>
868 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
873 <p>Returns the <a href=
874 "#point_iterator2789896775"><tt>point_iterator</tt></a>
875 corresponding to the <a href=
876 "#value_type279018186"><tt>value_type</tt></a> with
877 <span class="c1"><tt>r_key</tt></span> as its key, or the
879 "#point_iterator2789896775"><tt>point_iterator</tt></a>
880 corresponding to the just-after-last entry if no such
882 "#value_type279018186"><tt>value_type</tt></a>.</p>
890 "#const_point_iterator2364676009"><tt>const_point_iterator</tt></a>
893 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
898 <p>Returns the <a href=
899 "#const_point_iterator2364676009"><tt>const_point_iterator</tt></a>
900 corresponding to the <a href=
901 "#value_type279018186"><tt>value_type</tt></a> with
902 <span class="c1"><tt>r_key</tt></span> as its key, or the
904 "#const_point_iterator2364676009"><tt>const_point_iterator</tt></a>
905 corresponding to the just-after-last entry if no such
907 "#value_type279018186"><tt>value_type</tt></a>.</p>
912 <h3><a name="link15" id="link15">Erase Methods</a></h3>
914 <table class="c1" width="100%" border="1" summary="Methods">
916 <td width="45%" align="left"><b>Method</b></td>
918 <td width="55%" align="left"><b>Description</b></td>
927 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
932 <p>Erases the <a href=
933 "#value_type279018186"><tt>value_type</tt></a> associated
934 with <span class="c1"><tt>r_key</tt></span>. returns
935 <tt><b>false</b></tt> iff <span class=
936 "c1"><tt>r_key</tt></span> was not contained.</p>
944 <b>class</b> Pred>
945 <a href="#size_type55424436"><tt>size_type</tt></a>
952 <p>Erases any <a href=
953 "#value_type279018186"><tt>value_type</tt></a> satisfying
954 the predicate <span class="c1"><tt>prd</tt></span> (this
955 is transactional, either all matching <a href=
956 "#value_type279018186"><tt>value_type</tt></a>s are
957 erased, or, if an exception is thrown (for types whose
958 erase can throw an exception) none); returns the number
960 "#value_type279018186"><tt>value_type</tt></a>s
975 <p>Clears the container object.</p>
980 <h3><a name="link16" id="link16">Iteration Methods</a></h3>
982 <table class="c1" width="100%" border="1" summary="Methods">
984 <td width="45%" align="left"><b>Method</b></td>
986 <td width="55%" align="left"><b>Description</b></td>
992 <a href="#iterator10418194"><tt>iterator</tt></a>
999 <p>Returns an <a href=
1000 "#iterator10418194"><tt>iterator</tt></a> corresponding
1001 to the first <a href=
1002 "#value_type279018186"><tt>value_type</tt></a> in the
1010 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>
1017 <p>Returns a <a href=
1018 "#const_iterator98626788"><tt>const_iterator</tt></a>
1019 corresponding to the first <a href=
1020 "#value_type279018186"><tt>value_type</tt></a> in the
1028 <a href="#iterator10418194"><tt>iterator</tt></a>
1035 <p>Returns an <a href=
1036 "#iterator10418194"><tt>iterator</tt></a> corresponding
1037 to the just-after-last <a href=
1038 "#value_type279018186"><tt>value_type</tt></a> in the
1046 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>
1053 <p>Returns a <a href=
1054 "#const_iterator98626788"><tt>const_iterator</tt></a>
1055 corresponding to the just-after-last <a href=
1056 "#value_type279018186"><tt>value_type</tt></a> in the