|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r60980 - in branches/release: boost/functional/hash boost/functional/hash/detail boost/iostreams boost/unordered libs/functional/hash libs/functional/hash/test libs/iostreams libs/unordered libs/unordered/doc libs/unordered/test/unordered tools/boostbook tools/quickbook
From: daniel_james_at_[hidden]
Date: 2010-03-31 17:39:09
Author: danieljames
Date: 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
New Revision: 60980
URL: http://svn.boost.org/trac/boost/changeset/60980
Log:
Merge from trunk.
- Add `quick_erase` for unordered. `erase_return_void` is now deprecated.
Fixes #3966
- Avoid collision between 0 and 0.5. Fixes #4038
Properties modified:
branches/release/boost/functional/hash/ (props changed)
branches/release/boost/iostreams/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/libs/functional/hash/ (props changed)
branches/release/libs/iostreams/ (props changed)
branches/release/libs/unordered/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/quickbook/ (props changed)
Text files modified:
branches/release/boost/functional/hash/detail/hash_float_generic.hpp | 8 -
branches/release/boost/unordered/unordered_map.hpp | 10 ++
branches/release/boost/unordered/unordered_set.hpp | 10 ++
branches/release/libs/functional/hash/test/hash_float_test.hpp | 17 ++++
branches/release/libs/unordered/doc/changes.qbk | 11 +++
branches/release/libs/unordered/doc/ref.xml | 144 +++++++++++++++++++++++++++++++++------
branches/release/libs/unordered/test/unordered/erase_tests.cpp | 8 +-
7 files changed, 175 insertions(+), 33 deletions(-)
Modified: branches/release/boost/functional/hash/detail/hash_float_generic.hpp
==============================================================================
--- branches/release/boost/functional/hash/detail/hash_float_generic.hpp (original)
+++ branches/release/boost/functional/hash/detail/hash_float_generic.hpp 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
@@ -51,17 +51,15 @@
limits<T>::min_exponent;
}
- // The result of frexp is always between 0.5 and 1, so its
- // top bit will always be 1. Subtract by 0.5 to remove that.
- v -= T(0.5);
- v = ldexp(v, limits<std::size_t>::digits + 1);
+ v = ldexp(v, limits<std::size_t>::digits);
std::size_t seed = static_cast<std::size_t>(v);
v -= seed;
// ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1;
std::size_t const length
= (limits<T>::digits *
- boost::static_log2<limits<T>::radix>::value - 1)
+ boost::static_log2<limits<T>::radix>::value
+ + limits<std::size_t>::digits - 1)
/ limits<std::size_t>::digits;
for(std::size_t i = 0; i != length; ++i)
Modified: branches/release/boost/unordered/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_map.hpp (original)
+++ branches/release/boost/unordered/unordered_map.hpp 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
@@ -369,6 +369,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void quick_erase(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void erase_return_void(const_iterator position)
{
table_.erase(get(position));
@@ -907,6 +912,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void quick_erase(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void erase_return_void(const_iterator position)
{
table_.erase(get(position));
Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp (original)
+++ branches/release/boost/unordered/unordered_set.hpp 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
@@ -361,6 +361,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void quick_erase(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void erase_return_void(const_iterator position)
{
table_.erase(get(position));
@@ -849,6 +854,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void quick_erase(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void erase_return_void(const_iterator position)
{
table_.erase(get(position));
Modified: branches/release/libs/functional/hash/test/hash_float_test.hpp
==============================================================================
--- branches/release/libs/functional/hash/test/hash_float_test.hpp (original)
+++ branches/release/libs/functional/hash/test/hash_float_test.hpp 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
@@ -79,6 +79,11 @@
BOOST_TEST(x1(minus_zero) == HASH_NAMESPACE::hash_value(minus_zero));
#endif
+ BOOST_TEST(x1(zero) != x1(0.5));
+ BOOST_TEST(x1(minus_zero) != x1(0.5));
+ BOOST_TEST(x1(0.5) != x1(-0.5));
+ BOOST_TEST(x1(1) != x1(-1));
+
using namespace std;
// Doing anything with infinity causes borland to crash.
@@ -176,6 +181,12 @@
BOOST_TEST(half_max != three_quarter_max);
BOOST_TEST(quarter_max != three_quarter_max);
+ BOOST_TEST(max != -max);
+ BOOST_TEST(half_max != -half_max);
+ BOOST_TEST(quarter_max != -quarter_max);
+ BOOST_TEST(three_quarter_max != -three_quarter_max);
+
+
#if defined(TEST_EXTENSIONS)
BOOST_TEST(x1(max) == HASH_NAMESPACE::hash_value(max));
BOOST_TEST(x1(half_max) == HASH_NAMESPACE::hash_value(half_max));
@@ -197,6 +208,12 @@
BOOST_TEST(x1(half_max) != x1(three_quarter_max));
BOOST_TEST(x1(three_quarter_max) == x1(three_quarter_max));
+ BOOST_TEST(x1(max) != x1(-max));
+ BOOST_TEST(x1(half_max) != x1(-half_max));
+ BOOST_TEST(x1(quarter_max) != x1(-quarter_max));
+ BOOST_TEST(x1(three_quarter_max) != x1(-three_quarter_max));
+
+
// Intel with gcc stdlib sometimes segfaults on calls to asin and acos.
#if !((defined(__INTEL_COMPILER) || defined(__ICL) || \
defined(__ICC) || defined(__ECC)) && \
Modified: branches/release/libs/unordered/doc/changes.qbk
==============================================================================
--- branches/release/libs/unordered/doc/changes.qbk (original)
+++ branches/release/libs/unordered/doc/changes.qbk 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
@@ -117,4 +117,15 @@
Add missing `std` qualifier to `ptrdiff_t`.
* Some code formatting changes to fit almost all lines into 80 characters.
+
+[h2 Boost 1.43.0]
+
+* [@http://svn.boost.org/trac/boost/ticket/3966 Ticket 3966]:
+ `erase_return_void` is now `quick_erase`, which is the
+ [@http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579
+ current forerunner for resolving the slow erase by iterator], although
+ there's a strong possibility that this may change in the future. The old
+ method name remains for backwards compatibility but is considered deprecated
+ and will be removed in a future release.
+
[endsect]
Modified: branches/release/libs/unordered/doc/ref.xml
==============================================================================
--- branches/release/libs/unordered/doc/ref.xml (original)
+++ branches/release/libs/unordered/doc/ref.xml 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
@@ -464,8 +464,8 @@
When the number of elements is a lot smaller than the number of buckets
this function can be very inefficient as it has to search through empty
buckets for the next element, in order to return the iterator.
- As a temporary workaround, the container has the method
- <methodname>erase_return_void</methodname> which will be faster.
+ The method <methodname>quick_erase</methodname> is faster, but has yet
+ to be standardized.
</para>
</notes>
</method>
@@ -503,6 +503,30 @@
<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="quick_erase">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <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>
+ <notes>
+ <para>
+ This method is faster than <methodname>erase</methodname> as
+ it doesn't have to find the next element in the container -
+ a potentially costly operation.
+ </para>
+ <para>
+ As it hasn't been standardized, it's likely that this may
+ change in the future.
+ </para>
+ </notes>
+ </method>
<method name="erase_return_void">
<parameter name="position">
<paramtype>const_iterator</paramtype>
@@ -517,10 +541,10 @@
</throws>
<notes>
<para>
- This is a temporary workaround for the inefficient
- <methodname>erase</methodname> method. Hopefully, in a future
- version the signature of <methodname>erase</methodname> will
- be changed and this will be deprecated.
+ This method is now deprecated, use
+ <methodname>quick_return</methodname> instead. Although be
+ warned that as that isn't standardized yet, it could also
+ change.
</para>
</notes>
</method>
@@ -1327,8 +1351,8 @@
When the number of elements is a lot smaller than the number of buckets
this function can be very inefficient as it has to search through empty
buckets for the next element, in order to return the iterator.
- As a temporary workaround, the container has the method
- <methodname>erase_return_void</methodname> which will be faster.
+ The method <methodname>quick_erase</methodname> is faster, but has yet
+ to be standardized.
</para>
</notes>
</method>
@@ -1366,6 +1390,30 @@
<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="quick_erase">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <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>
+ <notes>
+ <para>
+ This method is faster than <methodname>erase</methodname> as
+ it doesn't have to find the next element in the container -
+ a potentially costly operation.
+ </para>
+ <para>
+ As it hasn't been standardized, it's likely that this may
+ change in the future.
+ </para>
+ </notes>
+ </method>
<method name="erase_return_void">
<parameter name="position">
<paramtype>const_iterator</paramtype>
@@ -1380,10 +1428,10 @@
</throws>
<notes>
<para>
- This is a temporary workaround for the inefficient
- <methodname>erase</methodname> method. Hopefully, in a future
- version the signature of <methodname>erase</methodname> will
- be changed and this will be deprecated.
+ This method is now deprecated, use
+ <methodname>quick_return</methodname> instead. Although be
+ warned that as that isn't standardized yet, it could also
+ change.
</para>
</notes>
</method>
@@ -2204,8 +2252,8 @@
When the number of elements is a lot smaller than the number of buckets
this function can be very inefficient as it has to search through empty
buckets for the next element, in order to return the iterator.
- As a temporary workaround, the container has the method
- <methodname>erase_return_void</methodname> which will be faster.
+ The method <methodname>quick_erase</methodname> is faster, but has yet
+ to be standardized.
</para>
</notes>
</method>
@@ -2243,6 +2291,30 @@
<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="quick_erase">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <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>
+ <notes>
+ <para>
+ This method is faster than <methodname>erase</methodname> as
+ it doesn't have to find the next element in the container -
+ a potentially costly operation.
+ </para>
+ <para>
+ As it hasn't been standardized, it's likely that this may
+ change in the future.
+ </para>
+ </notes>
+ </method>
<method name="erase_return_void">
<parameter name="position">
<paramtype>const_iterator</paramtype>
@@ -2257,10 +2329,10 @@
</throws>
<notes>
<para>
- This is a temporary workaround for the inefficient
- <methodname>erase</methodname> method. Hopefully, in a future
- version the signature of <methodname>erase</methodname> will
- be changed and this will be deprecated.
+ This method is now deprecated, use
+ <methodname>quick_return</methodname> instead. Although be
+ warned that as that isn't standardized yet, it could also
+ change.
</para>
</notes>
</method>
@@ -3116,8 +3188,8 @@
When the number of elements is a lot smaller than the number of buckets
this function can be very inefficient as it has to search through empty
buckets for the next element, in order to return the iterator.
- As a temporary workaround, the container has the method
- <methodname>erase_return_void</methodname> which will be faster.
+ The method <methodname>quick_erase</methodname> is faster, but has yet
+ to be standardized.
</para>
</notes>
</method>
@@ -3155,6 +3227,30 @@
<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="quick_erase">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <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>
+ <notes>
+ <para>
+ This method is faster than <methodname>erase</methodname> as
+ it doesn't have to find the next element in the container -
+ a potentially costly operation.
+ </para>
+ <para>
+ As it hasn't been standardized, it's likely that this may
+ change in the future.
+ </para>
+ </notes>
+ </method>
<method name="erase_return_void">
<parameter name="position">
<paramtype>const_iterator</paramtype>
@@ -3169,10 +3265,10 @@
</throws>
<notes>
<para>
- This is a temporary workaround for the inefficient
- <methodname>erase</methodname> method. Hopefully, in a future
- version the signature of <methodname>erase</methodname> will
- be changed and this will be deprecated.
+ This method is now deprecated, use
+ <methodname>quick_return</methodname> instead. Although be
+ warned that as that isn't standardized yet, it could also
+ change.
</para>
</notes>
</method>
Modified: branches/release/libs/unordered/test/unordered/erase_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/erase_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/erase_tests.cpp 2010-03-31 17:39:07 EDT (Wed, 31 Mar 2010)
@@ -116,7 +116,7 @@
BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin());
}
- std::cerr<<"erase_return_void(begin()).\n";
+ std::cerr<<"quick_erase(begin()).\n";
{
test::random_values<Container> v(1000, generator);
Container x(v.begin(), v.end());
@@ -126,7 +126,7 @@
BOOST_DEDUCED_TYPENAME Container::key_type
key = test::get_key<Container>(*x.begin());
std::size_t count = x.count(key);
- x.erase_return_void(x.begin());
+ x.quick_erase(x.begin());
--size;
BOOST_TEST(x.count(key) == count - 1);
BOOST_TEST(x.size() == size);
@@ -134,7 +134,7 @@
BOOST_TEST(x.empty());
}
- std::cerr<<"erase_return_void(random position).\n";
+ std::cerr<<"quick_erase(random position).\n";
{
test::random_values<Container> v(1000, generator);
Container x(v.begin(), v.end());
@@ -155,7 +155,7 @@
BOOST_DEDUCED_TYPENAME Container::key_type
key = test::get_key<Container>(*pos);
std::size_t count = x.count(key);
- x.erase_return_void(pos);
+ x.quick_erase(pos);
--size;
if(size > 0)
BOOST_TEST(index == 0 ? next == x.begin() :
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