|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2007-12-16 14:17:37
Author: danieljames
Date: 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
New Revision: 42111
URL: http://svn.boost.org/trac/boost/changeset/42111
Log:
Merge in changes from hash trunk. Most are in response to the review.
Added:
sandbox-branches/unordered-refactor/libs/unordered/doc/src_code/point1.cpp
- copied unchanged from r42108, /sandbox/unordered/libs/unordered/doc/src_code/point1.cpp
sandbox-branches/unordered-refactor/libs/unordered/doc/src_code/point2.cpp
- copied unchanged from r42108, /sandbox/unordered/libs/unordered/doc/src_code/point2.cpp
Properties modified:
sandbox-branches/unordered-refactor/ (props changed)
Text files modified:
sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp | 138 ++++++++--
sandbox-branches/unordered-refactor/boost/unordered_map.hpp | 36 ++
sandbox-branches/unordered-refactor/boost/unordered_set.hpp | 36 ++
sandbox-branches/unordered-refactor/libs/unordered/doc/Jamfile.v2 | 10
sandbox-branches/unordered-refactor/libs/unordered/doc/buckets.qbk | 11
sandbox-branches/unordered-refactor/libs/unordered/doc/comparison.qbk | 27 -
sandbox-branches/unordered-refactor/libs/unordered/doc/hash_equality.qbk | 56 ---
sandbox-branches/unordered-refactor/libs/unordered/doc/intro.qbk | 12
sandbox-branches/unordered-refactor/libs/unordered/doc/rationale.qbk | 115 ++++++-
sandbox-branches/unordered-refactor/libs/unordered/doc/ref.xml | 548 ++++++++++++++++++++++++++++++++++-----
sandbox-branches/unordered-refactor/libs/unordered/doc/src_code/insensitive.cpp | 5
sandbox-branches/unordered-refactor/libs/unordered/examples/case_insensitive.hpp | 2
sandbox-branches/unordered-refactor/libs/unordered/test/container/compile_tests.hpp | 19
sandbox-branches/unordered-refactor/libs/unordered/test/container/map_compile.cpp | 32 ++
sandbox-branches/unordered-refactor/libs/unordered/test/container/set_compile.cpp | 2
sandbox-branches/unordered-refactor/libs/unordered/test/exception/Jamfile.v2 | 2
sandbox-branches/unordered-refactor/libs/unordered/test/exception/insert_tests.cpp | 53 +++
sandbox-branches/unordered-refactor/libs/unordered/test/objects/minimal.hpp | 27 +
sandbox-branches/unordered-refactor/libs/unordered/test/unordered/Jamfile.v2 | 2
sandbox-branches/unordered-refactor/libs/unordered/test/unordered/bucket_tests.cpp | 2
sandbox-branches/unordered-refactor/libs/unordered/test/unordered/compile_tests.cpp | 5
21 files changed, 908 insertions(+), 232 deletions(-)
Modified: sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp (original)
+++ sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -82,17 +82,21 @@
// no throw
inline std::size_t next_prime(std::size_t n) {
+ std::size_t const* const prime_list_end = prime_list +
+ sizeof(prime_list) / sizeof(*prime_list);
std::size_t const* bound =
- std::lower_bound(prime_list,prime_list + 28, n);
- if(bound == prime_list + 28)
+ std::lower_bound(prime_list,prime_list_end, n);
+ if(bound == prime_list_end)
bound--;
return *bound;
}
// no throw
inline std::size_t prev_prime(std::size_t n) {
+ std::size_t const* const prime_list_end = prime_list +
+ sizeof(prime_list) / sizeof(*prime_list);
std::size_t const* bound =
- std::upper_bound(prime_list,prime_list + 28, n);
+ std::upper_bound(prime_list,prime_list_end, n);
if(bound != prime_list)
bound--;
return *bound;
@@ -569,6 +573,11 @@
return get_value(node_);
}
+ value_type* operator->() const
+ {
+ return &get_value(node_);
+ }
+
void increment()
{
BOOST_ASSERT(node_);
@@ -1295,32 +1304,17 @@
// Swap
//
- // Swap's behaviour when allocators aren't equal is in dispute, see
- // this paper for full details:
- //
- // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2004/n1599.html
- //
- // It lists 3 possible behaviours:
- //
- // 1 - If the allocators aren't equal then throw an exception.
- // 2 - Reallocate the elements in the containers with the
- // appropriate allocators - messing up exception safety in
- // the process.
- // 3 - Swap the allocators, hoping that the allocators have a
- // no-throw swap.
- //
- // The paper recommends #3.
+ // Swap's behaviour when allocators aren't equal is in dispute, for
+ // details see:
+ //
+ // http://unordered.nfshost.com/doc/html/unordered/rationale.html#swapping_containers_with_unequal_allocators
//
// ----------------------------------------------------------------
//
// Strong exception safety (might change unused function objects)
//
- // Can throw if hash or predicate object's copy constructor throws.
- // If allocators are unequal:
- // Can throw if allocator's swap throws
- // (I'm assuming that the allocator's swap doesn't throw
- // but this doesn't seem to be guaranteed. Maybe I
- // could double buffer the allocators).
+ // Can throw if hash or predicate object's copy constructor throws
+ // or if allocators are unequal
void swap(hash_table& x)
{
@@ -1333,10 +1327,18 @@
this->data::swap(x); // no throw
}
else {
- // Note: I'm not sure that allocator swap is guaranteed to be no
- // throw.
- this->allocators_.swap(x.allocators_);
- this->data::swap(x);
+ // Create new buckets in separate HASH_TABLE_DATA objects
+ // which will clean up if anything throws an exception.
+ // (all can throw, but with no effect as these are new objects).
+ data new_this(*this, x.min_buckets_for_size(x.size_));
+ copy_buckets(x, new_this, this->*new_func_this);
+
+ data new_that(x, min_buckets_for_size(this->size_));
+ x.copy_buckets(*this, new_that, x.*new_func_that);
+
+ // Start updating the data here, no throw from now on.
+ this->data::swap(new_this);
+ x.data::swap(new_that);
}
// We've made it, the rest is no throw.
@@ -1998,6 +2000,86 @@
}
}
+ //
+ // equals
+ //
+
+private:
+ inline bool group_equals(local_iterator_base it1,
+ local_iterator_base it2, type_wrapper<key_type>*) const
+ {
+ return this->group_count(it1) == this->group_count(it2);
+ }
+
+ inline bool group_equals(local_iterator_base it1,
+ local_iterator_base it2, void*) const
+ {
+ if(!it2.not_finished()) return false;
+ local_iterator_base end1 = it1, end2 = it2;
+ end1.next_group(); end2.next_group();
+ do {
+ if(it1->second != it2->second) return false;
+ it1.increment();
+ it2.increment();
+ } while(it1 != end1 && it2 != end2);
+ return it1 == end1 && it2 == end2;
+ }
+public:
+ bool equals(hash_table const& other) const
+ {
+ if(this->size() != other.size()) return false;
+
+ for(bucket_ptr i = this->cached_begin_bucket_,
+ j = this->buckets_ + this->bucket_count_; i != j; ++i)
+ {
+ for(local_iterator_base it(i->next_); it.not_finished(); it.next_group())
+ {
+ local_iterator_base other_pos = other.find_iterator(other.extract_key(*it));
+ if(!other_pos.not_finished() ||
+ !group_equals(it, other_pos, (type_wrapper<value_type>*)0))
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ inline bool group_hash(local_iterator_base it, type_wrapper<key_type>*) const
+ {
+ std::size_t seed = this->group_count(it);
+ boost::hash_combine(seed, hash_function()(*it));
+ return seed;
+ }
+
+ inline bool group_hash(local_iterator_base it, void*) const
+ {
+ std::size_t seed = hash_function()(it->first);
+
+ local_iterator_base end = it;
+ end.next_group();
+
+ do {
+ boost::hash_combine(seed, it->second);
+ } while(it != end);
+
+ return seed;
+ }
+
+ std::size_t hash_value() const
+ {
+ std::size_t seed = 0;
+
+ for(bucket_ptr i = this->cached_begin_bucket_,
+ j = this->buckets_ + this->bucket_count_; i != j; ++i)
+ {
+ for(local_iterator_base it(i->next_); it.not_finished(); it.next_group())
+ seed ^= group_hash(it, (type_wrapper<value_type>*)0);
+ }
+
+ return seed;
+ }
+
+
private:
// strong exception safety, no side effects
Modified: sandbox-branches/unordered-refactor/boost/unordered_map.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/boost/unordered_map.hpp (original)
+++ sandbox-branches/unordered-refactor/boost/unordered_map.hpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -16,8 +16,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
namespace boost
{
@@ -296,7 +296,6 @@
return const_local_iterator(base.end(n));
}
-#if defined(BOOST_UNORDERED_LOCAL_CBEGIN)
const_local_iterator cbegin(size_type n) const
{
return const_local_iterator(base.begin(n));
@@ -306,7 +305,6 @@
{
return const_local_iterator(base.end(n));
}
-#endif
// hash policy
@@ -329,6 +327,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_map const& m1, unordered_map const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_map const& m1, unordered_map const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_map const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_map
template <class K, class T, class H, class P, class A>
@@ -597,7 +610,6 @@
return const_local_iterator(base.end(n));
}
-#if defined(BOOST_UNORDERED_LOCAL_CBEGIN)
const_local_iterator cbegin(size_type n) const
{
return const_local_iterator(base.begin(n));
@@ -607,7 +619,6 @@
{
return const_local_iterator(base.end(n));
}
-#endif
// hash policy
@@ -630,6 +641,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_multimap const& m1, unordered_multimap const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_multimap const& m1, unordered_multimap const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_multimap const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_multimap
template <class K, class T, class H, class P, class A>
Modified: sandbox-branches/unordered-refactor/boost/unordered_set.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/boost/unordered_set.hpp (original)
+++ sandbox-branches/unordered-refactor/boost/unordered_set.hpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -16,8 +16,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
namespace boost
{
@@ -266,7 +266,6 @@
return const_local_iterator(base.end(n));
}
-#if defined(BOOST_UNORDERED_LOCAL_CBEGIN)
const_local_iterator cbegin(size_type n) const
{
return const_local_iterator(base.begin(n));
@@ -276,7 +275,6 @@
{
return const_local_iterator(base.end(n));
}
-#endif
// hash policy
@@ -299,6 +297,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_set const& m1, unordered_set const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_set const& m1, unordered_set const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_set const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_set
template <class T, class H, class P, class A>
@@ -552,7 +565,6 @@
return const_local_iterator(base.end(n));
}
-#if defined(BOOST_UNORDERED_LOCAL_CBEGIN)
const_local_iterator cbegin(size_type n) const
{
return const_local_iterator(base.begin(n));
@@ -562,7 +574,6 @@
{
return const_local_iterator(base.end(n));
}
-#endif
// hash policy
@@ -585,6 +596,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_multiset const& m1, unordered_multiset const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_multiset const& m1, unordered_multiset const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_multiset const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_multiset
template <class T, class H, class P, class A>
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/Jamfile.v2
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/Jamfile.v2 (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/Jamfile.v2 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -6,4 +6,12 @@
using quickbook ;
xml unordered : unordered.qbk ;
-boostbook standalone : unordered ;
+boostbook standalone : unordered :
+ <xsl:param>boost.root=../../../..
+ <xsl:param>boost.libraries=../../../libraries.htm
+ <xsl:param>html.stylesheet=../../../../doc/html/boostbook.css
+ <xsl:param>chunk.first.sections=1
+ <xsl:param>chunk.section.depth=2
+ <xsl:param>generate.section.toc.level=2
+ <xsl:param>toc.section.depth=1
+ <xsl:param>toc.max.depth=1 ;
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/buckets.qbk
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/buckets.qbk (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/buckets.qbk 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -7,8 +7,8 @@
The containers are made up of a number of 'buckets', each of which can contain
any number of elements. For example, the following diagram shows an [classref
boost::unordered_set unordered_set] with 7 buckets containing 5 elements, `A`,
-`B`, `C`, `D` and `E` (this is just for illustration, in practise containers
-will have more buckets).
+`B`, `C`, `D` and `E` (this is just for illustration, containers will typically
+have more buckets).
[$../../libs/unordered/doc/diagrams/buckets.png]
@@ -97,9 +97,10 @@
x.rehash((x.size() + n) / x.max_load_factor() + 1);
[blurb Note: `rehash`'s argument is the number of buckets, not the number of
-elements, which is why the new size is divided by the maximum load factor. The
-`+ 1` is required because the container is allowed to resize when the load
-factor is equal to the maximum load factor.]
+elements, which is why the new size is divided by the maximum load factor. The
++ 1 guarantees there is no invalidation; without it, reallocation could occur
+if the number of bucket exactly divides the target size, since the container is
+allowed to rehash when the load factor is equal to the maximum load factor.]
[table Methods for Controlling Bucket Size
[[Method] [Description]]
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/comparison.qbk
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/comparison.qbk (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/comparison.qbk 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -8,19 +8,16 @@
[[Associative Containers] [Unordered Associative Containers]]
[
- [Parametrised by an ordering relation `Compare`]
- [Parametrised by a function object `Hash` and an equivalence relation
+ [Parameterized by an ordering relation `Compare`]
+ [Parameterized by a function object `Hash` and an equivalence relation
`Pred`]
]
[
- [`Compare` exposed by member typedef `key_compare`, accessed by member function `key_comp()`]
- [`Hash` exposed by member typedef `hasher`, accessed by member function `hash_function()`.
-
- `Pred` by member typedef `key_equal` and member function `key_eq()`.]
- ]
- [
- [Member typedef `value_compare` supplies an ordering comparison for member elements, accessed by member function `value_comp()`.]
- [No equivalent. No idea why.]
+ [Keys can be compared using `key_compare` which is accessed by member function `key_comp()`,
+ values can be compared using `value_compare` which is accessed by member function `value_comp()`.]
+ [Keys can be hashed using `hasher` which is accessed by member function `hash_function()`,
+ and checked for equality using `key_equal` which is accessed by member function `key_eq()`.
+ There is no function object for compared or hashing values.]
]
[
[Constructors have optional extra parameters for the comparison object.]
@@ -105,15 +102,15 @@
]
[
[Insert a single element with a hint]
- [Amortised constant if t elements inserted right after hint,
+ [Amortized constant if t elements inserted right after hint,
logarithmic otherwise]
[Average case constant, worst case linear (ie. the same as
a normal insert).]
]
[
[Inserting a range of /N/ elements]
- [/N/ log(`size()`+/N/)]
- [Average case O(/N/), worst case O(/N/ * 'size()')]
+ [ /N/ log(`size()`+/N/) ]
+ [Average case O(/N/), worst case O(/N/ * `size()`)]
]
[
[Erase by key, `k`]
@@ -122,7 +119,7 @@
]
[
[Erase a single element by iterator]
- [Amortised constant]
+ [Amortized constant]
[Average case: O(1), Worst case: O(`size()`)]
]
[
@@ -138,7 +135,7 @@
[
[Find]
[logarithmic]
- [Average case: O(/N/), Worst case: O(`size()`)]
+ [Average case: O(1), Worst case: O(`size()`)]
]
[/ TODO: Average case is probably wrong. ]
[
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/hash_equality.qbk
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/hash_equality.qbk (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/hash_equality.qbk 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -16,7 +16,7 @@
class ``[classref boost::unordered_set unordered_set]``;
The hash function comes first as you might want to change the hash function
-but not the equality predicate, while if you were to change the behaviour
+but not the equality predicate, while if you were to change the behavior
of the equality predicate you would have to change the hash function to match
it. So, if you wanted to use the
[@http://www.isthe.com/chongo/tech/comp/fnv/ FNV-1 hash] you could write:
@@ -34,59 +34,21 @@
[case_insensitive_functions]
[case_insensitive_dictionary]
-A more generic version is available at:
+This is a simplified version of the example at:
[@../../libs/unordered/examples/case_insensitive.hpp /libs/unordered/examples/case_insensitive.hpp]
+which supports other locales and string types.
[h2 Custom Types]
Similarly, a custom hash function can be used for custom types:
- struct point {
- int x;
- int y;
- };
-
- bool operator==(point const& p1, point const& p2)
- {
- return p1.x == p2.x && p1.y == p2.y;
- }
-
- struct point_hash
- : std::unary_function<point, std::size_t>
- {
- std::size_t operator()(point const& p) const
- {
- std::size_t seed = 0;
- boost::hash_combine(seed, p.x);
- boost::hash_combine(seed, p.y);
- return seed;
- }
- }
-
- boost::unordered_multiset<point, std::equal_to<point>, point_hash>
- points;
-
-Although, customising Boost.Hash is probably a better solution:
-
- struct point {
- int x;
- int y;
- };
-
- bool operator==(point const& p1, point const& p2)
- {
- return p1.x == p2.x && p1.y == p2.y;
- }
-
- std::size_t hash_value(point const& x) {
- std::size_t seed = 0;
- boost::hash_combine(seed, p.x);
- boost::hash_combine(seed, p.y);
- return seed;
- }
+[import src_code/point1.cpp]
+[point_example1]
- // Now the default functions work.
- boost::unordered_multiset<point> points;
+Although, customizing Boost.Hash is probably a better solution:
+
+[import src_code/point2.cpp]
+[point_example2]
See the Boost.Hash documentation for more detail on how to do this. Remember
that it relies on extensions to the draft standard - so it won't work on other
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/intro.qbk
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/intro.qbk (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/intro.qbk 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -45,14 +45,14 @@
namespace boost {
template <
class Key,
- class Hash = boost::hash<Key>,
+ class Hash = ``[classref 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 Hash = ``[classref boost::hash]``<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<Key> >
class ``[classref boost::unordered_multiset unordered_multiset]``;
@@ -63,15 +63,15 @@
namespace boost {
template <
- class Key, class T,
- class Hash = boost::hash<Key>,
+ class Key, class Mapped,
+ class Hash = ``[classref 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 Key, class Mapped,
+ class Hash = ``[classref boost::hash]``<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<Key> >
class ``[classref boost::unordered_multimap unordered_multimap]``;
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/rationale.qbk
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/rationale.qbk (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/rationale.qbk 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -7,7 +7,7 @@
Thomas Wang's article on integer hash functions]]
[def __n2345__
[@http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2345.pdf
- N2345, 'Placement Instert for Containers']]
+ N2345, 'Placement Insert for Containers']]
[def __n2369__
[@http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2369.pdf
the August 2008 version of the working draft standard]]
@@ -28,12 +28,12 @@
standard pretty much requires that the hash table uses chained addressing.
It would be conceivable to write a hash table that uses another method. For
-example, an it could use open addressing, and use the lookup chain to act as a
+example, it could use open addressing, and use the lookup chain to act as a
bucket but there are a some serious problems with this:
* The draft standard requires that pointers to elements aren't invalidated, so
the elements can't be stored in one array, but will need a layer of
- indirection instead - loosing the efficiency and most of the memory gain,
+ indirection instead - losing the efficiency and most of the memory gain,
the main advantages of open addressing.
* Local iterators would be very inefficient and may not be able to
@@ -98,35 +98,96 @@
[h2 Active Issues and Proposals]
-[h3 [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2257.html
- Removing unused allocator functions]]
+[h3 Removing unused allocator functions]
-This proposal suggests removing the `construct`, `destroy` and `address`
-member functions - all of which Boost.Unordered calls. It's near trivial
-to replace the calls with the appropriate code - and will simplify the
-implementation, as well as make supporting `emplace` easier.
-[@http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2339.htm
-N2339] opposed this change.
-
-[h3 [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#431
- 431. Swapping containers with unequal allocators]]
-
-I followed Howard Hinnant's advice and implemented option 3.
-
-There is currently a further issue - if the allocator's swap does throw there's
-no guarantee what state the allocators will be in. The only solution seems to
-be to double buffer the allocators. But I'm assuming that it won't throw for now.
-
-Update: The committee have now decided that `swap` should do a fast swap if the
+In
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2257.html
+N2257, removing unused allocator functions],
+Matt Austern suggests removing the `construct`, `destroy` and `address` member
+functions - all of which Boost.Unordered calls. Changing this will simplify the
+implementation, as well as make supporting `emplace` easier, but means that the
+containers won't support allocators which require these methods to be called.
+Detlef Vollmann opposed this change in
+[@http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2339.htm N2339].
+
+[h3 Swapping containers with unequal allocators]
+
+It isn't clear how to swap containers when their allocators aren't equal.
+This is
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#431
+Issue 431: Swapping containers with unequal allocators].
+
+Howard Hinnant wrote about this in
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html N1599]
+and suggested swapping both the allocators and the containers' contents.
+But the committee have now decided that `swap` should do a fast swap if the
allocator is Swappable and a slow swap using copy construction otherwise. To
-make this distinction requires concepts. For now I'm sticking with the current
-implementation.
-
-[h3 [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#518
- 518. Are insert and erase stable for unordered_multiset and unordered_multimap?]]
+make this distinction requires concepts.
+In
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2387.pdf
+N2387, Omnibus Allocator Fix-up Proposals],
+Pablo Halpern suggests that there are actually two distinct allocator models,
+"Moves with Value" and "Scoped" which behave differently:
+
+[:
+When allocators are allowed to have state, it is necessary to have a model for
+determining from where an object obtains its allocator. We’ve identified two such
+models: the “Moves with Value†allocator model and the “Scoped†allocator model.
+
+In the “Moves with Value†allocator model, the copy constructor of an allocator-aware
+class will copy both the value and the allocator from its argument. This is the model
+specified in the C++03 standard. With this model, inserting an object into a container
+usually causes the new container item to copy the allocator from the object that was
+inserted. This model can be useful in special circumstances, e.g., if the items within a
+container use an allocator that is specially tuned to the item’s type.
+
+In the “Scoped†allocator model, the allocator used to construct an object is determined
+by the context of that object, much like a storage class. With this model, inserting an
+object into a container causes the new container item to use the same allocator as the
+container. To avoid allocators being used in the wrong context, the allocator is never
+copied during copy or move construction. Thus, it is possible using this model to use
+allocators based on short-lived resources without fear that an object will transfer its
+allocator to a copy that might outlive the (shared) allocator resource. This model is
+reasonably safe and generally useful on a large scale. There was strong support in the
+2005 Tremblant meeting for pursuing an allocator model that propagates allocators
+from container to contained objects.
+]
+
+With these models the choice becomes clearer:
+
+[:
+I introduced the “Moves with Value†allocator model and the
+“Scoped†allocator model. In the former case, the allocator is copied when the container
+is copy-constructed. In the latter case it is not. Swapping the allocators is the right thing
+to do if the containers conform to the “Moves with Value†allocator model and
+absolutely the wrong thing to do if the containers conform to the “Scoped†allocator
+model. With the two allocator models well-defined, the desired behavior becomes clear.
+]
+
+The proposal is that allocators are swapped if the allocator follows the
+"Moves with Value" model and the allocator is swappable. Otherwise a slow swap
+is used. Since containers currently only support the "Moves with Value" model
+this is consistent with the committee's current recommendation (although it
+suggests using a trait to detect if the allocator is swappable rather than a
+concept).
+
+Since there is currently neither have a swappable trait or concept for
+allocators this implementation always performs a slow swap.
+
+[h3 Are insert and erase stable for unordered_multiset and unordered_multimap?]
+
+It is not specified if `unordered_multiset` and `unordered_multimap` preserve the order
+of elements with equivalent keys (i.e. if they're stable under `insert` and `erase`).
+This is [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#518 issue 581].
The current proposal is that insert, erase and rehash are stable - so they are here.
+[h3 const_local_iterator cbegin, cend missing from TR1]
+
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2482.html#691
+Issue 691] is that `cbegin` and `cend` are missing for local iterators.
+The current resolution is that they'll be added, so I've added them.
+
[h2 Future Developments]
[h3 Support for `emplace`]
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/ref.xml
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/ref.xml (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/ref.xml 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -128,7 +128,7 @@
<para>A const_local_iterator object can be used to iterate through a single bucket.</para>
</description>
</typedef>
- <constructor>
+ <constructor specifiers="explicit">
<parameter name="n">
<paramtype>size_type</paramtype>
<default><emphasis>implementation-defined</emphasis></default>
@@ -149,7 +149,7 @@
<code><methodname>size</methodname>() == 0</code>
</postconditions>
<description>
- <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocatorand a maximum load factor of 1.0.</para>
+ <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocator and a maximum load factor of 1.0.</para>
</description>
</constructor>
<constructor>
@@ -263,7 +263,7 @@
</description>
<returns>
<para>The bool component of the return type is true if an insert took place.</para>
- <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the elment with equivalent value.</para>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent value.</para>
</returns>
<throws>
<para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
@@ -285,7 +285,7 @@
<para>hint is a suggestion to where the element should be inserted.</para>
</description>
<returns>
- <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the elment with equivalent value.</para>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent value.</para>
</returns>
<throws>
<para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
@@ -329,8 +329,8 @@
<para>The iterator following <code>position</code> before the erasure.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="erase">
@@ -345,7 +345,7 @@
<para>The number of elements erased.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
</throws>
</method>
<method name="erase">
@@ -356,15 +356,15 @@
<paramtype>const_iterator</paramtype>
</parameter>
<type>iterator</type>
- <descritpion>
+ <description>
<para>Erases the elements in the range from <code>first</code> to <code>last</code>.</para>
- </descritpion>
+ </description>
<returns>
<para>The iterator following the erased elements - i.e. <code>last</code>.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="clear">
@@ -385,8 +385,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -439,7 +443,7 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
- <type>std::pair<iterator, iterator></type>
+ <type>std::pair<const_iterator, const_iterator></type>
</signature>
<returns>
<para>A range containing all elements with key equivalent to <code>k</code>.
@@ -526,6 +530,30 @@
<para>A local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
</returns>
</overloaded-method>
+ <method name="cbegin" cv="const">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the first element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
+ <method name="cend">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
</method-group>
<method-group name="hash policy">
<method name="load_factor" cv="const">
@@ -563,6 +591,71 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
@@ -576,18 +669,22 @@
</template-type-parameter>
</template>
<parameter name="x">
- <paramtype>unordered_set<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc>&</paramtype>
</parameter>
<parameter name="y">
- <paramtype>unordered_set<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc>&</paramtype>
</parameter>
<type>void</type>
<effects>
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
@@ -708,7 +805,7 @@
<para>A const_local_iterator object can be used to iterate through a single bucket.</para>
</description>
</typedef>
- <constructor>
+ <constructor specifiers="explicit">
<parameter name="n">
<paramtype>size_type</paramtype>
<default><emphasis>implementation-defined</emphasis></default>
@@ -729,7 +826,7 @@
<code><methodname>size</methodname>() == 0</code>
</postconditions>
<description>
- <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocatorand a maximum load factor of 1.0.</para>
+ <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocator and a maximum load factor of 1.0.</para>
</description>
</constructor>
<constructor>
@@ -908,8 +1005,8 @@
<para>The iterator following <code>position</code> before the erasure.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="erase">
@@ -924,7 +1021,7 @@
<para>The number of elements erased.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
</throws>
</method>
<method name="erase">
@@ -935,15 +1032,15 @@
<paramtype>const_iterator</paramtype>
</parameter>
<type>iterator</type>
- <descritpion>
+ <description>
<para>Erases the elements in the range from <code>first</code> to <code>last</code>.</para>
- </descritpion>
+ </description>
<returns>
<para>The iterator following the erased elements - i.e. <code>last</code>.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="clear">
@@ -964,8 +1061,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -1018,7 +1119,7 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
- <type>std::pair<iterator, iterator></type>
+ <type>std::pair<const_iterator, const_iterator></type>
</signature>
<returns>
<para>A range containing all elements with key equivalent to <code>k</code>.
@@ -1105,6 +1206,30 @@
<para>A local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
</returns>
</overloaded-method>
+ <method name="cbegin" cv="const">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the first element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
+ <method name="cend">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
</method-group>
<method-group name="hash policy">
<method name="load_factor" cv="const">
@@ -1142,6 +1267,71 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
@@ -1155,18 +1345,22 @@
</template-type-parameter>
</template>
<parameter name="x">
- <paramtype>unordered_multiset<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc>&</paramtype>
</parameter>
<parameter name="y">
- <paramtype>unordered_multiset<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc>&</paramtype>
</parameter>
<type>void</type>
<effects>
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
@@ -1187,7 +1381,7 @@
<template>
<template-type-parameter name="Key">
</template-type-parameter>
- <template-type-parameter name="T">
+ <template-type-parameter name="Mapped">
</template-type-parameter>
<template-type-parameter name="Hash">
<default><type>boost::hash<Value></type></default>
@@ -1196,7 +1390,7 @@
<default><type>std::equal_to<Value></type></default>
</template-type-parameter>
<template-type-parameter name="Alloc">
- <default><type>std::allocator<std::pair<const Key, T> ></type></default>
+ <default><type>std::allocator<std::pair<const Key, Mapped> ></type></default>
</template-type-parameter>
</template>
<purpose>An unordered associative container that associates unique keys with another value.
@@ -1212,8 +1406,8 @@
<entry><emphasis>Key</emphasis></entry>
<entry>Key must be Assignable and CopyConstructible.</entry></row>
<row>
- <entry><emphasis>T</emphasis></entry>
- <entry>T must be CopyConstructible</entry></row>
+ <entry><emphasis>Mapped</emphasis></entry>
+ <entry>Mapped must be CopyConstructible</entry></row>
<row>
<entry><emphasis>Hash</emphasis></entry>
<entry>A unary function object type that acts a hash function for a <code>Key</code>. It takes a single argument of type <code>Key</code> and returns a value of type std::size_t.</entry></row>
@@ -1235,7 +1429,7 @@
<type>std::pair<Key const, Value></type>
</typedef>
<typedef name="mapped_type">
- <type>T</type>
+ <type>Mapped</type>
</typedef>
<typedef name="hasher">
<type>Hash</type>
@@ -1303,7 +1497,7 @@
<para>A const_local_iterator object can be used to iterate through a single bucket.</para>
</description>
</typedef>
- <constructor>
+ <constructor specifiers="explicit">
<parameter name="n">
<paramtype>size_type</paramtype>
<default><emphasis>implementation-defined</emphasis></default>
@@ -1324,7 +1518,7 @@
<code><methodname>size</methodname>() == 0</code>
</postconditions>
<description>
- <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocatorand a maximum load factor of 1.0.</para>
+ <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocator and a maximum load factor of 1.0.</para>
</description>
</constructor>
<constructor>
@@ -1438,7 +1632,7 @@
</description>
<returns>
<para>The bool component of the return type is true if an insert took place.</para>
- <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the elment with equivalent key.</para>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.</para>
</returns>
<throws>
<para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
@@ -1460,7 +1654,7 @@
<para>hint is a suggestion to where the element should be inserted.</para>
</description>
<returns>
- <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the elment with equivalent key.</para>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.</para>
</returns>
<throws>
<para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
@@ -1504,8 +1698,8 @@
<para>The iterator following <code>position</code> before the erasure.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="erase">
@@ -1520,7 +1714,7 @@
<para>The number of elements erased.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
</throws>
</method>
<method name="erase">
@@ -1531,15 +1725,15 @@
<paramtype>const_iterator</paramtype>
</parameter>
<type>iterator</type>
- <descritpion>
+ <description>
<para>Erases the elements in the range from <code>first</code> to <code>last</code>.</para>
- </descritpion>
+ </description>
<returns>
<para>The iterator following the erased elements - i.e. <code>last</code>.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="clear">
@@ -1560,8 +1754,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -1614,7 +1812,7 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
- <type>std::pair<iterator, iterator></type>
+ <type>std::pair<const_iterator, const_iterator></type>
</signature>
<returns>
<para>A range containing all elements with key equivalent to <code>k</code>.
@@ -1642,9 +1840,9 @@
</notes>
</method>
<overloaded-method name="at">
- <signature><type>T&</type>
+ <signature><type>Mapped&</type>
<parameter name="k"><paramtype>key_type const&</paramtype></parameter></signature>
- <signature cv="const"><type>T const&</type>
+ <signature cv="const"><type>Mapped const&</type>
<parameter name="k"><paramtype>key_type const&</paramtype></parameter></signature>
<returns>
<para>A reference to <code>x.second</code> where <code>x</code> is the (unique) element whose key is equivalent to <code>k</code>.</para>
@@ -1735,6 +1933,30 @@
<para>A local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
</returns>
</overloaded-method>
+ <method name="cbegin" cv="const">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the first element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
+ <method name="cend">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
</method-group>
<method-group name="hash policy">
<method name="load_factor" cv="const">
@@ -1772,12 +1994,83 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
<template-type-parameter name="Key">
</template-type-parameter>
- <template-type-parameter name="T">
+ <template-type-parameter name="Mapped">
</template-type-parameter>
<template-type-parameter name="Hash">
</template-type-parameter>
@@ -1787,18 +2080,22 @@
</template-type-parameter>
</template>
<parameter name="x">
- <paramtype>unordered_map<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc>&</paramtype>
</parameter>
<parameter name="y">
- <paramtype>unordered_map<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc>&</paramtype>
</parameter>
<type>void</type>
<effects>
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
@@ -1811,7 +2108,7 @@
<template>
<template-type-parameter name="Key">
</template-type-parameter>
- <template-type-parameter name="T">
+ <template-type-parameter name="Mapped">
</template-type-parameter>
<template-type-parameter name="Hash">
<default><type>boost::hash<Value></type></default>
@@ -1820,7 +2117,7 @@
<default><type>std::equal_to<Value></type></default>
</template-type-parameter>
<template-type-parameter name="Alloc">
- <default><type>std::allocator<std::pair<const Key, T> ></type></default>
+ <default><type>std::allocator<std::pair<const Key, Mapped> ></type></default>
</template-type-parameter>
</template>
<purpose>An unordered associative container that associates keys with another value. The same key can be stored multiple times.
@@ -1836,8 +2133,8 @@
<entry><emphasis>Key</emphasis></entry>
<entry>Key must be Assignable and CopyConstructible.</entry></row>
<row>
- <entry><emphasis>T</emphasis></entry>
- <entry>T must be CopyConstructible</entry></row>
+ <entry><emphasis>Mapped</emphasis></entry>
+ <entry>Mapped must be CopyConstructible</entry></row>
<row>
<entry><emphasis>Hash</emphasis></entry>
<entry>A unary function object type that acts a hash function for a <code>Key</code>. It takes a single argument of type <code>Key</code> and returns a value of type std::size_t.</entry></row>
@@ -1859,7 +2156,7 @@
<type>std::pair<Key const, Value></type>
</typedef>
<typedef name="mapped_type">
- <type>T</type>
+ <type>Mapped</type>
</typedef>
<typedef name="hasher">
<type>Hash</type>
@@ -1927,7 +2224,7 @@
<para>A const_local_iterator object can be used to iterate through a single bucket.</para>
</description>
</typedef>
- <constructor>
+ <constructor specifiers="explicit">
<parameter name="n">
<paramtype>size_type</paramtype>
<default><emphasis>implementation-defined</emphasis></default>
@@ -1948,7 +2245,7 @@
<code><methodname>size</methodname>() == 0</code>
</postconditions>
<description>
- <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocatorand a maximum load factor of 1.0.</para>
+ <para>Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocator and a maximum load factor of 1.0.</para>
</description>
</constructor>
<constructor>
@@ -2127,8 +2424,8 @@
<para>The iterator following <code>position</code> before the erasure.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="erase">
@@ -2143,7 +2440,7 @@
<para>The number of elements erased.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
</throws>
</method>
<method name="erase">
@@ -2154,15 +2451,15 @@
<paramtype>const_iterator</paramtype>
</parameter>
<type>iterator</type>
- <descritpion>
+ <description>
<para>Erases the elements in the range from <code>first</code> to <code>last</code>.</para>
- </descritpion>
+ </description>
<returns>
<para>The iterator following the erased elements - i.e. <code>last</code>.</para>
</returns>
<throws>
- <para>Only throws an exception, if it is thrown by a call to <code>hasher</code> or <code>key_equal</code>.</para>
- <para>They don't get called by the current implementation Boost.Unordered but other implementations may call them.</para>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
<method name="clear">
@@ -2183,8 +2480,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -2237,7 +2538,7 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
- <type>std::pair<iterator, iterator></type>
+ <type>std::pair<const_iterator, const_iterator></type>
</signature>
<returns>
<para>A range containing all elements with key equivalent to <code>k</code>.
@@ -2324,6 +2625,30 @@
<para>A local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
</returns>
</overloaded-method>
+ <method name="cbegin" cv="const">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the first element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
+ <method name="cend">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>const_local_iterator</type>
+ <requires>
+ <para><code>n</code> shall be in the range <code>[0, bucket_count())</code>.</para>
+ </requires>
+ <returns>
+ <para>A constant local iterator pointing the 'one past the end' element in the bucket with index <code>n</code>.</para>
+ </returns>
+ </method>
</method-group>
<method-group name="hash policy">
<method name="load_factor" cv="const">
@@ -2361,12 +2686,83 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
<template-type-parameter name="Key">
</template-type-parameter>
- <template-type-parameter name="T">
+ <template-type-parameter name="Mapped">
</template-type-parameter>
<template-type-parameter name="Hash">
</template-type-parameter>
@@ -2376,18 +2772,22 @@
</template-type-parameter>
</template>
<parameter name="x">
- <paramtype>unordered_multimap<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc>&</paramtype>
</parameter>
<parameter name="y">
- <paramtype>unordered_multimap<Key, T, Hash, Pred, Alloc>&</paramtype>
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc>&</paramtype>
</parameter>
<type>void</type>
<effects>
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
Modified: sandbox-branches/unordered-refactor/libs/unordered/doc/src_code/insensitive.cpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/doc/src_code/insensitive.cpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/doc/src_code/insensitive.cpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -14,7 +14,7 @@
bool operator()(std::string const& x,
std::string const& y) const
{
- return boost::algorithm::iequals(x, y);
+ return boost::algorithm::iequals(x, y, std::locale());
}
};
@@ -24,11 +24,12 @@
std::size_t operator()(std::string const& x) const
{
std::size_t seed = 0;
+ std::locale locale;
for(std::string::const_iterator it = x.begin();
it != x.end(); ++it)
{
- boost::hash_combine(seed, std::toupper(*it));
+ boost::hash_combine(seed, std::toupper(*it, locale));
}
return seed;
Modified: sandbox-branches/unordered-refactor/libs/unordered/examples/case_insensitive.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/examples/case_insensitive.hpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/examples/case_insensitive.hpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -27,7 +27,7 @@
template <typename String1, typename String2>
bool operator()(String1 const& x1, String2 const& x2) const
{
- return boost::algorithm::iequals(x1, x2);
+ return boost::algorithm::iequals(x1, x2, locale_);
}
private:
std::locale locale_;
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/container/compile_tests.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/container/compile_tests.hpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/container/compile_tests.hpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -111,6 +111,7 @@
(&a1)->~X();
X const a_const;
+
test::check_return_type<iterator>::equals(a.begin());
test::check_return_type<const_iterator>::equals(a_const.begin());
test::check_return_type<const_iterator>::equals(a.cbegin());
@@ -119,12 +120,18 @@
test::check_return_type<const_iterator>::equals(a_const.end());
test::check_return_type<const_iterator>::equals(a.cend());
test::check_return_type<const_iterator>::equals(a_const.cend());
+}
- // No tests for ==, != since they're not required for unordered containers.
+template <class X, class T>
+void equality_test(X& r, T&)
+{
+ X const a = r, b = r;
- a.swap(b);
- test::check_return_type<X>::equals_ref(r = a);
- test::check_return_type<size_type>::equals(a.size());
- test::check_return_type<size_type>::equals(a.max_size());
- test::check_return_type<bool>::convertible(a.empty());
+ test::check_return_type<bool>::equals(a == b);
+ test::check_return_type<bool>::equals(a != b);
+#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+ test::check_return_type<std::size_t>::equals(boost::hash_value(a));
+#else
+ test::check_return_type<std::size_t>::equals(hash_value(a));
+#endif
}
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/container/map_compile.cpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/container/map_compile.cpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/container/map_compile.cpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -13,7 +13,7 @@
#include "../objects/minimal.hpp"
#include "./compile_tests.hpp"
-int main()
+void container_tests()
{
typedef std::pair<test::minimal::assignable const,
test::minimal::copy_constructible> value_type;
@@ -40,6 +40,36 @@
test::minimal::allocator<value_type> > multimap;
container_test(multimap, value);
+}
+
+void equality_tests() {
+ typedef std::pair<test::minimal::assignable const,
+ test::minimal::copy_constructible_equality_comparable> value_type;
+ value_type value(
+ test::minimal::assignable::create(),
+ test::minimal::copy_constructible_equality_comparable::create());
+
+ boost::unordered_map<
+ test::minimal::assignable,
+ test::minimal::copy_constructible_equality_comparable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > map;
+
+ equality_test(map, value);
+
+ boost::unordered_multimap<
+ test::minimal::assignable,
+ test::minimal::copy_constructible_equality_comparable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > multimap;
+
+ equality_test(multimap, value);
+}
+int main() {
+ container_tests();
+ equality_tests();
return boost::report_errors();
}
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/container/set_compile.cpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/container/set_compile.cpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/container/set_compile.cpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -25,6 +25,7 @@
test::minimal::allocator<test::minimal::assignable> > set;
container_test(set, assignable);
+ equality_test(set, assignable);
std::cout<<"Test unordered_multiset.\n";
boost::unordered_multiset<
@@ -34,6 +35,7 @@
test::minimal::allocator<test::minimal::assignable> > multiset;
container_test(multiset, assignable);
+ equality_test(multiset, assignable);
return boost::report_errors();
}
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/exception/Jamfile.v2
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/exception/Jamfile.v2 (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/exception/Jamfile.v2 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -21,5 +21,5 @@
[ run erase_tests.cpp framework ]
[ run rehash_tests.cpp framework ]
[ run swap_tests.cpp framework : : :
- <define>BOOST_UNORDERED_SWAP_METHOD=3 ]
+ <define>BOOST_UNORDERED_SWAP_METHOD=2 ]
;
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/exception/insert_tests.cpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/exception/insert_tests.cpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/exception/insert_tests.cpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -73,11 +73,7 @@
template <class T>
struct insert_test3 : public insert_test_base<T>
{
- typedef typename insert_test_base<T>::strong_type strong_type;
-
- void run(T& x, strong_type& strong) const {
- // I don't think there's any need for this here.
- //strong.store(x);
+ void run(T& x) const {
x.insert(this->values.begin(), this->values.end());
}
@@ -165,7 +161,52 @@
}
};
+template <class T>
+struct insert_test_rehash3 : public insert_test_base<T>
+{
+ typename T::size_type mutable rehash_bucket_count, original_bucket_count;
+
+ insert_test_rehash3() : insert_test_base<T>(1000) {}
+
+ T init() const {
+ typedef typename T::size_type size_type;
+
+ T x;
+ x.max_load_factor(0.25);
+
+ original_bucket_count = x.bucket_count();
+ rehash_bucket_count = static_cast<size_type>(
+ std::ceil(original_bucket_count * x.max_load_factor())) - 1;
+
+ size_type initial_elements = rehash_bucket_count - 5;
+
+ BOOST_REQUIRE(initial_elements < this->values.size());
+ x.insert(this->values.begin(),
+ boost::next(this->values.begin(), initial_elements));
+ BOOST_REQUIRE(original_bucket_count == x.bucket_count());
+ return x;
+ }
+
+ void run(T& x) const {
+ typename T::size_type bucket_count = x.bucket_count();
+
+ x.insert(boost::next(this->values.begin(), x.size()),
+ boost::next(this->values.begin(), x.size() + 20));
+
+ // This isn't actually a failure, but it means the test isn't doing its
+ // job.
+ BOOST_REQUIRE(x.bucket_count() != bucket_count);
+ }
+
+ void check(T const& x) const {
+ if(x.size() < rehash_bucket_count) {
+ //BOOST_CHECK(x.bucket_count() == original_bucket_count);
+ }
+ test::check_equivalent_keys(x);
+ }
+};
+
RUN_EXCEPTION_TESTS(
(insert_test1)(insert_test2)(insert_test3)(insert_test4)
- (insert_test_rehash1)(insert_test_rehash2),
+ (insert_test_rehash1)(insert_test_rehash2)(insert_test_rehash3),
CONTAINER_SEQ)
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/objects/minimal.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/objects/minimal.hpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/objects/minimal.hpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -18,6 +18,7 @@
namespace minimal
{
class copy_constructible;
+ class copy_constructible_equality_comparable;
class default_copy_constructible;
class assignable;
template <class T> class hash;
@@ -37,6 +38,29 @@
copy_constructible() {}
};
+ class copy_constructible_equality_comparable
+ {
+ public:
+ static copy_constructible_equality_comparable create() { return copy_constructible_equality_comparable(); }
+ copy_constructible_equality_comparable(copy_constructible_equality_comparable const&) {}
+ ~copy_constructible_equality_comparable() {}
+ private:
+ copy_constructible_equality_comparable& operator=(copy_constructible_equality_comparable const&);
+ copy_constructible_equality_comparable() {}
+ };
+
+ bool operator==(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
+ return true;
+ }
+
+ bool operator!=(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
+ return false;
+ }
+
+ std::size_t hash_value(copy_constructible_equality_comparable) {
+ return 1;
+ }
+
class default_copy_constructible
{
public:
@@ -217,7 +241,8 @@
size_type max_size() const { return 1000; }
-#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) || \
+ BOOST_WORKAROUND(MSVC, <= 1300)
public: allocator& operator=(allocator const&) { return *this;}
#else
private: allocator& operator=(allocator const&);
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/unordered/Jamfile.v2 (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/unordered/Jamfile.v2 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -27,5 +27,5 @@
[ run bucket_tests.cpp ]
[ run load_factor_tests.cpp ]
[ run rehash_tests.cpp ]
- [ run swap_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD=3 ]
+ [ run swap_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD=2 ]
;
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/unordered/bucket_tests.cpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/unordered/bucket_tests.cpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/unordered/bucket_tests.cpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -41,8 +41,10 @@
for(size_type i = 0; i < x.bucket_count(); ++i) {
BOOST_TEST(x.bucket_size(i) == (size_type) std::distance(x.begin(i), x.end(i)));
+ BOOST_TEST(x.bucket_size(i) == (size_type) std::distance(x.cbegin(i), x.cend(i)));
X const& x_ref = x;
BOOST_TEST(x.bucket_size(i) == (size_type) std::distance(x_ref.begin(i), x_ref.end(i)));
+ BOOST_TEST(x.bucket_size(i) == (size_type) std::distance(x_ref.cbegin(i), x_ref.cend(i)));
}
}
Modified: sandbox-branches/unordered-refactor/libs/unordered/test/unordered/compile_tests.cpp
==============================================================================
--- sandbox-branches/unordered-refactor/libs/unordered/test/unordered/compile_tests.cpp (original)
+++ sandbox-branches/unordered-refactor/libs/unordered/test/unordered/compile_tests.cpp 2007-12-16 14:17:35 EST (Sun, 16 Dec 2007)
@@ -190,6 +190,11 @@
test::check_return_type<local_iterator>::equals(a.end(0));
test::check_return_type<const_local_iterator>::equals(b.end(0));
+ test::check_return_type<const_local_iterator>::equals(a.cbegin(0));
+ test::check_return_type<const_local_iterator>::equals(b.cbegin(0));
+ test::check_return_type<const_local_iterator>::equals(a.cend(0));
+ test::check_return_type<const_local_iterator>::equals(b.cend(0));
+
test::check_return_type<float>::equals(b.load_factor());
test::check_return_type<float>::equals(b.max_load_factor());
a.max_load_factor((float) 2.0);
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