<li><a href="#dss_other">Other Sequential Container Options</a></li>
</ul></li>
<li><a href="#ds_string">String-like containers</a>
- <!--<ul>
- todo
- </ul>--></li>
+ <ul>
+ <li><a href="#dss_stringref">llvm/ADT/StringRef.h</a></li>
+ <li><a href="#dss_twine">llvm/ADT/Twine.h</a></li>
+ <li><a href="#dss_smallstring">llvm/ADT/SmallString.h</a></li>
+ <li><a href="#dss_stdstring">std::string</a></li>
+ </ul></li>
<li><a href="#ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
<ul>
<li><a href="#dss_sortedvectorset">A sorted 'vector'</a></li>
<li><a href="#dss_smallset">"llvm/ADT/SmallSet.h"</a></li>
<li><a href="#dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a></li>
<li><a href="#dss_denseset">"llvm/ADT/DenseSet.h"</a></li>
+ <li><a href="#dss_sparseset">"llvm/ADT/SparseSet.h"</a></li>
<li><a href="#dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a></li>
<li><a href="#dss_set"><set></a></li>
<li><a href="#dss_setvector">"llvm/ADT/SetVector.h"</a></li>
<li><a href="#dss_uniquevector">"llvm/ADT/UniqueVector.h"</a></li>
- <li><a href="#dss_otherset">Other Set-Like ContainerOptions</a></li>
+ <li><a href="#dss_immutableset">"llvm/ADT/ImmutableSet.h"</a></li>
+ <li><a href="#dss_otherset">Other Set-Like Container Options</a></li>
</ul></li>
<li><a href="#ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
<ul>
<li><a href="#dss_intervalmap">"llvm/ADT/IntervalMap.h"</a></li>
<li><a href="#dss_map"><map></a></li>
<li><a href="#dss_inteqclasses">"llvm/ADT/IntEqClasses.h"</a></li>
+ <li><a href="#dss_immutablemap">"llvm/ADT/ImmutableMap.h"</a></li>
<li><a href="#dss_othermap">Other Map-Like Container Options</a></li>
</ul></li>
<li><a href="#ds_bit">BitVector-like containers</a>
. Doing so avoids (relatively) expensive malloc/free calls, which dwarf the
cost of adding the elements to the container. </p>
-</div>
-
-
<!-- ======================================================================= -->
<h3>
<a name="ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
<pre>
for ( ... ) {
std::vector<foo> V;
- use V;
+ // make use of V.
}
</pre>
</div>
<pre>
std::vector<foo> V;
for ( ... ) {
- use V;
+ // make use of V.
V.clear();
}
</pre>
method if the method "computes" the result string. Instead, use
std::string.</li>
-<li>StringRef's allow you to mutate the pointed-to string bytes, but because it
-doesn't own the string, it doesn't allow you to insert or remove bytes from
-the range. For editing operations like this, it interoperates with the
-<a href="#dss_twine">Twine</a> class.</li>
+<li>StringRef's do not allow you to mutate the pointed-to string bytes and it
+doesn't allow you to insert or remove bytes from the range. For editing
+operations like this, it interoperates with the <a
+href="#dss_twine">Twine</a> class.</li>
</ol>
<p>Because of its strengths and limitations, it is very common for a function to
</div>
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_sparseset">"llvm/ADT/SparseSet.h"</a>
+</h4>
+
+<div>
+
+<p>SparseSet holds a small number of objects identified by unsigned keys of
+moderate size. It uses a lot of memory, but provides operations that are
+almost as fast as a vector. Typical keys are physical registers, virtual
+registers, or numbered basic blocks.</p>
+
+<p>SparseSet is useful for algorithms that need very fast clear/find/insert/erase
+and fast iteration over small sets. It is not intended for building composite
+data structures.</p>
+
+</div>
+
<!-- _______________________________________________________________________ -->
<h4>
<a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
faster.
</p>
-<p>SetVector is an adapter class that defaults to using std::vector and std::set
-for the underlying containers, so it is quite expensive. However,
-<tt>"llvm/ADT/SetVector.h"</tt> also provides a SmallSetVector class, which
-defaults to using a SmallVector and SmallSet of a specified size. If you use
-this, and if your sets are dynamically smaller than N, you will save a lot of
-heap traffic.</p>
+<p><tt>SetVector</tt> is an adapter class that defaults to
+ using <tt>std::vector</tt> and a size 16 <tt>SmallSet</tt> for the underlying
+ containers, so it is quite expensive. However,
+ <tt>"llvm/ADT/SetVector.h"</tt> also provides a <tt>SmallSetVector</tt>
+ class, which defaults to using a <tt>SmallVector</tt> and <tt>SmallSet</tt>
+ of a specified size. If you use this, and if your sets are dynamically
+ smaller than <tt>N</tt>, you will save a lot of heap traffic.</p>
</div>
</div>
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_immutableset">"llvm/ADT/ImmutableSet.h"</a>
+</h4>
+
+<div>
+
+<p>
+ImmutableSet is an immutable (functional) set implementation based on an AVL
+tree.
+Adding or removing elements is done through a Factory object and results in the
+creation of a new ImmutableSet object.
+If an ImmutableSet already exists with the given contents, then the existing one
+is returned; equality is compared with a FoldingSetNodeID.
+The time and space complexity of add or remove operations is logarithmic in the
+size of the original set.
+
+<p>
+There is no method for returning an element of the set, you can only check for
+membership.
+
+</div>
+
<!-- _______________________________________________________________________ -->
<h4>
<p>
There are several aspects of DenseMap that you should be aware of, however. The
-iterators in a densemap are invalidated whenever an insertion occurs, unlike
+iterators in a DenseMap are invalidated whenever an insertion occurs, unlike
map. Also, because DenseMap allocates space for a large number of key/value
pairs (it starts with 64 by default), it will waste a lot of space if your keys
or values are large. Finally, you must implement a partial specialization of
is required to tell DenseMap about two special marker values (which can never be
inserted into the map) that it needs internally.</p>
+<p>
+DenseMap's find_as() method supports lookup operations using an alternate key
+type. This is useful in cases where the normal key type is expensive to
+construct, but cheap to compare against. The DenseMapInfo is responsible for
+defining the appropriate comparison and hashing methods for each alternate
+key type used.
+</p>
+
</div>
<!-- _______________________________________________________________________ -->
</div>
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_immutablemap">"llvm/ADT/ImmutableMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+ImmutableMap is an immutable (functional) map implementation based on an AVL
+tree.
+Adding or removing elements is done through a Factory object and results in the
+creation of a new ImmutableMap object.
+If an ImmutableMap already exists with the given key set, then the existing one
+is returned; equality is compared with a FoldingSetNodeID.
+The time and space complexity of add or remove operations is logarithmic in the
+size of the original map.
+
+</div>
+
<!-- _______________________________________________________________________ -->
<h4>
<a name="dss_othermap">Other Map-Like Container Options</a>
projects / oota-llvm.git / blobdiff