
BoostCommit : 
From: danieljames_at_[hidden]
Date: 20070531 18:33:39
Author: danieljames
Date: 20070531 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 20070531 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 20070531 18:33:39 EDT (Thu, 31 May 2007)
@@ 5,6 +5,9 @@
[def __tr1__
[@http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2006/n2009.pdf
C++ Standard Library Technical Report]]
+[def __boosttr1__
+ [@http://www.boost.org/doc/html/boost_tr1.html
+ Boost.TR1]]
[def __draft__
[@http://www.openstd.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
__hashtable__ 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 __boosttr1__.
+
+`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:
BoostCommit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk