From 6aed5afbbb43d9909bab1818b560dda45fc9121a Mon Sep 17 00:00:00 2001 From: Artyom Skrobov Date: Tue, 19 May 2015 10:21:12 +0000 Subject: [PATCH] Fix documentation for Set-Like Containers git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@237677 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/ProgrammersManual.rst | 36 ++++++++++++++++++++++++++---------- 1 file changed, 26 insertions(+), 10 deletions(-) diff --git a/docs/ProgrammersManual.rst b/docs/ProgrammersManual.rst index 6a4c22a692d..ceb39e18efd 100644 --- a/docs/ProgrammersManual.rst +++ b/docs/ProgrammersManual.rst @@ -1105,10 +1105,10 @@ If you have a set-like data structure that is usually small and whose elements are reasonably small, a ``SmallSet`` is a good choice. This set has space for N elements in place (thus, if the set is dynamically smaller than N, no malloc traffic is required) and accesses them with a simple linear search. -When the set grows beyond 'N' elements, it allocates a more expensive +When the set grows beyond N elements, it allocates a more expensive representation that guarantees efficient access (for most types, it falls back -to std::set, but for pointers it uses something far better, :ref:`SmallPtrSet -`. +to :ref:`std::set `, but for pointers it uses something far better, +:ref:`SmallPtrSet `. The magic of this class is that it handles small sets extremely efficiently, but gracefully handles extremely large sets without loss of efficiency. The @@ -1120,16 +1120,31 @@ and erasing, but does not support iteration. llvm/ADT/SmallPtrSet.h ^^^^^^^^^^^^^^^^^^^^^^ -SmallPtrSet has all the advantages of ``SmallSet`` (and a ``SmallSet`` of +``SmallPtrSet`` has all the advantages of ``SmallSet`` (and a ``SmallSet`` of pointers is transparently implemented with a ``SmallPtrSet``), but also supports -iterators. If more than 'N' insertions are performed, a single quadratically +iterators. If more than N insertions are performed, a single quadratically probed hash table is allocated and grows as needed, providing extremely efficient access (constant time insertion/deleting/queries with low constant factors) and is very stingy with malloc traffic. -Note that, unlike ``std::set``, the iterators of ``SmallPtrSet`` are invalidated -whenever an insertion occurs. Also, the values visited by the iterators are not -visited in sorted order. +Note that, unlike :ref:`std::set `, the iterators of ``SmallPtrSet`` +are invalidated whenever an insertion occurs. Also, the values visited by the +iterators are not visited in sorted order. + +.. _dss_stringset: + +llvm/ADT/StringSet.h +^^^^^^^^^^^^^^^^^^^^ + +``StringSet`` is a thin wrapper around :ref:`StringMap\ `, +and it allows efficient storage and retrieval of unique strings. + +Functionally analogous to ``SmallSet``, ``StringSet`` also suports +iteration. (The iterator dereferences to a ``StringMapEntry``, so you +need to call ``i->getKey()`` to access the item of the StringSet.) On the +other hand, ``StringSet`` doesn't support range-insertion and +copy-construction, which :ref:`SmallSet ` and :ref:`SmallPtrSet +` do support. .. _dss_denseset: @@ -1297,8 +1312,9 @@ never use hash_set and unordered_set because they are generally very expensive (each insertion requires a malloc) and very non-portable. std::multiset is useful if you're not interested in elimination of duplicates, -but has all the drawbacks of std::set. A sorted vector (where you don't delete -duplicate entries) or some other approach is almost always better. +but has all the drawbacks of :ref:`std::set `. A sorted vector +(where you don't delete duplicate entries) or some other approach is almost +always better. .. _ds_map: -- 2.34.1