[Boost-commit] svn:boost r4407

From: danieljames_at_[hidden]
Date: 2007-05-31 18:33:39

Author: danieljames
Date: 2007-05-31 18:33:39 EDT (Thu, 31 May 2007)
New Revision: 4407
URL: http://svn.boost.org/trac/boost/changeset/4407

Log:
Trying to make the unordered documentation a little better.

Text files modified: 
   sandbox/unordered/libs/unordered/doc/buckets.qbk |    25 ++++++-----                             
   sandbox/unordered/libs/unordered/doc/intro.qbk   |    83 +++++++++++++++++++++++---------------- 
   2 files changed, 62 insertions(+), 46 deletions(-)

Modified: sandbox/unordered/libs/unordered/doc/buckets.qbk
==============================================================================
--- sandbox/unordered/libs/unordered/doc/buckets.qbk	(original)
+++ sandbox/unordered/libs/unordered/doc/buckets.qbk	2007-05-31 18:33:39 EDT (Thu, 31 May 2007)
@@ -13,23 +13,24 @@
 [$../../libs/unordered/doc/diagrams/buckets.png]
 
 In order to decide which bucket to place an element in, the container applies
-`Hash` to the element's key (for `unordered_set` and `unordered_multiset` the
-key is the whole element, but this refered to as the key so that the same
-terminology can be used for sets and maps). This gives a `std::size_t`.
-`std::size_t` has a much greater range of values then the number of buckets, so
-that container applies another transformation to that value to choose a bucket
-to place the element in.
+the hash function, `Hash`, to the element's key (for `unordered_set` and
+`unordered_multiset` the key is the whole element, but is refered to as the key
+so that the same terminology can be used for sets and maps). This returns a
+value of type `std::size_t`.  `std::size_t` has a much greater range of values
+then the number of buckets, so that container applies another transformation to
+that value to choose a bucket to place the element in.
 
 If at a later date the container wants to find an element in the container it
 just has to apply the same process to the element's key to discover which
-bucket to find it in. This means that you only have to look at the elements
-within a single bucket. If the hash function has worked well the elements will
-be evenly distributed amongst the buckets.
+bucket it is in. If the hash function has worked well the elements will be
+evenly distributed amongst the buckets so it will only have to examine a small
+number of elements.
 
 You can see in the diagram that `A` & `D` have been placed in the same bucket.
-This means that when looking in this bucket, up to 2 comparison have to be
-made, making searching slower. This is known as a collision. To keep things
-fast we try to keep these to a minimum.
+This means that when looking for these elements, of another element that would
+be placed in the same bucket, up to 2 comparison have to be made, making
+searching slower. This is known as a collision. To keep things fast we try to
+keep these to a minimum.  
 
 [table Methods for Accessing Buckets
     [[Method] [Description]]

Modified: sandbox/unordered/libs/unordered/doc/intro.qbk
==============================================================================
--- sandbox/unordered/libs/unordered/doc/intro.qbk	(original)
+++ sandbox/unordered/libs/unordered/doc/intro.qbk	2007-05-31 18:33:39 EDT (Thu, 31 May 2007)
@@ -5,6 +5,9 @@
 [def __tr1__ 
     [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2009.pdf
     C++ Standard Library Technical Report]]
+[def __boost-tr1__
+    [@http://www.boost.org/doc/html/boost_tr1.html
+    Boost.TR1]]
 [def __draft__
     [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2009.pdf
     Working Draft of the C++ Standard]]
@@ -15,10 +18,10 @@
 
 [section:intro Introduction]
 
-For accessing data based on keys, the C++ standard library offers `std::set`,
+For accessing data based on key lookup, the C++ standard library offers `std::set`,
 `std::map`, `std::multiset` and `std::multimap`. These are generally
-implemented using balanced binary trees so lookup time has
-logarithmic complexity. Which is generally okay, but in many cases a
+implemented using balanced binary trees so that lookup time has
+logarithmic complexity. That is generally okay, but in many cases a
 __hash-table__ can perform better, as accessing data has constant complexity,
 on average. The worst case complexity is linear, but that occurs rarely and
 with some care, can be avoided.
@@ -30,38 +33,50 @@
 
 So the __tr1__ introduced the unordered associative containers, which are
 implemented using hash tables, and they have now been added to the __draft__.
-There are four containers to match the existing
-associate containers. In the header <[headerref boost/unordered_set.hpp]>:
 
-    template <
-        class Key,
-        class Hash = boost::hash<Key>, 
-        class Pred = std::equal_to<Key>, 
-        class Alloc = std::allocator<Key> > 
-    class ``[classref boost::unordered_set unordered_set]``;
-
-    template<
-        class Key,
-        class Hash = boost::hash<Key>, 
-        class Pred = std::equal_to<Key>, 
-        class Alloc = std::allocator<Key> > 
-    class ``[classref boost::unordered_multiset unordered_multiset]``;
-
-and in <[headerref boost/unordered_map.hpp]>:
-
-    template <
-        class Key, class T,
-        class Hash = boost::hash<Key>, 
-        class Pred = std::equal_to<Key>, 
-        class Alloc = std::allocator<Key> > 
-    class ``[classref boost::unordered_map unordered_map]``;
-
-    template<
-        class Key, class T,
-        class Hash = boost::hash<Key>, 
-        class Pred = std::equal_to<Key>, 
-        class Alloc = std::allocator<Key> > 
-    class ``[classref boost::unordered_multimap unordered_multimap]``;
+This library supplies a standards compliant implementation that is proposed for
+addition to boost. If accepted they should also be added to __boost-tr1__.
+
+`unordered_set` and `unordered_multiset` are defined in the header
+<[headerref boost/unordered_set.hpp]>
+
+    namespace boost {
+        template <
+            class Key,
+            class Hash = boost::hash<Key>, 
+            class Pred = std::equal_to<Key>, 
+            class Alloc = std::allocator<Key> > 
+        class ``[classref boost::unordered_set unordered_set]``;
+
+        template<
+            class Key,
+            class Hash = boost::hash<Key>, 
+            class Pred = std::equal_to<Key>, 
+            class Alloc = std::allocator<Key> > 
+        class ``[classref boost::unordered_multiset unordered_multiset]``;
+    }
+
+`unordered_map` and `unordered_multimap` are defined in the header
+<[headerref boost/unordered_map.hpp]>
+
+    namespace boost {
+        template <
+            class Key, class T,
+            class Hash = boost::hash<Key>,
+            class Pred = std::equal_to<Key>,
+            class Alloc = std::allocator<Key> >
+        class ``[classref boost::unordered_map unordered_map]``;
+
+        template<
+            class Key, class T,
+            class Hash = boost::hash<Key>,
+            class Pred = std::equal_to<Key>,
+            class Alloc = std::allocator<Key> >
+        class ``[classref boost::unordered_multimap unordered_multimap]``;
+    }
+
+If using Boost.TR1, these classes will be included from `<unordered_set>` and
+`<unordered_map>`, with the classes included in the `std::tr1` namespace.
 
 The containers are used in a similar manner to the normal associative
 containers: