|
|
Boost-Commit : |
From: john_at_[hidden]
Date: 2008-08-05 06:42:04
Author: johnmaddock
Date: 2008-08-05 06:42:03 EDT (Tue, 05 Aug 2008)
New Revision: 47988
URL: http://svn.boost.org/trac/boost/changeset/47988
Log:
Added support for the unordered containers.
Added:
trunk/libs/tr1/test/cyclic_depend/unordered_map.cpp (contents, props changed)
trunk/libs/tr1/test/cyclic_depend/unordered_set.cpp (contents, props changed)
trunk/libs/tr1/test/test_unordered_map.cpp (contents, props changed)
trunk/libs/tr1/test/test_unordered_set.cpp (contents, props changed)
trunk/libs/tr1/test/unordered_concepts.hpp (contents, props changed)
Text files modified:
trunk/libs/tr1/doc/tr1.qbk | 226 ++++++++++++++++++++++-----------------
1 files changed, 127 insertions(+), 99 deletions(-)
Modified: trunk/libs/tr1/doc/tr1.qbk
==============================================================================
--- trunk/libs/tr1/doc/tr1.qbk (original)
+++ trunk/libs/tr1/doc/tr1.qbk 2008-08-05 06:42:03 EDT (Tue, 05 Aug 2008)
@@ -1337,6 +1337,133 @@
[endsect]
+[section:unordered_set Unordered Associative Set (Hash Table).]
+
+ #include <boost/tr1/unordered_set.hpp>
+
+or
+
+ #include <unordered_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 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.
+
+With this in mind, the C++ Standard Library Technical Report
+introduced the unordered associative containers, which are
+implemented using hash tables, and they have now been added to
+the Working Draft of the C++ Standard.
+
+Refer to the
+[@../../libs/unordered/index.html Unordered Library docs]
+for more information.
+
+ namespace std {
+ namespace tr1 {
+
+ template <class Value,
+ class Hash = hash<Value>,
+ class Pred = std::equal_to<Value>,
+ class Alloc = std::allocator<Value> >
+ class unordered_set;
+
+ // [6.3.4.5] Class template unordered_multiset
+ template <class Value,
+ class Hash = hash<Value>,
+ class Pred = std::equal_to<Value>,
+ class Alloc = std::allocator<Value> >
+ class unordered_multiset;
+
+ template <class Value, class Hash, class Pred, class Alloc>
+ void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
+ unordered_set<Value, Hash, Pred, Alloc>& y);
+
+ template <class Value, class Hash, class Pred, class Alloc>
+ void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
+ unordered_multiset<Value, Hash, Pred, Alloc>& y);
+
+ } // namespace tr1
+ } // namespace std
+
+[*Configuration:]
+[@../../libs/config/index.html Boost.Config] should (automatically) define
+the macro BOOST_HAS_TR1_UNORDERED_SET if your
+standard library implements this part of TR1.
+
+[*Standard Conformity:]
+No known issues for conforming compilers.
+
+[endsect]
+
+[section:unordered_map Unordered Associative Map (Hash Table).]
+
+ #include <boost/tr1/unordered_map.hpp>
+
+or
+
+ #include <unordered_map>
+
+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 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.
+
+With this in mind, the C++ Standard Library Technical Report
+introduced the unordered associative containers, which are
+implemented using hash tables, and they have now been added to
+the Working Draft of the C++ Standard.
+
+Refer to the
+[@../../libs/unordered/index.html Unordered Library docs]
+for more information.
+
+ namespace std {
+ namespace tr1 {
+
+ // [6.3.4.4] Class template unordered_map
+ template <class Key,
+ class T,
+ class Hash = hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<const Key, T> > >
+ class unordered_map;
+
+ // [6.3.4.6] Class template unordered_multimap
+ template <class Key,
+ class T,
+ class Hash = hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<const Key, T> > >
+ class unordered_multimap;
+
+ template <class Key, class T, class Hash, class Pred, class Alloc>
+ void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
+ unordered_map<Key, T, Hash, Pred, Alloc>& y);
+
+ template <class Key, class T, class Hash, class Pred, class Alloc>
+ void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
+ unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
+
+ } // namespace tr1
+ } // namespace std
+
+[*Configuration:]
+[@../../libs/config/index.html Boost.Config] should (automatically) define
+the macro BOOST_HAS_TR1_UNORDERED_MAP if your
+standard library implements this part of TR1.
+
+[*Standard Conformity:]
+No known issues for conforming compilers.
+
+[endsect]
+
[endsect]
[section:unsupported TR By Subject: Unsupported Features]
@@ -1477,105 +1604,6 @@
[endsect]
-[section:unordered_set Unordered Associative Set (Hash Table).]
-
- #include <boost/tr1/unordered_set.hpp>
-
-or
-
- #include <unordered_set>
-
-This is not currently supported by Boost, although that situation is
-hoped to change soon.
-
- namespace std {
- namespace tr1 {
-
- template <class Value,
- class Hash = hash<Value>,
- class Pred = std::equal_to<Value>,
- class Alloc = std::allocator<Value> >
- class unordered_set;
-
- // [6.3.4.5] Class template unordered_multiset
- template <class Value,
- class Hash = hash<Value>,
- class Pred = std::equal_to<Value>,
- class Alloc = std::allocator<Value> >
- class unordered_multiset;
-
- template <class Value, class Hash, class Pred, class Alloc>
- void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
- unordered_set<Value, Hash, Pred, Alloc>& y);
-
- template <class Value, class Hash, class Pred, class Alloc>
- void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
- unordered_multiset<Value, Hash, Pred, Alloc>& y);
-
- } // namespace tr1
- } // namespace std
-
-[*Configuration:]
-[@../../libs/config/index.html Boost.Config] should (automatically) define
-the macro BOOST_HAS_TR1_UNORDERED_SET if your
-standard library implements this part of TR1.
-
-[*Standard Conformity:]
-Not supported.
-
-[endsect]
-
-[section:unordered_map Unordered Associative Map (Hash Table).]
-
- #include <boost/tr1/unordered_map.hpp>
-
-or
-
- #include <unordered_map>
-
-This is not currently supported by Boost, although that situation is
-hoped to change soon.
-
- namespace std {
- namespace tr1 {
-
- // [6.3.4.4] Class template unordered_map
- template <class Key,
- class T,
- class Hash = hash<Key>,
- class Pred = std::equal_to<Key>,
- class Alloc = std::allocator<std::pair<const Key, T> > >
- class unordered_map;
-
- // [6.3.4.6] Class template unordered_multimap
- template <class Key,
- class T,
- class Hash = hash<Key>,
- class Pred = std::equal_to<Key>,
- class Alloc = std::allocator<std::pair<const Key, T> > >
- class unordered_multimap;
-
- template <class Key, class T, class Hash, class Pred, class Alloc>
- void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
- unordered_map<Key, T, Hash, Pred, Alloc>& y);
-
- template <class Key, class T, class Hash, class Pred, class Alloc>
- void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
-
- } // namespace tr1
- } // namespace std
-
-[*Configuration:]
-[@../../libs/config/index.html Boost.Config] should (automatically) define
-the macro BOOST_HAS_TR1_UNORDERED_MAP if your
-standard library implements this part of TR1.
-
-[*Standard Conformity:]
-Not supported.
-
-[endsect]
-
[endsect]
[section:header_list TR1 By Header]
Added: trunk/libs/tr1/test/cyclic_depend/unordered_map.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/tr1/test/cyclic_depend/unordered_map.cpp 2008-08-05 06:42:03 EDT (Tue, 05 Aug 2008)
@@ -0,0 +1,12 @@
+
+// (C) Copyright John Maddock 2008.
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/unordered_map.hpp>
+
+int main()
+{
+ return 0;
+}
\ No newline at end of file
Added: trunk/libs/tr1/test/cyclic_depend/unordered_set.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/tr1/test/cyclic_depend/unordered_set.cpp 2008-08-05 06:42:03 EDT (Tue, 05 Aug 2008)
@@ -0,0 +1,12 @@
+
+// (C) Copyright John Maddock 2008.
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/unordered_set.hpp>
+
+int main()
+{
+ return 0;
+}
\ No newline at end of file
Added: trunk/libs/tr1/test/test_unordered_map.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/tr1/test/test_unordered_map.cpp 2008-08-05 06:42:03 EDT (Tue, 05 Aug 2008)
@@ -0,0 +1,91 @@
+// (C) Copyright John Maddock 2008.
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+// These are the headers included by the Boost.TR1 implementation,
+// by including these directly we probe for problems with cyclic
+// dependencies when the TR1 headers are in the include search path.
+
+#ifdef TEST_STD_HEADERS
+#include <unordered_map>
+#else
+#include <boost/tr1/unordered_map.hpp>
+#endif
+
+#include "unordered_concepts.hpp"
+#include "boost/concept_archetype.hpp"
+
+
+int main()
+{
+ typedef boost::copy_constructible_archetype<boost::assignable_archetype<> > value_type;
+ typedef boost::default_constructible_unary_function_archetype<value_type, std::size_t> func_type;
+ typedef boost::default_constructible_binary_predicate_archetype<value_type, value_type> pred_type;
+ typedef std::tr1::unordered_map<value_type, value_type, func_type, pred_type> hash_map_type;
+ typedef std::tr1::unordered_multimap<value_type, value_type, func_type, pred_type> hash_multimap_type;
+
+ boost::function_requires<boost::UniqueUnorderedContainer<hash_map_type> >();
+ boost::function_requires<boost::MultiUnorderedContainer<hash_multimap_type> >();
+
+ do{
+ // unordered_map specific functions:
+ typedef hash_map_type::key_type key_type;
+ typedef hash_map_type::hasher hasher;
+ typedef hash_map_type::key_equal key_equal;
+ typedef hash_map_type::local_iterator local_iterator;
+ typedef hash_map_type::const_local_iterator const_local_iterator;
+ typedef hash_map_type::value_type value_type;
+ typedef hash_map_type::iterator iterator;
+ typedef hash_map_type::const_iterator const_iterator;
+ typedef hash_map_type::size_type size_type;
+ typedef hash_map_type::allocator_type allocator_type;
+ typedef boost::input_iterator_archetype<value_type> input_iterator;
+ input_iterator i = boost::static_object<input_iterator>::get();
+ input_iterator j = i;
+
+ size_type n = 1;
+ const hasher& hf = boost::static_object<hasher>::get();
+ const key_equal& eq = boost::static_object<key_equal>::get();
+ //value_type const& t = boost::static_object<value_type>::get();
+ //key_type const& k = boost::static_object<key_type>::get();
+ allocator_type const& a = boost::static_object<allocator_type>::get();
+
+ hash_map_type x1(n, hf, eq, a);
+ hash_map_type x2(i, j, n, hf, eq, a);
+ swap(x1, x2);
+ std::tr1::swap(x1, x2);
+ }while(0);
+ do{
+ // unordered_map specific functions:
+ typedef hash_multimap_type::key_type key_type;
+ typedef hash_multimap_type::hasher hasher;
+ typedef hash_multimap_type::key_equal key_equal;
+ typedef hash_multimap_type::local_iterator local_iterator;
+ typedef hash_multimap_type::const_local_iterator const_local_iterator;
+ typedef hash_multimap_type::value_type value_type;
+ typedef hash_multimap_type::iterator iterator;
+ typedef hash_multimap_type::const_iterator const_iterator;
+ typedef hash_multimap_type::size_type size_type;
+ typedef hash_multimap_type::allocator_type allocator_type;
+ typedef boost::input_iterator_archetype<value_type> input_iterator;
+ input_iterator i = boost::static_object<input_iterator>::get();
+ input_iterator j = i;
+
+ size_type n = 1;
+ const hasher& hf = boost::static_object<hasher>::get();
+ const key_equal& eq = boost::static_object<key_equal>::get();
+ //value_type const& t = boost::static_object<value_type>::get();
+ //key_type const& k = boost::static_object<key_type>::get();
+ allocator_type const& a = boost::static_object<allocator_type>::get();
+
+ hash_multimap_type x1(n, hf, eq, a);
+ hash_multimap_type x2(i, j, n, hf, eq, a);
+ swap(x1, x2);
+ std::tr1::swap(x1, x2);
+ }while(0);
+}
+
+
+
+
Added: trunk/libs/tr1/test/test_unordered_set.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/tr1/test/test_unordered_set.cpp 2008-08-05 06:42:03 EDT (Tue, 05 Aug 2008)
@@ -0,0 +1,91 @@
+// (C) Copyright John Maddock 2008.
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+// These are the headers included by the Boost.TR1 implementation,
+// by including these directly we probe for problems with cyclic
+// dependencies when the TR1 headers are in the include search path.
+
+#ifdef TEST_STD_HEADERS
+#include <unordered_set>
+#else
+#include <boost/tr1/unordered_set.hpp>
+#endif
+
+#include "unordered_concepts.hpp"
+#include "boost/concept_archetype.hpp"
+
+
+int main()
+{
+ typedef boost::copy_constructible_archetype<boost::assignable_archetype<> > value_type;
+ typedef boost::default_constructible_unary_function_archetype<value_type, std::size_t> func_type;
+ typedef boost::default_constructible_binary_predicate_archetype<value_type, value_type> pred_type;
+ typedef std::tr1::unordered_set<value_type, func_type, pred_type> hash_set_type;
+ typedef std::tr1::unordered_multiset<value_type, func_type, pred_type> hash_multiset_type;
+
+ boost::function_requires<boost::UniqueUnorderedContainer<hash_set_type> >();
+ boost::function_requires<boost::MultiUnorderedContainer<hash_multiset_type> >();
+
+ do{
+ // unordered_set specific functions:
+ typedef hash_set_type::key_type key_type;
+ typedef hash_set_type::hasher hasher;
+ typedef hash_set_type::key_equal key_equal;
+ typedef hash_set_type::local_iterator local_iterator;
+ typedef hash_set_type::const_local_iterator const_local_iterator;
+ typedef hash_set_type::value_type value_type;
+ typedef hash_set_type::iterator iterator;
+ typedef hash_set_type::const_iterator const_iterator;
+ typedef hash_set_type::size_type size_type;
+ typedef hash_set_type::allocator_type allocator_type;
+ typedef boost::input_iterator_archetype<value_type> input_iterator;
+ input_iterator i = boost::static_object<input_iterator>::get();
+ input_iterator j = i;
+
+ size_type n = 1;
+ const hasher& hf = boost::static_object<hasher>::get();
+ const key_equal& eq = boost::static_object<key_equal>::get();
+ //value_type const& t = boost::static_object<value_type>::get();
+ //key_type const& k = boost::static_object<key_type>::get();
+ allocator_type const& a = boost::static_object<allocator_type>::get();
+
+ hash_set_type x1(n, hf, eq, a);
+ hash_set_type x2(i, j, n, hf, eq, a);
+ swap(x1, x2);
+ std::tr1::swap(x1, x2);
+ }while(0);
+ do{
+ // unordered_set specific functions:
+ typedef hash_multiset_type::key_type key_type;
+ typedef hash_multiset_type::hasher hasher;
+ typedef hash_multiset_type::key_equal key_equal;
+ typedef hash_multiset_type::local_iterator local_iterator;
+ typedef hash_multiset_type::const_local_iterator const_local_iterator;
+ typedef hash_multiset_type::value_type value_type;
+ typedef hash_multiset_type::iterator iterator;
+ typedef hash_multiset_type::const_iterator const_iterator;
+ typedef hash_multiset_type::size_type size_type;
+ typedef hash_multiset_type::allocator_type allocator_type;
+ typedef boost::input_iterator_archetype<value_type> input_iterator;
+ input_iterator i = boost::static_object<input_iterator>::get();
+ input_iterator j = i;
+
+ size_type n = 1;
+ const hasher& hf = boost::static_object<hasher>::get();
+ const key_equal& eq = boost::static_object<key_equal>::get();
+ //value_type const& t = boost::static_object<value_type>::get();
+ //key_type const& k = boost::static_object<key_type>::get();
+ allocator_type const& a = boost::static_object<allocator_type>::get();
+
+ hash_multiset_type x1(n, hf, eq, a);
+ hash_multiset_type x2(i, j, n, hf, eq, a);
+ swap(x1, x2);
+ std::tr1::swap(x1, x2);
+ }while(0);
+}
+
+
+
+
Added: trunk/libs/tr1/test/unordered_concepts.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/tr1/test/unordered_concepts.hpp 2008-08-05 06:42:03 EDT (Tue, 05 Aug 2008)
@@ -0,0 +1,147 @@
+// (C) Copyright John Maddock 2008.
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include "boost/concept_check.hpp"
+#include "boost/concept_archetype.hpp"
+#include "verify_return.hpp"
+
+namespace boost{
+
+template <class Arg, class Return>
+class default_constructible_unary_function_archetype {
+public:
+ const Return& operator()(const Arg&) const {
+ return static_object<Return>::get();
+ }
+};
+
+template <class Arg1, class Arg2, class Base = null_archetype<> >
+class default_constructible_binary_predicate_archetype {
+ typedef boolean_archetype Return;
+public:
+ const Return& operator()(const Arg1&, const Arg2&) const {
+ return static_object<Return>::get();
+ }
+};
+
+template <class Unordered>
+struct UnorderedContainer
+{
+ void constraints()
+ {
+ function_requires<Container<Unordered> >();
+
+ typedef typename Unordered::key_type key_type;
+ typedef typename Unordered::hasher hasher;
+ typedef typename Unordered::key_equal key_equal;
+ typedef typename Unordered::local_iterator local_iterator;
+ typedef typename Unordered::const_local_iterator const_local_iterator;
+ typedef typename Unordered::value_type value_type;
+ typedef typename Unordered::iterator iterator;
+ typedef typename Unordered::const_iterator const_iterator;
+ typedef typename Unordered::size_type size_type;
+
+ function_requires<Assignable<key_type> >();
+ function_requires<CopyConstructible<key_type> >();
+ function_requires<UnaryFunction<hasher, std::size_t, key_type> >();
+ function_requires<BinaryPredicate<key_equal, key_type, key_type> >();
+ function_requires<ForwardIterator<local_iterator> >();
+ function_requires<ForwardIterator<const_local_iterator> >();
+
+ size_type n = 1;
+ const hasher& hf = static_object<hasher>::get();
+ const key_equal& eq = static_object<key_equal>::get();
+ value_type const& t = static_object<value_type>::get();
+ key_type const& k = static_object<key_type>::get();
+ Unordered x1(n, hf, eq);
+ Unordered x2(n, hf);
+ Unordered x3(n);
+ Unordered x4;
+
+ typedef input_iterator_archetype<typename Unordered::value_type> input_iterator;
+ input_iterator i = static_object<input_iterator>::get();
+ input_iterator j = i;
+ x1 = Unordered(i, j, n, hf, eq);
+ x2 = Unordered(i, j, n, hf);
+ x3 = Unordered(i, j, n);
+ x4 = Unordered(i, j);
+ x1 = x2;
+ Unordered x5(x1);
+ iterator q = x1.begin();
+ const_iterator r = x1.begin();
+
+ verify_return_type(x1.hash_function(), hf);
+ verify_return_type(x1.key_eq(), eq);
+ verify_return_type(x1.insert(q, t), q);
+ x1.insert(i, j);
+ verify_return_type(x1.erase(k), n);
+ verify_return_type(x1.erase(q), q);
+ verify_return_type(x1.erase(q, q), q);
+ x1.clear();
+
+ const Unordered& b = x1;
+ verify_return_type(x1.find(k), q);
+ verify_return_type(b.find(k), r);
+ verify_return_type(b.count(k), n);
+ verify_return_type(x1.equal_range(k), std::make_pair(q, q));
+ verify_return_type(b.equal_range(k), std::make_pair(r, r));
+ verify_return_type(b.bucket_count(), n);
+ verify_return_type(b.max_bucket_count(), n);
+ verify_return_type(b.bucket(k), n);
+ verify_return_type(b.bucket_size(n), n);
+
+ local_iterator li = x1.begin(n);
+ const_local_iterator cli = b.begin(n);
+ verify_return_type(x1.begin(n), li);
+ verify_return_type(b.begin(n), cli);
+ verify_return_type(x1.end(n), li);
+ verify_return_type(b.end(n), cli);
+ verify_return_type(b.load_factor(), 1.0f);
+ verify_return_type(b.max_load_factor(), 1.0f);
+ x1.max_load_factor(1.0f);
+ x1.rehash(n);
+ }
+};
+
+template <class Unordered>
+struct UniqueUnorderedContainer
+{
+ void constraints()
+ {
+ typedef typename Unordered::key_type key_type;
+ typedef typename Unordered::hasher hasher;
+ typedef typename Unordered::key_equal key_equal;
+ typedef typename Unordered::local_iterator local_iterator;
+ typedef typename Unordered::const_local_iterator const_local_iterator;
+ typedef typename Unordered::value_type value_type;
+
+ Unordered x;
+ value_type const& t = static_object<value_type>::get();
+ function_requires<UnorderedContainer<Unordered> >();
+ verify_return_type(x.insert(t), static_object<std::pair<typename Unordered::iterator, bool> >::get());
+ }
+};
+
+template <class Unordered>
+struct MultiUnorderedContainer
+{
+ void constraints()
+ {
+ typedef typename Unordered::key_type key_type;
+ typedef typename Unordered::hasher hasher;
+ typedef typename Unordered::key_equal key_equal;
+ typedef typename Unordered::local_iterator local_iterator;
+ typedef typename Unordered::const_local_iterator const_local_iterator;
+ typedef typename Unordered::value_type value_type;
+
+ Unordered x;
+ value_type const& t = static_object<value_type>::get();
+ function_requires<UnorderedContainer<Unordered> >();
+ verify_return_type(x.insert(t), static_object<typename Unordered::iterator>::get());
+ }
+};
+
+}
+
Boost-Commit 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